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+木の探索コストは件数の対数オーダ

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

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

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

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

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

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

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

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

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

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

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

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

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

  正解：イ：中間ノードAからB、C1、C2、Dの4つ全てに矢印。リーフノードは B⇔C1⇔C2⇔D の順で相互連結。

  要点：B+木は全リーフを親が参照し順序どおり連結する

  B+木ではすべてのキーがリーフノードに置かれ、リーフ同士が順次アクセス用のポインタで連結される。リーフが分割されたときは、新しいリーフも親ノードから参照されるようポインタを追加し、リーフ間の連結もキー順を保つよう張り替える必要がある。したがって親AからB・C1・C2・Dの4つすべてへポインタがあり、リーフがB⇔C1⇔C2⇔Dの順で連結された構造が正しい。

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

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

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

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

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

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