B+木とは？

B+木の意味

データベースの索引に広く使われる多分木。すべてのデータは葉（リーフ）にあり、葉は同じ深さでキー順に相互リンクされている。検索は木の高さに比例するのでO(log n)、範囲検索は葉のリンクをたどれば効率よく行える。

B+木の具体例

葉が満杯になると分割して親に昇格させるため、木の高さは均等に保たれる。

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

分割後もすべての葉は同じ深さのまま。等値検索だけでなく範囲検索に強い点がハッシュ索引との違い。

B+木と関連する用語

• 2分探索木
• 索引

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）