B+木

B+木（B+ tree）は、キーを指定することで挿入・検索・削除が効率的に行える木構造の一種である。動的な階層型インデックスであり、各インデックスセグメント（「ブロック」などと呼ばれる。木構造におけるノードに相当）にはキー数の上限と下限がある。B+木はB木とは異なり、全てのレコードは木の最下層（葉ノード）に格納され、内部ノードにはキーのみが格納される。B+木は、特にブロック型記憶装置での効率的データ検索に効果を発揮する。ブロックサイズ <math>b</math> の記憶装置があるとき、<math>b</math> の倍数個のキーを格納するB+木は2分探索木に比較して非常に効率が良い（2分探索木はブロック型でない記憶装置に適している）。ReiserFS（UNIX、Linux）、XFS（IRIX、Linux）、JFS2（AIX、OS/2、Linux）、HammerFS（DragonFly BSD）、NTFSといったファイルシステムはいずれもB+木に類する構造をブロックのインデックス付けに使っている。関係データベースでも表のインデックスにこの種の木構造を使っていることが多い。