索引 (データベース)
インデックス定義が列を定義する順序は重要である。最初のインデックス付き列のみを使用して、行識別子のセットを取得できるが、ほとんどのデータベースでは2番目以降のインデックス付き列のみを使用して行識別子のセットを取得することは不可能または効率が落ちてしまう。
たとえば、特定の都市で、最初に都市、次に姓、次に名で編成された電話帳では、すべての電話番号の一覧を簡単に抽出できる。ただし、特定の姓のすべての電話番号を見つけるのは非常に面倒である。各都市のセクション内で、特定の姓を持つ項目を探す必要があるためだ。データベースによっては可能なものもあれば、インデックスを使用しないデータベースもある。
(city, last_name, first_name )に複合インデックスが作成された電話帳の例では、3つのフィールドすべてに正確な値を指定して検索すると、検索時間は最小限になるが、 cityとfirst_name値のみを指定した場合、検索では、 cityフィールドのみを使用して、一致するすべてのレコードを取得する。線形検索では次に、first_nameとの一致をチェックする。したがって、検索効率を向上させるには、検索列の順序でインデックスが作成されるようにする必要がある。
インデックスファイルは、特定のキーから任意のレコードにランダムアクセスできるインデックスを格納するコンピュータのファイルのこと。
キーは、レコードを一意に識別できる必要がある。複数のインデックスが存在する場合、他のインデックスは代替インデックスと呼ばれる。インデックスはシステムが作成したファイルに格納され、維持される。
IBMは、OS/360以降でインデックス付き順次アクセス方式 (ISAM)でインデックスファイルを使っている。IBM仮想ストレージオペレーティングシステムは、より多くのオプションを備えたキーシーケンスデータセット(KSDS)としてインデックスファイルを使うVSAMをサポートした。
OpenVMSなどのDECのオペレーティングシステムは、レコード管理サービス (RMS) でインデックスファイルの読み書きをサポートする。
インデックスファイルは、COBOL言語やPL/Iにでも利用される。 C言語などのI/O機能が制限されている他の言語は、C-ISAMなどのランタイムライブラリのアドオンパッケージでインデックスファイルを使う。
COBOL言語は、FILE CONTROLセクションの 次のコマンドでインデックスファイルをサポートする。
IBM PL/Iは、ファイル属性のENVIRONMENT(INDEXED)かENVIRONMENT(VSAM)で、インデックスファイルを宣言する。
最近のシステムでは、インデックスファイルの代わりにリレーショナルデータベースがよく使用される。
カバリングインデックスはインデックス中にキーではない列を含める方式である。インデックスは通常はデータレコードを素早く見つける目的で利用されるが、検索クエリに対する返り値の作成には利用されない。しかし、もしインデックスを使う検索が、行全体ではなく、キーと幾つかの列のみを必要とする場合、その必要とされる列がインデックスのデータ構造内にあれば、検索はインデックス内で完結できる。テーブルからデータを読み取る必要が無いため効率が良い。
例として次のテーブルで説明する。
ID 13の名前を見つけるには、(ID)のインデックスを使うことになるが、名前列のデータを取得するには、テーブルのレコードを読み取る必要がある。ここでカバリングインデックスとして(ID、Name)が含まれていれば、別途テーブルのレコードを検索する必要がなくなる。
カバリングインデックスは、特定のテーブルごと向けに作成される。複数のテーブル間でJOIN するクエリでは、関係するテーブルすべてのの複数のインデックスをカバーする必要がある。
カバリングインデックスはテーブルのサイズがメモリに保持しきれないほど大きい場合の検索で検索結果を得る速度を向上させる際にに有効であるが、インデックスのサイズは増加することに注意が必要である。また、キーでない列の値が変更された際にもインデックスを更新する必要があるため、データの挿入や更新の性能は低下する。
複数のデータベースと複数のテーブルが結合される場合、それはクラスタと呼ばれる。(前述のクラスタ化インデックスと混同しないこと)クラスタキーの値を共有するテーブルのレコードは、同じまたは近くのデータブロックに一緒に保存されるものとする。これにより、一致するレコードが一緒に保存され、それらを見つけるために必要なI/Oが少なくなるため、クラスタキーでのこれらのテーブルの結合時の速度が改善される。 クラスタ構成は、クラスタの一部であるテーブルのデータレイアウトを定義する。クラスタはB木インデックスまたはハッシュテーブルを使用してキーを設定する。テーブルレコードが格納されるデータブロックは、クラスタキーの値によって定義される。
これは、単語が左から右に移動することを前提としてインデックスが作成されているからである。検索語の先頭にワイルドカードが付いていると、データベースソフトウェアはインデックスデータ構造を活用できない(つまり、WHERE句は検索引数可能 (SARGable)ではない)。この問題は reverse(email_address)を元に作成した別のインデックスと次のようなSQLクエリで解決できる。
SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');
。これにより、クエリの右端の部分(現在はgro.aidepikiw @%)にワイルドカードが配置され、reverse(email_address)のインデックスを活用できる。
検索ワードの両側で%wikipedia.org%のようにワイルドカード文字が使われている場合、このフィールドでインデックスは活用できない。計算時間がO(N)かかる順次検索が行われる。