B-treeインデックス

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

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

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

表のデータ行そのものを、インデックスのキーの順に物理的に並べて格納するインデックス。キーの範囲を指定する検索では目的の行が連続した領域にまとまっているので、読み込むページが少なくて済む。データの並び順は1通りしか取れないため、1つの表に1つだけ作成できる。

列が取り得る値ごとに、各行がその値を持つかどうかを1ビットで表したビット列を持つインデックス。性別や地域のように値の種類が少ない列に向き、複数の条件の組合せをビット列の論理演算で高速に絞り込める。更新のたびにビット列を書き換えるので、更新の多い表には向かない。

キー値をハッシュ関数で変換した値から、データの格納位置を直接求めるインデックス。キー値が完全に一致する行の検索は高速だが、範囲検索や大小比較、並べ替えには使えない。

ある問合せで参照する列をすべて含んでいるインデックス。インデックスを読むだけで結果を返せ、表本体のデータを読みに行かずに済むので、ディスクへのアクセスが減って検索が速くなる。

単語ごとに、その単語を含む文書とその出現位置の一覧を記録したインデックス。全文検索で使われ、大量の文書からキーワードを含むものを、文書を順に読むことなく高速に見つけられる。