B木・B+木とは？

B木・B+木の意味

1つの節点に多数のキーと子ポインタを持たせ、木の高さを極端に低く抑えた多分木。ディスクの1ブロック＝1節点として読み込むことでI/O回数を減らす設計で、B+木はデータを葉だけに置き、葉同士を連結して範囲検索を高速化した派生形。

B木・B+木の具体例

1節点に200の分岐を持たせられるなら、3段でも200の3乗＝800万件、4段で16億件に届く。データベースの索引はこの性質を使い、数億行のテーブルでも数回のディスクアクセスで目的行に到達できるようにしている。

B木・B+木は試験でどう引っ掛けられる？

B木の「B」はbinary（2分）ではない。二分木と違い1節点に複数キーを持つ。またB+木はすべての実データが葉にあるため、範囲検索やソート済み読み出しはB木より速いが、単一キー検索では必ず葉まで下りる分だけ不利になり得る。

B木・B+木と関連する用語

• 平衡木（AVL木・赤黒木）
• 二分探索木（BST）
• 木構造（二分木）

B木・B+木が出た過去問

• B+木インデックスが定義されている候補キーを利用して、1件のデータを検索するとき、データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオー…

  正解：logX

  要点：B+木の検索は木の高さ、すなわちO(log X)

  B+木は全ての葉が同じ深さになる平衡木で、1ノードに多数のキーを収めて木の高さを抑える構造である。1件の検索は根から葉までを1回ずつたどるのでアクセス回数は木の高さに等しく、データ総件数Xに対してO(log X)のオーダとなる。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問9（IPA）

• 関係データベースのテーブルにレコードを1件追加したところ、インデックスとして使う、図のB+木のリーフノードCがノードC1とC2に分割された。ノード分割後のB+木…

  正解：中間ノードAから、B、C1、C2、Dの4つのリーフノードへポインタが伸びる。リーフノード同士はB↔C1↔C2↔Dの順に双方向リンクでつながる。

  要点：B+木の分割後もリーフは同じ深さでキー順にリンクされる

  B+木ではすべてのリーフノードが同じ深さに置かれ、リーフは親ノードから直接ポインタで指される。リーフCが分割されてC1とC2になった場合、両方とも親である中間ノードAの直下に並び、キー値の順序どおりに B→C1→C2→D とリーフ同士が順次リンクされる。中間ノードAには空きがあるので木の高さは変わらない。

  出典：平成30年度 春期 高度共通_午前I試験 am1 問8（IPA）