B+木
B+ Tree
びーぷらすぎ
B木を改良したデータ構造で、データ（またはその所在）は葉にだけ格納し、内部の節は探索のためのキーだけを持つ。葉どうしがポインタで順につながっているため、範囲を指定した検索や順次の読出しが速く、データベースの索引に広く使われる。
Past Exams
過去問での出題
過去問で 3 回出題（応用情報技術者試験 1・データベーススペシャリスト試験 1・高度試験 午前Ⅰ 1）
出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。用語名で照合しているため、関係の薄い問題が含まれることがあります。
Related
関連キーワードの用語
1つの節に複数のキーと子へのポインタを持ち、すべての葉が同じ深さになるように保たれる多分木のバランス木。1つの節を補助記憶の1ブロックに対応させるとアクセスの回数を少なくできるため、データベースやファイルシステムの索引に使われる。
キーを整列した状態で保持する平衡木（B木やB+木）で構成した索引で、根から葉までの深さがどのキーでも同じなので、データ量がnのとき探索・挿入・削除をO(log n)で行える。一致検索のほか範囲検索や並び替えにも使えるため、多くのDBMSで標準の索引方式になっている。値の種類が多い（カーディナリティが高い）列に向く。
要素の挿入や削除のたびに木の形を調整し、根から各葉までの深さがほぼ等しくなるように保つ木構造で、平衡木ともいう。探索、挿入、削除をいずれもO(log n)で行える。AVL木やB木、赤黒木などがある。
どの節でも左右の部分木の高さの差が1以下になるように保つ2分探索木。挿入や削除で条件が崩れると、回転と呼ぶ操作で形を直すため、探索、挿入、削除をO(log n)で行える。
平衡木構造を用いたインデックス方式。ルートノードからリーフノードまでの深さが均一であり、検索・挿入・削除の計算量がO(log n)で安定している。関係データベースで最も一般的に使用されるインデックス構造。
重複した値の登録を許さないインデックス。検索を速くすると同時に一意性も保証する。主キーや一意性制約を定義すると、DBMSが自動的にこの索引を作ることが多い。