B木とは？ビーき
B木とは、1ノードに複数のキーと子ポインタを詰め、根から全ての葉までの高さを常に等しく保つ多分探索木。1ノードをディスクの1ページに合わせることで、数百万行でも数回のページ読込みで目的のキーに届く。RDBMSの索引は葉に全キーを並べたB+木として実装している。
最終更新：2026-10-06
データベースSPを最短で暗記・合格する →背景
主記憶向けの二分探索木をそのままディスクへ置くと、比較のたびにI/Oが起き、段数がそのまま待ち時間になる。1回のI/Oで読めるのはページ単位なので、「1回読むごとに枝を2本ではなく数百本に絞る」ようノードを太らせたのがB木である。挿入・削除を繰り返しても高さが揃うため最悪応答時間が見積もれ、索引設計を数値で議論できる前提になっている。
具体例
Rudolf BayerとEdward McCreightが1972年に発表した構造で、Oracle Database・PostgreSQL・MySQL（InnoDB）のいずれも既定の索引はB+木である。会員表100万行に会員番号の索引を張ると高さは3段程度に収まり、行数が10倍になっても4段に増えるだけで済む。
試験での引っ掛け
探索コストは行数nではなく木の高さ、すなわち対数オーダーで増える。「行数が10倍なら索引探索も10倍遅い」は誤り。また葉を順にたどれるB+木だからこそ範囲検索やORDER BYに使える点が、順序を持たないハッシュ索引との分かれ目になる。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。