B+木とは？

B+木の意味

実データ（または行の位置）を葉ノードにだけ持ち、葉どうしをキー順のポインタで連結したB木の変形。関係データベースの標準的な索引構造。

B+木の具体例

「日付が4月1日から4月30日までの範囲」を検索するとき、開始位置の葉に到達してから連結をたどるだけで済む。

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

範囲検索・整列・前方一致に強い一方、値の一致検索の一撃の速さではハッシュ索引に劣る。葉が分割されても分割後の両方のノードは同じ深さに保たれ、葉の連結順序はキー順のまま維持される。

B+木と関連する用語

• B木
• ハッシュインデックス

B+木が出た過去問

• B+木インデックスとビットマップインデックスを比較した説明のうち、適切なものはどれか。

  正解：少数の異なる値をもつ列への検索は、ビットマップインデックスの方が有効である。

  要点：値の種類が少ない列にはビットマップインデックスが有効

  ビットマップインデックスは、列がとり得る値ごとに行の該当有無をビット列で表す方式である。値の種類（カーディナリティ）が少ないほどビット列の本数が少なく済んで効率がよく、性別や区分コードのような列に向いている。

  出典：平成30年度 春期 データベーススペシャリスト試験 am2 問15（IPA）

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

  正解：log X

  要点：B+木の探索は木の高さ分、つまり対数オーダー

  B+木は根から葉へ向かって多分岐でたどる平衡木で、木の高さはデータ件数の対数に比例する。検索は根から葉まで1経路をたどるだけなので、アクセス回数のオーダーは件数の対数になる。よってイが正しい。

  出典：令和5年度 秋期 データベーススペシャリスト試験 am2 問4（IPA）

• "部品"表のメーカーコード列に対し、B+木インデックスを作成した。これによって、"部品"表の検索の性能改善が最も期待できる操作はどれか。ここで、部品及びメーカー…

  正解：メーカーコードの値が4001以上、4003以下の部品を検索する。

  要点：B+木索引が効くのは値の順序を活かせる範囲検索

  B+木は葉ノードがキー値の順に並んでいるため、範囲の下限を索引で探し当てた後は葉をたどるだけで該当行を集められる。一方、否定条件やNULL以外といった条件は対象がほぼ全件に及ぶので、索引を経由するより表を直接走査したほうが速く、性能改善は期待できない。よってウが最も効果を見込める。

  出典：令和5年度 秋期 データベーススペシャリスト試験 am2 問13（IPA）

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

  正解：選択肢イ：AがB,C1,C2,Dの4ノードを指し、B↔C1↔C2↔Dの順で連結。

  要点：リーフ分割後も2つとも親直下、リーフ列はキー順連結

  B+木でリーフがあふれて分割されると、分割後の2つのリーフはどちらも親（中間ノード）から直接ポインタで参照される。親に空きがある前提なので、親へキーとポインタを1つ追加するだけで済み、それ以上は上位へ波及しない。またB+木のリーフはキー順の双方向リストでつながっているため、分割後もキーの順序どおりに前後のリーフと連結し直される。この2条件を同時に満たす構造が正解となる。

  出典：令和6年度 秋期 データベーススペシャリスト試験 am2 問3（IPA）