索引 (データベース)
ISO SQL標準はインデックスの物理的な実装方法や作成方法について触れていない。インデックスは、物理的にはストレージ(テーブルスペースまたはファイルグループ)のようなデータベース概念の実装になる。 CREATE INDEX構文を呼び出すことでインデックスは作成される。
インデックスは、さまざまなデータ構造を使って実装される。よく使われる方式には、平衡二分探索木、B+木、ハッシュなどがある。検索の要件により必要なインデックス構造は異なるため、異なる構造を持つ複数のインデックスを提供するデータベース製品も存在する。
インデックスは通常、複数のトランザクションとプロセスによって同時にアクセスされるため、同時実行制御が必要となる。原則として、インデックスへのアクセスには一般的なデータベースの同時実行制御方法が用いられるが、インデックス用の特殊な方法と一般的な方法と組み合わせることで、パフォーマンスが大幅に向上する。
データは任意の順序で存在するが、論理的順序はインデックスによって指定される。データ行は、インデックス付きの列または式の値に関係なく、テーブル全体に分散される場合がある。非クラスタ化インデックス (英: non-clustered index) ツリーには、ソートされた順序でインデックスキーが含まれ、インデックスの木構造には、レコードへのポインタが含まれる。これは、ページ編成エンジンでは、データページのページと行番号にあたり、ファイル編成エンジンでは行オフセットにあたる情報である。
非クラスタ化インデックスでは、
行の物理的な順序は、インデックスの順序と同じではない。
インデックス付き列は通常、JOIN、WHERE、およびORDERBY句で使用される非主キー列である。
データベーステーブルには、非クラスタ化インデックスが複数存在する場合がある。
疎インデックス (英: sparse index) は、データファイル内のすべてのブロックへのキーとポインタのペアを持つファイルのこと。このファイルのすべてのキーは、ソートされたデータファイルのブロックへの特定のポインタに関連付けられている。キーが重複しているクラスタ化インデックスでは、疎インデックスは各ブロックの最下位の検索キーを指す。