B+木とは？びーぷらすき
B+木とは、データベースの索引に広く使われる多分木。値はすべて葉に置かれ、葉はどれも同じ深さに揃い、キー順に隣どうしがリンクされている。1つの節点に多数のキーを詰めるので木が低く、検索はO(log n)、範囲検索は葉のリンクをたどるだけで済む。
最終更新：2026-10-07
この語が出る過去問を解く →背景
索引はメモリに載りきらずディスクに置かれることが多く、性能を決めるのは比較回数よりディスクアクセスの回数になる。1節点をディスクの1ページ分の大きさにして分岐数を数百に増やせば、数百万件でも数回のアクセスで葉に届く。B木との違いは、値を葉だけに置いて内部節点を道案内に徹させ、さらに葉どうしを順につないだ点にある。
具体例
PostgreSQLやMySQL（InnoDB）の既定の索引はB+木。葉が満杯になると分割してキーを親へ昇格させ、それが根まで届いたときだけ木全体が1段高くなる。この作り方のおかげで、どの葉も深さが揃った状態が保たれる。
試験での引っ掛け
ハッシュ索引との分岐点は範囲検索。ハッシュは等値検索が速い代わりに「〜以上〜以下」に使えず、B+木は葉のリンクをたどって範囲を走査できる。分割が起きても片側だけ深くなることはない。またワイルドカードで始まるLIKEのような後方一致には索引が効かない点も問われる。
関連用語
出た過去問
出典：平成30年度 春期 高度試験 午前Ⅰ 問8（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には空きがあるので木の高さは変わらない。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。