B木

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

1ノードに複数のキーと子ポインタを持つ多分木構造の平衡探索木。ディスクアクセスの回数を最小化するよう設計され、データベースのインデックスやファイルシステムで広く使用される。全葉が同じ深さにある。

ディスクベースのデータ構造で多分木の一種。すべての葉ノードが同じ深さにあり、各ノードに複数のキーを格納する。探索、挿入、削除がO(log n)で実行でき、DBMSのインデックス構造として広く利用される。

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

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

どの節でも左右の部分木の高さの差が1以下になるように保つ2分探索木。挿入や削除で条件が崩れると、回転と呼ぶ操作で形を直すため、探索、挿入、削除をO(log n)で行える。

平衡木構造を用いたインデックス方式。ルートノードからリーフノードまでの深さが均一であり、検索・挿入・削除の計算量がO(log n)で安定している。関係データベースで最も一般的に使用されるインデックス構造。

重複した値の登録を許さないインデックス。検索を速くすると同時に一意性も保証する。主キーや一意性制約を定義すると、DBMSが自動的にこの索引を作ることが多い。

インデックスの並び順に合わせて、データそのものを物理的に並べて格納する方式。範囲検索でディスクアクセスがまとまるため高速だが、1つの表に1つしか作れない。