アルゴリズム・データ構造図鑑 · 基礎から応用へ

B木:一度のページ読み込みで多くのキーを調べる

多分岐と高さの制御により、外部記憶の探索回数を抑える仕組みを理解する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. ノードに複数の区切りキーを持つ
  2. キー35を探す道筋
  3. 分割と統合で平衡を保つ
  4. DBの索引を見るときの注意
  5. この記事をロゲイアに質問する理解を確かめる

ノードに複数の区切りキーを持つ

B木は、一つのノードに複数の整列済みキーと子への参照を持つ平衡探索木です。たとえばノードの区切りが[20,50]なら、探索先を20未満、20と50の間、50超の三つの範囲へ分けられます。各ノードを記憶装置のページに収め、多数の分岐を一つのページを読み込んだ時点で候補を大きく絞れるようにします。分岐数が大きいと木の高さを小さくでき、根から葉へたどるページ数を減らせます。

キー35を探す道筋

根に[20,50]があり、中央の子に[28,40]があるとします。35は根で中央を選び、次のページでは28と40の間の子を選びます。比較はページ内でも行いますが、外部記憶では比較回数だけでなく、別ページを読みに行く回数が重要です。根や上段のページがキャッシュされていれば、すべての段で実際の装置読み込みが起こるとも限りません。論理的な高さと物理I/Oを分けて考えます。

分割と統合で平衡を保つ

挿入先のノードが満杯なら、分割して区切りキーを親へ反映します。親も満杯なら変更が上へ伝わり、根が分割されたときには高さが一段増えます。逆に削除で少なすぎるノードが生じたら、隣からの再配分や統合で条件を回復します。キー数の上下限や「次数」の定義は説明・実装によって表記が異なるため、具体的な値を計算するときには採用する規則を先に確認します。

DBの索引を見るときの注意

実際のDBには、値を葉へ集めて葉を連結するB+木系の変種などがあります。整列した葉は範囲走査に役立ちますが、索引があればすべての問い合わせが速くなるわけではありません。多数行を取得する場合や、索引のキー順と条件が合わない場合は別の計画が選ばれます。索引更新には書き込みと領域の費用もかかります。B木の原理と、使っているDBのページ構造・実行計画の仕様を区別して確認します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

サーバーの中で起きていること · STEP 12

学習コースから次を選ぶ