データベースの分野において、索引（さくいん）またはインデックス (英: 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木よりも効率が良く、パフォーマンスが大幅に向上する。

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