データベースの分野において、索引（さくいん）またはインデックス (英: index) 、データベースインデックス (英: database index) は、テーブルへの処理を高速化するためのデータ構造である。インデックスの作成には追加の書き込み操作とストレージ容量を必要とする。

インデックスは、データベーステーブルにアクセスするたびにデータベーステーブルのすべての行を検索しなくても、データをすばやく見つけるために使用される。インデックスは、データベーステーブルの1つ以上の列を使用して作成し、高速なランダムルックアップと順序付けられたレコードへの効率的なアクセスの両方の基礎を提供する。
概要

インデックスはテーブルの中の1個以上の列を対象に作成され、ランダムな参照処理や一定の順序でのレコードへのアクセスの効率を高めることができる。インデックスには通常、行全体を効率的に取得できるように、コピー元のデータの元の行への「キー」または直接リンクを含む。

データベースによっては、インデックス作成機能を拡張し、開発者が関数や式による計算列の値にインデックスを作成する式インデックスという仕組みを採用している。 upper(last_name)にインデックスを作成するlast_nameフィールドの大文字バージョンのみがインデックスに格納される。ユーザー定義関数、組み込み関数による計算列の値にインデックスを作成できるシステムもある。他にも、何らかの条件式を満たす一部のレコードに対してのみインデックスを作成する部分インデックスという仕組みがある。

インデックスにはテーブルの中のキー列のみが含まれるが、テーブルにはキー列以外のデータも含むため、一般に、インデックスが占めるストレージ容量は対象となるテーブルよりも少ない。そのため、全体をメモリ上に保持しきれないほど大きなテーブルであっても、そのインデックスであればメモリに保持できる可能性がある。
使用法
高速検索のサポート

大規模なデータベースでは線型検索 (liner search)が非効率的であるため、ほとんどのデータベースソフトウェアでは、劣線形時間検索 (sub-linear time lookup)を使ってパフォーマンス向上ができるようにインデックスが作成される。

データベースにN個のデータ項目があって、フィールドのどれか1つの値からデータ項目の1つを取得することを考える。単純な実装では、各項目を取得して調べていく。一致する項目が1つだけとわかっている場合は、その項目が最初に見つかった時点で停止できるが、複数項目ある可能性がある場合は、全項目を検査する必要がある。これは、平均的な場合の操作数がO(N)または線形時間であることを意味する。データベースには多くのオブジェクトが含まれ、検索は一般的な操作であるため、検索アルゴリズムの効率向上はとても重要である。

インデックスは、検索効率を向上させるためのデータ構造である。この目的で使用されるさまざまなデータ構造がある。各データ構造には、検索効率、インデックスサイズ、インデックス更新効率のどれを優先させるかにより複雑な設計上のトレードオフがある。多くのインデックスデザインでは計算時間が対数 (O(log(N)))の検索効率を示し、一部のアプリケーションでは計算時間がフラット (O(1))の検索効率の達成が可能である。
データベース制約の維持

インデックスは、UNIQUE (一意性制約)、EXCLUSION (排他制約)、PRIMARY KEY (主キー制約)、FOREIGN KEY (外部キー制約) などのデータベース制約の維持にも使用される。一意インデックスでは重複したエントリが登録されるのを禁止するため、そのインデックスの対象であるテーブルでも一意性が保障される。データベースシステムは通常、PRIMARY KEYと宣言された一連の列に暗黙的にインデックスを作成し、既存のインデックスを使用してこの制約を監視できるものもある。多くのデータベースシステムでは、FOREIGN KEY制約内の参照元と参照先の列の両方にインデックスを付けるため、制約がかかっているテーブルの挿入、更新、および削除のパフォーマンスが向上する。

一部のデータベースシステムは、新しく挿入または更新されたレコードに対して、特定の述部が他のレコードに対して保持されないことを保証するEXCLUSION制約をサポートする。これを使用して、UNIQUE制約（等式述語を使用）またはより複雑な制約を実装できる。たとえば、重複する時間範囲や交差するジオメトリオブジェクトがテーブルに格納されないようにすることができる。このような制約を監視するには、述語を満たすレコードの高速検索をサポートするインデックスが必要となる[1]。
インデックスに用いるデータ構造別方式

