ノードに複数の区切りキーを持つ
B木は、一つのノードに複数の整列済みキーと子への参照を持つ平衡探索木です。たとえばノードの区切りが[20,50]なら、探索先を20未満、20と50の間、50超の三つの範囲へ分けられます。各ノードを記憶装置のページに収め、多数の分岐を一つのページを読み込んだ時点で候補を大きく絞れるようにします。分岐数が大きいと木の高さを小さくでき、根から葉へたどるページ数を減らせます。
キー35を探す道筋
根に[20,50]があり、中央の子に[28,40]があるとします。35は根で中央を選び、次のページでは28と40の間の子を選びます。比較はページ内でも行いますが、外部記憶では比較回数だけでなく、別ページを読みに行く回数が重要です。根や上段のページがキャッシュされていれば、すべての段で実際の装置読み込みが起こるとも限りません。論理的な高さと物理I/Oを分けて考えます。
分割と統合で平衡を保つ
挿入先のノードが満杯なら、分割して区切りキーを親へ反映します。親も満杯なら変更が上へ伝わり、根が分割されたときには高さが一段増えます。逆に削除で少なすぎるノードが生じたら、隣からの再配分や統合で条件を回復します。キー数の上下限や「次数」の定義は説明・実装によって表記が異なるため、具体的な値を計算するときには採用する規則を先に確認します。
DBの索引を見るときの注意
実際のDBには、値を葉へ集めて葉を連結するB+木系の変種などがあります。整列した葉は範囲走査に役立ちますが、索引があればすべての問い合わせが速くなるわけではありません。多数行を取得する場合や、索引のキー順と条件が合わない場合は別の計画が選ばれます。索引更新には書き込みと領域の費用もかかります。B木の原理と、使っているDBのページ構造・実行計画の仕様を区別して確認します。