索引 (データベース)
インデックスはテーブルの中の1個以上の列を対象に作成され、ランダムな参照処理や一定の順序でのレコードへのアクセスの効率を高めることができる。インデックスには通常、行全体を効率的に取得できるように、コピー元のデータの元の行への「キー」または直接リンクを含む。
データベースによっては、インデックス作成機能を拡張し、開発者が関数や式による計算列の値にインデックスを作成する式インデックスという仕組みを採用している。 upper(last_name)にインデックスを作成するlast_nameフィールドの大文字バージョンのみがインデックスに格納される。ユーザー定義関数、組み込み関数による計算列の値にインデックスを作成できるシステムもある。他にも、何らかの条件式を満たす一部のレコードに対してのみインデックスを作成する部分インデックスという仕組みがある。
インデックスにはテーブルの中のキー列のみが含まれるが、テーブルにはキー列以外のデータも含むため、一般に、インデックスが占めるストレージ容量は対象となるテーブルよりも少ない。そのため、全体をメモリ上に保持しきれないほど大きなテーブルであっても、そのインデックスであればメモリに保持できる可能性がある。
B+木など、最も一般的に使用されるインデックスは、インデックスを作成する値が繰り返されないか、数回繰り返されない場合に最も効率的である。対照的に、ビットマップインデックス (英: bitmap index) はキーの濃度 (カーディナリティ、cardinality) が低い場合に適したインデックスである。つまり、変数の値が非常に頻繁に繰り返される場合である。
例えば、「性別」を表す列 (「男性」または「女性」の値のみを含む) に対してインデックスを作成する場合には、B木よりも効率が良く、パフォーマンスが大幅に向上する。
それぞれのキー値ごとにビットマップ (ビット配列) を作成し、その各ビットはレコードがキーを含んでいるかを表す。これらのビットマップに対してビット演算を行うことによりクエリに応答する。