索引 (データベース)
データベースの分野において、索引（さくいん）またはインデックス (英: 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 のインデックス構成表。
- Microsoft SQL Server のクラスタ化インデックス。
- MySQL InnoDB では強制的に主キーがクラスタ化インデックスになる。
- PostgreSQL では CLUSTER コマンドにより類似の効果を得られる。
Microsoft SQL Serverでは、クラスタ化インデックスの木構造は実際のデータに対応し、非クラスタ化インデックスの場合のように他の場所にあるデータへのポインターではない[3]。 各リレーションは、クラスタ化インデックスを1つと非クラスタ化インデックスを複数持つことができる[4]。
クラスタ
[編集]複数のデータベースと複数のテーブルが結合される場合、それはクラスタと呼ばれる。（前述のクラスタ化インデックスと混同しないこと）クラスタキーの値を共有するテーブルのレコードは、同じまたは近くのデータブロックに一緒に保存されるものとする。これにより、一致するレコードが一緒に保存され、それらを見つけるために必要なI/Oが少なくなるため、クラスタキーでのこれらのテーブルの結合時の速度が改善される[5]。 クラスタ構成は、クラスタの一部であるテーブルのデータレイアウトを定義する。クラスタはB木インデックスまたはハッシュテーブルを使用してキーを設定する。テーブルレコードが格納されるデータブロックは、クラスタキーの値によって定義される。
列の順序
[編集]インデックス定義が列を定義する順序は重要である。最初のインデックス付き列のみを使用して、行識別子のセットを取得できるが、ほとんどのデータベースでは2番目以降のインデックス付き列のみを使用して行識別子のセットを取得することは不可能または効率が落ちてしまう。
たとえば、特定の都市で、最初に都市、次に姓、次に名で編成された電話帳では、すべての電話番号の一覧を簡単に抽出できる。ただし、特定の姓のすべての電話番号を見つけるのは非常に面倒である。各都市のセクション内で、特定の姓を持つ項目を探す必要があるためだ。データベースによっては可能なものもあれば、インデックスを使用しないデータベースもある。
(city, last_name, first_name )に複合インデックスが作成された電話帳の例では、3つのフィールドすべてに正確な値を指定して検索すると、検索時間は最小限になるが、 cityとfirst_name値のみを指定した場合、検索では、 cityフィールドのみを使用して、一致するすべてのレコードを取得する。線形検索では次に、first_nameとの一致をチェックする。したがって、検索効率を向上させるには、検索列の順序でインデックスが作成されるようにする必要がある。
応用例と制限事項
[編集]インデックスは多くの応用例に役立つが、いくつかの制限事項がある。次のSQLステートメントについて考えてみよう。
SELECT first_name FROM people WHERE last_name = 'Smith';
インデックスなしでこのステートメントを処理するには、データベースソフトウェアは、テーブルのすべての行のlast_name列を確認する必要がある（全表スキャンと呼ばれる）。インデックスを使う場合、データベースは、項目にSmithが見つかるまで、インデックスデータ構造（通常はB木）に従って検索する。この方法は、全表スキャンよりもはるかに計算コストが低くなる。
次のSQLステートメントについて考えてみよう。
SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';
このクエリにより、電子メールアドレスが「@wikipedia.org」で終わるすべての顧客の電子メールアドレスが返されるが、email_address列にインデックスが付けられている場合でも、データベースは完全なインデックススキャンを実行する必要がある。これは、単語が左から右に移動することを前提としてインデックスが作成されているからである。検索語の先頭にワイルドカードが付いていると、データベースソフトウェアはインデックスデータ構造を活用できない（つまり、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)かかる順次検索が行われる。
リレーショナルデータベースの機能
[編集]式インデックス
[編集]式インデックス (関数インデックス、英: expression index) とは、関数や式に基づいたインデックスである。
例えば、関数 upper(last_name) に基づいて作成したインデックスを使って、列 last_name を大文字小文字を区別せずにデータを検索することができる (大文字に変換された値がインデックスに格納されているため、検索キーは大文字で与える)。
部分インデックス
[編集]部分インデックス (条件付きインデックス、英: partial index) とは、与えられた条件で行をフィルタし、条件を満たす行のみをインデックスの対象とする。
密インデックス
[編集]密インデックス (英: dense index) は、データファイル内のすべてのレコードへのキーとポインタのペアを持つファイルのこと。このファイルのすべてのキーは、ソートされたデータファイルのレコードへの特定のポインタに関連付けられている。キーが重複しているクラスタ化インデックスでは、密インデックスはそのキーを持つ最初のレコードを指す[6]。
疎インデックス
[編集]疎インデックス (英: sparse index) は、データファイル内のすべてのブロックへのキーとポインタのペアを持つファイルのこと。このファイルのすべてのキーは、ソートされたデータファイルのブロックへの特定のポインタに関連付けられている。キーが重複しているクラスタ化インデックスでは、疎インデックスは各ブロックの最下位の検索キーを指す。
リバースキーインデックス
[編集]リバースキーインデックス (英: reverse-key index)は、インデックスに入力する前にキー値を逆にする。たとえば、値24538はインデックスで83542になる。キー値を逆にすることは、新しいキー値が単調に増加するシーケンス番号などのデータのインデックス作成に特に役立つ。
プライマリインデックス
[編集]プライマリインデックスには、テーブルのキーフィールドとテーブルの非キーフィールドへのポインタが含まれる。プライマリインデックスは、データベースにテーブルが作成されるときに自動的に作成される。
セカンダリインデックス
[編集]これは、順序フィールドでもキーフィールドでもないフィールドにインデックスを付けるために使用される（ファイルがキーフィールドまたは主キーフィールドで編成されているという保証はない）。データファイル（密インデックス）内のタプルごとに1つのインデックスエントリには、インデックス付き属性の値とブロックまたはレコードへのポインタが含まれる。
カバリングインデックス
[編集]カバリングインデックスはインデックス中にキーではない列を含める方式である。インデックスは通常はデータレコードを素早く見つける目的で利用されるが、検索クエリに対する返り値の作成には利用されない。しかし、もしインデックスを使う検索が、行全体ではなく、キーと幾つかの列のみを必要とする場合、その必要とされる列がインデックスのデータ構造内にあれば、検索はインデックス内で完結できる。テーブルからデータを読み取る必要が無いため効率が良い。
例として次のテーブルで説明する。
| ID | 名前 | その他の分野 |
|---|---|---|
| 12 | プラグ | ... |
| 13 | ランプ | ... |
| 14 | ヒューズ | ... |
ID 13の名前を見つけるには、（ID）のインデックスを使うことになるが、名前列のデータを取得するには、テーブルのレコードを読み取る必要がある。ここでカバリングインデックスとして（ID、Name）が含まれていれば、別途テーブルのレコードを検索する必要がなくなる。
カバリングインデックスは、特定のテーブルごと向けに作成される。複数のテーブル間でJOIN するクエリでは、関係するテーブルすべてのの複数のインデックスをカバーする必要がある[7]。
カバリングインデックスはテーブルのサイズがメモリに保持しきれないほど大きい場合の検索で検索結果を得る速度を向上させる際にに有効であるが、インデックスのサイズは増加することに注意が必要である。また、キーでない列の値が変更された際にもインデックスを更新する必要があるため、データの挿入や更新の性能は低下する。
物理的実装
[編集]ISO SQL標準はインデックスの物理的な実装方法や作成方法について触れていない。インデックスは、物理的にはストレージ（テーブルスペースまたはファイルグループ）のようなデータベース概念の実装になる。 CREATE INDEX構文を呼び出すことでインデックスは作成される。
インデックスファイル
[編集]インデックスファイルは、特定のキーから任意のレコードにランダムアクセスできるインデックスを格納するコンピュータのファイルのこと。
キーは、レコードを一意に識別できる必要がある。複数のインデックスが存在する場合、他のインデックスは代替インデックスと呼ばれる。インデックスはシステムが作成したファイルに格納され、維持される。
IBMは、OS/360以降でインデックス付き順次アクセス方式 (ISAM)でインデックスファイルを使っている。IBM仮想ストレージオペレーティングシステムは、より多くのオプションを備えたキーシーケンスデータセット（KSDS）としてインデックスファイルを使うVSAMをサポートした。
OpenVMSなどのDECのオペレーティングシステムは、レコード管理サービス (RMS) でインデックスファイルの読み書きをサポートする。
インデックスファイルは、COBOL言語[8]やPL/I[9]にでも利用される。 C言語などのI/O機能が制限されている他の言語は、C-ISAMなどのランタイムライブラリのアドオンパッケージでインデックスファイルを使う[10]。
COBOL言語は、FILE CONTROLセクションの 次のコマンドでインデックスファイルをサポートする。
ORGANIZATION IS INDEXED
IBM PL/Iは、ファイル属性のENVIRONMENT(INDEXED)かENVIRONMENT(VSAM)で、インデックスファイルを宣言する。
最近のシステムでは、インデックスファイルの代わりにリレーショナルデータベースがよく使用される。
インデックスの同時実行制御
[編集]インデックスは通常、複数のトランザクションとプロセスによって同時にアクセスされるため、同時実行制御が必要となる。原則として、インデックスへのアクセスには一般的なデータベースの同時実行制御方法が用いられるが、インデックス用の特殊な方法と一般的な方法と組み合わせることで、パフォーマンスが大幅に向上する。
関連項目
[編集]出典
[編集]- ^ PostgreSQL 9.1.2 Documentation: CREATE TABLE
- ^ Gavin Powell (2006). Chapter 8: Building Fast-Performing Database Models. Wrox Publishing. ISBN 978-0-7645-7490-0
- ^ “Clustered Index Structures”. SQL Server 2005 Books Online (September 2007). マイクロソフト. 2021年3月17日閲覧。
- ^ Daren Bieniek (January 2006). “Chapter 4: Creating Indices”. SQL Server 2005 Implementation and Management. Microsoft Press. 2007年1月2日時点のオリジナルよりアーカイブ。2021年3月17日閲覧。
- ^ Overview of Clusters Oracle® Database Concepts 10g Release 1 (10.1)
- ^ Database Systems: The Complete Book. Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer D. Widom
- ^ Covering Indexes for Query Optimization
- ^ 1 VS COBOL II Application Programming Language Reference, Release 4, Eighth Edition (March 1993), IBM Corporation, Department J58, Copyright International Business Machines Corporation 1984, 1993. pp. 67-73
- ^ IBM Corporation (2012). Enterprise PL/I for z/OS, Version 4.3, Language Reference. p. 276 Nov 25, 2015閲覧。
- ^ “Informix C-ISAM”. Nov 25, 2015閲覧。
| 概念 | |
|---|---|
| オブジェクト | |
| SQL | |
| 構成要素 | |
 カテゴリ | |