インデックスは、さまざまなデータ構造を使って実装される。よく使われる方式には、平衡二分探索木、B+木、ハッシュなどがある[2]。検索の要件により必要なインデックス構造は異なるため、異なる構造を持つ複数のインデックスを提供するデータベース製品も存在する。
B木インデックス

多くのデータベースは、インデックスに B木 (または B+木, B*木) 構造を採用している。B木は範囲検索にも利用できる。

B木を使ったインデックスでは、インデックス定義の際の順序が重要である。最初の列のみを条件とした検索であればインデックスは利用できるが、2番目以降の列を指定するだけではインデックスは利用できない。

インデックスのキーを (住所, 苗字, 名前) とする電話帳データベースを例に挙げると、住所が与えられればこのインデックスを使った検索ができるが、苗字だけではできない。
ハッシュインデックス

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

B+木など、最も一般的に使用されるインデックスは、インデックスを作成する値が繰り返されないか、数回繰り返されない場合に最も効率的である。対照的に、ビットマップインデックス (英: bitmap index) はキーの濃度 (カーディナリティ、cardinality) が低い場合に適したインデックスである。つまり、変数の値が非常に頻繁に繰り返される場合である。

例えば、「性別」を表す列 (「男性」または「女性」の値のみを含む) に対してインデックスを作成する場合には、B木よりも効率が良く、パフォーマンスが大幅に向上する。

それぞれのキー値ごとにビットマップ (ビット配列) を作成し、その各ビットはレコードがキーを含んでいるかを表す。これらのビットマップに対してビット演算を行うことによりクエリに応答する。
多次元インデックス

B木に基づくインデックスはキーがスカラー[要曖昧さ回避]値である場合にのみ適用できる。GIS (地理空間情報) データ型等の多次元空間上での位置や広がりを持つデータに対しては、kd木や汎用検索ツリーを用いた多次元インデックスが利用される。
転置インデックス詳細は「転置インデックス」を参照

一般的なインデックスは、1つの行は1つのキーのみを持つことを前提としている。一方、配列の各要素を検索する場合や、文書を全文検索する場合には、1つの行から複数のキーが抽出されうる。これらのデータに対しては転置インデックス (英: inversed index)が利用される。
アーキテクチャと作成方法
非クラスタ化インデックス

データは任意の順序で存在するが、論理的順序はインデックスによって指定される。データ行は、インデックス付きの列または式の値に関係なく、テーブル全体に分散される場合がある。非クラスタ化インデックス (英: non-clustered index) ツリーには、ソートされた順序でインデックスキーが含まれ、インデックスの木構造には、レコードへのポインタが含まれる。これは、ページ編成エンジンでは、データページのページと行番号にあたり、ファイル編成エンジンでは行オフセットにあたる情報である。

非クラスタ化インデックスでは、

行の物理的な順序は、インデックスの順序と同じではない。

インデックス付き列は通常、JOIN、WHERE、およびORDERBY句で使用される非主キー列である。

データベーステーブルには、非クラスタ化インデックスが複数存在する場合がある。
クラスタ化インデックス

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

一方、クラスタ化インデックス (英: clustered index) では、データブロックをインデックスの順序で並べ替えて保持し、行データが順番に格納される。これは、頭文字で項目をソートしてあるアドレス帳に似ている。クラスタ化インデックスのキーで範囲検索を行う場合、条件に適合する行が連続して配置されるため全体的な取得速度を大幅に向上させることができる。ただし速度が向上するのは、クラスタ化インデックスと同じまたは逆の順序でデータに順次アクセスする場合、またはアイテムの範囲が選択されている場合に限る。

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

物理レコードはディスク上でこのソート順であるため、シーケンスの次の行項目は最後の行項目の直前または直後にあり、必要なデータブロックの読み取りは少なくなる。したがって、クラスタ化インデックスの主な機能は、物理データ行を指すインデックスブロックに従い物理データ行の順序を並び替えることである。データベースによっては、データブロックとインデックスブロックを別々のファイルに分割する場合もあれば、2つの完全に異なるデータブロックを同じ物理ファイル内に配置する場合もある。

以下に、クラスタ化インデックスを提供するデータベース製品の例を挙げる：

Oracle Database のインデックス構成表。