B-tree インデックス

B-treeインデックスは、キーを常に高さがほぼ均等な多分木へ格納する索引です。根から比較を繰り返して葉へ到達し、等価検索、大小比較、範囲検索、順序付き走査に広く使われます。

■ 試験で押さえるポイント

• 一ノードに多数のキーと子ポインタを収容して木の高さを低く保ち、全ての葉を同じ深さにするため、検索・挿入・削除は概ね$O(\log n)$です。

• B+木型では実データへの参照を葉に集め、葉同士をキー順に連結するため、開始キーを見つけた後の範囲走査を連続して行えます。

• 複合索引(a,b)は通常、先頭のa又はaを固定したbの検索に有効です。bだけの条件には並びの先頭を利用できず、十分な効果がない場合があります。

• 挿入先ページが満杯なら分割し、削除では統合や再配置が起こります。索引は更新負荷を伴い、大量行を読む問合せでは表走査が選ばれることもあります。

■ 選択肢での判断ポイント

=、<、>、BETWEEN、ORDER BYに使える点と、ハッシュ索引が範囲・順序に不向きな点を比較します。複合索引は左端列からの条件を確認します。

例: 索引(部署番号, 給与)なら、部署10で給与30万～50万円の検索は部署10の葉範囲を走査できます。給与だけの検索では全部署の給与が連続しておらず使いにくくなります。