B+木

B木を改良したデータ構造で、データ（またはその所在）は葉にだけ格納し、内部の節は探索のためのキーだけを持つ。葉どうしがポインタで順につながっているため、範囲を指定した検索や順次の読出しが速く、データベースの索引に広く使われる。

キーを整列した状態で保持する平衡木（B木やB+木）で構成した索引で、根から葉までの深さがどのキーでも同じなので、データ量がnのとき探索・挿入・削除をO(log n)で行える。一致検索のほか範囲検索や並び替えにも使えるため、多くのDBMSで標準の索引方式になっている。値の種類が多い（カーディナリティが高い）列に向く。

1つの節点が3つ以上の子を持てる木で、m個までの子を持つものをm分木という。1つの節点に多くのキーと子を持たせると木の高さが低くなり、根から葉までにたどる節点が少なくて済む。この性質を使ったB木やB+木は、ディスクの1回の読込みで多くのキーを比較できるので、データベースの索引に使われる。

各ノードが最大2つの子ノードを持つ木構造。左の子と右の子に分かれる。2分探索木、ヒープ、式木など多くの応用がある。探索や整列の効率的な実装に使われる。

左の子ノードの値が親より小さく、右の子ノードの値が親より大きいという条件を満たす2分木。探索・挿入・削除の平均計算量がO(log n)で効率的。バランスが崩れるとO(n)に悪化する。

親ノードの値が子ノードの値以上（最大ヒープ）または以下（最小ヒープ）という条件を満たす完全2分木。最大値または最小値の取得がO(1)で可能。優先度付きキューやヒープソートの実装に使用される。

1つのノードが複数のキーと子ノードを持てるバランス木。全ての葉ノードが同じ深さにあり、データベースのインデックスやファイルシステムで使用される。ディスクアクセスを最小化するために設計された。