索引

データベースのテーブルに対する検索を高速化するための索引。本の索引のように、目的のデータの位置を素早く特定できるようにする仕組み。

データベースの検索性能を向上させるために、テーブルのデータとは別に作成されるデータ構造。B-treeインデックスやハッシュインデックスなどの種類があり、特定の列に対する検索を高速化する。更新時はインデックスのメンテナンスコストが発生する。

データベースで、表の特定の列の値から行の格納位置をすばやく探せるようにする、表とは別に作るデータ構造。索引ともいう。検索は速くなるが、行の追加・更新・削除のたびにインデックスも更新されるため、更新の多い表では処理が遅くなる。B-treeインデックス、ビットマップインデックス、ハッシュインデックスなどの種類がある。

テーブルの特定の列に対する検索を高速化するためのデータ構造。キー値とデータの物理位置の対応関係を保持する。検索性能は向上するが、更新時にインデックスの維持コストが発生する。

キーの値をハッシュ関数で変換した値をもとに格納位置を決める索引。キーの値が一致する行を、データ量によらずほぼ一定の時間で探せる。一方、ハッシュ値には元の値の大小関係が残らないので、範囲検索や並び替えには使えない。

問合せで必要な列をすべて含んでいる索引。検索条件の列だけでなく、選択リストや並び替えに使う列も索引に持たせることで、表本体を読まずに索引だけで結果を返せる（インデックスオンリースキャン）。表へのアクセスが省けて入出力が減るが、索引が大きくなり更新の負荷が増える。

キーの値が重複しないことを保証する索引。重複する値の行を追加・更新しようとするとエラーになる。主キー制約や一意性制約を定義すると、多くのDBMSは一意性の検査のためにユニークインデックスを自動で作成する。

表の行そのものを、索引のキーの順に物理的に並べて格納する索引。行の並びは1通りしかないので、1つの表に1つしか作れない。キーの範囲を指定した検索や並び替えでは連続したページを読めばよいので速いが、キーの途中への挿入や更新では行の移動が起きやすい。

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

列の値ごとに、各行がその値を持つかを1ビットで表したビット列（ビットマップ）を持つ索引。性別や地域のように値の種類が少ない（カーディナリティが低い）列に向き、複数の条件のAND・ORをビット演算で高速に求められる。更新のたびにビットマップを書き換える負荷が大きいので、更新の少ないデータウェアハウスで使われる。