(Wikipedia 索引 (データベース)より)

索引（さくいん）またはインデックス (index) は、表への処理を高速化するためのデータ構造である。索引は表の中の1個以上の列を対象に作成され、ランダムな参照処理や一定の順序でのレコードへのアクセスの効率を高めることができる。索引には表の中のキー列のみが含まれるが、表にはキー列以外のデータも含むため、一般に、索引が占めるディスク容量は対象となる表よりも少ない。そのため、全体をメモリ上に保持しきれないほど大きな表であっても、その索引であればメモリに保持できる可能性がある。

索引は一意性制約を実現するためにも使用される。ユニーク索引では重複したエントリが登録されるのを禁止するため、その索引の対象である表でも一意性が保障される。

構造

検索の条件により必要な索引構造は異なるため、異なる構造を持つ複数の索引を提供するデータベース製品も存在する。

B木

多くのデータベースは、索引に B木 (または B+木, B*木) 構造を採用している。B木は範囲検索にも利用できる。B木を使った索引では、索引定義の際の順序が重要である。最初の列のみを条件とした検索であれば索引は利用できるが、2番目以降の列を指定するだけでは索引は利用できない。索引のキーを (住所, 苗字, 名前) とする電話帳データベースを例に挙げると、住所が与えられればこの索引を使った検索ができるが、苗字だけではできない。

ハッシュ索引

ハッシュ関数に基づく索引は、一般にB木よりも性能面およびサイズ面で有利であるが、範囲検索はできず、完全一致検索にのみ利用できる。

ビットマップ索引

ビットマップ索引はキーの濃度 (カーディナリティ; cardinality) が低い場合に適した索引である。例えば、「性別」を表す列 (「男性」または「女性」の値のみを含む) に対して索引を作成する場合には、B木よりも効率が良い。ビットマップ索引は、それぞれのキー値ごとにビットマップ (ビットの配列) を作成し、その各ビットはレコードがキーを含んでいるかを表す。また、ビット演算を行うことにより複数のビットマップ索引を同時に利用することもできる。

多次元索引

B木に基づく索引はキーがスカラー値である場合にのみ適用できる。GIS (地理空間情報) データ型等の多次元空間上での位置や広がりを持つデータに対しては、kd木や汎用検索ツリーを用いた多次元索引が利用される。

転置インデックス

一般的な索引は、1つの行は1つのキーのみを持つことを前提としている。一方、配列の各要素を検索する場合や、文書を全文検索する場合には、1つの行から複数のキーが抽出されうる。これらのデータに対しては転置インデックスが利用される。

実装

データベース製品によっては、以下のような機能を提供しているものもある：

式インデックス

式インデックス (関数インデックス) とは、関数や式に基づいた索引である。例えば、関数

upper(last_name)

に基づいて作成した索引を使って、列 last_name を大文字小文字を区別せずにデータを検索することができる (大文字に変換された値が索引に格納されているため、検索キーは大文字で与える)。

部分インデックス

部分インデックス (条件付きインデックス) とは、与えられた条件で行をフィルタし、条件を満たす行のみを索引の対象とする。

クラスタ索引

多くの索引は、書籍の索引と同様、実際のデータレコードの並び順とは無関係に構築される。そのため、範囲検索を行う場合、その対象のレコードは表内の複数個所に分散している可能性がある。分散したレコードにアクセスが必要なため、複数回のランダム I/O が発生してしまう。

一方、クラスタ索引 (clustered index) では、元のデータ自体を索引の順序で並び替えて保持する。これは、頭文字で項目をソートしてあるアドレス帳に似ている。クラスタ索引のキーで範囲検索を行う場合、条件に適合する行が連続して配置されるためアクセスの効率が高い。

表がクラスタキー以外の属性を持っていても、クラスタキーでソートする必要があるため、一般的には表には 1個のクラスタ索引のみを設定できる。ただし、データベース製品によっては複数のクラスタ索引を設定でき、多次元クラスタを提供するものもある。

以下に、クラスタ索引を提供するデータベース製品の例を挙げる：

• Oracle Database の索引構成表。
• Microsoft SQL Server のクラスタ化されたインデックス。
• MySQL InnoDB では強制的に主キーがクラスタ索引になる。
• PostgreSQL では CLUSTER コマンドにより類似の効果を得られる。

Covering index

Covering index は索引中にキーではない列を含める方式である。もし索引を使う検索が、行全体ではなく、キーと幾つかの列のみを必要とする場合、その必要とされる列が索引のデータ構造内にあれば、検索は索引内で完結できる。表からデータを読み取る必要が無いため効率が良い。

Covering index は表のサイズがメモリに保持しきれないほど大きい場合の検索で有効であるが、索引のサイズは増加することに注意が必要である。また、キーでない列の値が変更された際にも索引を更新する必要があるため、更新の性能は低下する傾向がある。