B+木インデックスとは？

B+木インデックスの意味

関係DBMSで最も一般的な索引構造。内部節点はキーとポインタだけを持ち、実データへの参照はすべて葉に置く。葉同士が順方向にリンクされるため、等値検索だけでなく範囲検索やORDER BYにも効く。木の高さが低く保たれ探索は対数時間になる。

B+木インデックスの具体例

1,000万行の受注表で受注日に索引を張ると、「先月分」の範囲検索は葉のリンクをたどるだけで済む。木の高さが3〜4段なら数回のページ読込みで開始位置に到達でき、全表走査で数万ページ読む場合と桁違いの差が出る。

B+木インデックスは試験でどう引っ掛けられる？

B木（B-tree）とB+木の違いは、B+木が実データ参照を葉だけに持ち葉をリンクする点。範囲検索の効率差はここから来る。またハッシュ索引は等値検索専用で範囲検索や整列には使えないという対比も問われる。

B+木インデックスと関連する用語

• インデックス設計の指針（選択率・複合索引）
• ビットマップインデックスとハッシュインデックス
• 実行計画とクエリオプティマイザ

B+木インデックスが出た過去問

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

  正解：logX

  要点：B+木の探索コストは件数の対数オーダ

  B+木は根から葉まで階層をたどる木構造で、1つのノードが多数の子を持つため木の高さはデータ件数の対数に比例します。候補キーで1件を検索する場合、根から葉までのノードをたどる回数がアクセス回数になるので、オーダは log X です。件数が増えても高さの伸びが緩やかなことが、大規模な表でも高速に検索できる理由です。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問27（IPA）

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

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

  要点：B+木インデックスは範囲検索で最も効果を発揮する

  B+木インデックスは値が大小順に並び、葉ノードが順につながっているため、ある範囲に含まれる値をまとめて取り出す範囲検索で効果が大きい。値の種類が多く均一に分散していれば、絞り込まれる行数も少なくて済む。

  出典：平成29年度 春期 応用情報技術者試験 午前 問28（IPA）

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

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

  要点：B+木インデックスは絞り込みの効く範囲・等値検索で効果が大きい。

  B+木インデックスは葉ノードがキー順に連結されているため、ある範囲に収まる値を探す検索や、特定の値に等しい行を探す検索で効率がよい。値の種類が多く均一に分散している状況で、限られた範囲だけを取り出す検索は、絞り込みが強く働くのでインデックスの効果が大きい。一方、否定条件のように表の大部分が該当する検索では、表全体を読むほうが速く、インデックスは活かせない。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問29（IPA）

• “売上”表への次の検索処理のうち、B+木インデックスよりもハッシュインデックスを設定した方が適切なものはどれか。ここで、インデックスを設定する列を＜＞内に示す。…

  正解：利用者IDが'1001'の売上を検索する。＜利用者ID＞

  要点：ハッシュインデックスは等価検索専用。範囲検索は不可

  ハッシュインデックスは、キーの値をハッシュ関数で変換して格納位置を求めるため、値が完全に一致する等価検索を高速に処理できる。一方で値の大小関係や並び順は保持しないので、範囲検索や前方一致検索には使えない。利用者IDが特定の値と一致する行を探す検索はまさに等価検索であり、ハッシュインデックスが適する。

  出典：令和5年度 秋期 応用情報技術者試験 午前 問26（IPA）