データベースインデックス

データベースインデックスは、インデックス データ構造を維持するための追加の書き込みとストレージ スペースを犠牲にして、データベース テーブルでのデータ取得操作の速度を向上させるデータ構造です。インデックスを使用すると、データベース テーブルにアクセスするたびにそのテーブル内のすべての行を検索することなく、データをすばやく見つけることができます。インデックスは、データベース テーブルの 1 つ以上の列を使用して作成でき、高速なランダム検索と順序付けられたレコードへの効率的なアクセス の両方の基盤となります。

インデックスは、テーブルから選択されたデータ列のコピーであり、非常に効率的な検索を可能にするように設計されています。インデックスには通常、コピー元のデータ行への「キー」または直接リンクが含まれており、行全体を効率的に取得できます。一部のデータベースでは、関数または式によって変換された列値に開発者がインデックスを作成できるようにすることで、インデックスの機能を拡張しています。たとえば、 にインデックスを作成してupper(last_name)、フィールドの大文字バージョンのみをインデックスに格納できます。サポートされている可能性のある別のオプションは、部分インデックスlast_nameの使用です。部分インデックスでは、条件式を満たすレコードに対してのみインデックス エントリが作成されます。柔軟性のさらなる側面は、ユーザー定義関数や、さまざまな組み込み関数から形成された式 にインデックスを作成できることです。

ほとんどのデータベースソフトウェアには、線形検索は大規模なデータベースでは非効率であるため、パフォーマンスを向上させるために線形時間未満での 検索を可能にするインデックス作成テクノロジが含まれています。

データベースに N 個のデータ項目が含まれており、フィールドの 1 つの値に基づいて 1 つを取得する必要があるとします。単純な実装では、テストに従って各項目を取得して検査します。一致する項目が 1 つしかない場合は、その項目が見つかった時点で停止できますが、一致する項目が複数ある場合は、すべてをテストする必要があります。つまり、平均的な場合の操作数はO (N) または線形時間です。データベースには多くのオブジェクトが含まれている可能性があり、検索は一般的な操作であるため、パフォーマンスを向上させることが望ましいことがよくあります。

インデックスとは、検索のパフォーマンスを向上させるデータ構造のことです。この目的で使用されるデータ構造は多種多様です。検索パフォーマンス、インデックス サイズ、インデックス更新パフォーマンスなど、設計上のトレードオフは複雑です。多くのインデックス設計では、対数 ( O (log(N))) の検索パフォーマンスが示され、アプリケーションによっては、フラット ( O (1)) のパフォーマンス を実現できます。

インデックスは、UNIQUE、EXCLUSION、 PRIMARY KEY、FOREIGN KEYなどのデータベース制約を監視するために使用されます。インデックスは UNIQUE として宣言することができ、これにより、基になるテーブルに暗黙的な制約が作成されます。データベース システムは通常、PRIMARY KEY として宣言された列セットに暗黙的にインデックスを作成しますが、既存のインデックスを使用してこの制約を監視する機能を持つものもあります。多くのデータベース システムでは、FOREIGN KEY 制約内の参照列セットと参照列セットの両方にインデックスを作成する必要があります。これにより、制約に関係するテーブルへの挿入、更新、削除のパフォーマンスが向上します。

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

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

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

• 行の物理的な順序はインデックスの順序と同じではありません。
• インデックスが付けられた列は通常、JOIN、WHERE、および ORDER BY 句で使用される非主キー列です。

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

クラスタリングは、データ ブロックをインデックスに合わせて特定の順序に変更し、行データが順序どおりに格納されるようにします。したがって、特定のデータベース テーブルには 1 つのクラスター化インデックスのみを作成できます。クラスター化インデックスにより、全体的な取得速度が大幅に向上しますが、通常は、データがクラスター化インデックスと同じ順序または逆の順序で順次アクセスされる場合、または項目の範囲が選択される場合に限られます。

物理レコードはディスク上でこの並び順になっているため、シーケンス内の次の行項目は最後の行項目の直前または直後になり、データ ブロックの読み取り回数が少なくなります。したがって、クラスター化インデックスの主な機能は、物理データ行を、それらを指すインデックス ブロックに従って順序付けることです。一部のデータベースでは、データ ブロックとインデックス ブロックを別々のファイルに分けますが、他のデータベースでは、2 つのまったく異なるデータ ブロックを同じ物理ファイル内に配置します。

複数のデータベースと複数のテーブルが結合されたものをクラスターと呼びます(前述のクラスター化インデックスと混同しないでください)。クラスターキーの値を共有するテーブルのレコードは、同じまたは近くのデータブロックに一緒に格納されます。これにより、一致するレコードが一緒に格納され、それらを見つけるために必要な I/O が少なくなるため、クラスターキーでのこれらのテーブルの結合が改善される可能性があります。^[2]クラスター構成は、クラスターの一部であるテーブルのデータレイアウトを定義します。クラスターは、Bツリーインデックスまたはハッシュテーブルでキー付けできます。テーブルレコードが格納されるデータブロックは、クラスターキーの値によって定義されます。

インデックス定義で列を定義する順序は重要です。最初のインデックス列のみを使用して行識別子のセットを取得することは可能です。ただし、2 番目以降のインデックス列のみを使用して行識別子のセットを取得することは不可能であり、効率的でもありません (ほとんどのデータベースでは)。

たとえば、最初に都市名、次に姓、そして名の順に整理された電話帳では、特定の都市のすべての電話番号のリストを簡単に抽出できます。ただし、特定の姓のすべての電話番号を検索するのは非常に面倒です。各都市のセクション内でその姓のエントリを探す必要があります。一部のデータベースではこれが可能ですが、他のデータベースではインデックスが使用されません。

列 ( ) に複合インデックスが作成された電話帳の例ではcity, last_name, first_name、3 つのフィールドすべてに正確な値を指定して検索すると、検索時間は最小限に抑えられますが、cityと first_nameのみに値を指定すると、検索ではcityフィールドのみを使用して、一致するすべてのレコードが取得されます。次に、順次検索で との一致がチェックされますfirst_name。したがって、パフォーマンスを向上させるには、検索列の順序でインデックスが作成されるようにする必要があります。

インデックスは多くのアプリケーションで役立ちますが、いくつかの制限があります。次のSQL文を考えてみましょう。インデックスなしでこの文を処理するには、データベース ソフトウェアはテーブル内のすべての行の last_name 列を調べる必要があります (これはフル テーブル スキャンと呼ばれます)。インデックスを使用すると、データベースは Smith エントリが見つかるまでインデックス データ構造 (通常はB ツリー) をたどるだけです。これはフル テーブル スキャンよりも計算コストがはるかに低くなります。 SELECT first_name FROM people WHERE last_name = 'Smith';

次の SQL 文を考えてみましょう: 。このクエリは、電子メール アドレスが "@wikipedia.org" で終わるすべての顧客の電子メール アドレスを返しますが、email_address 列がインデックス化されている場合でも、データベースは完全なインデックス スキャンを実行する必要があります。これは、単語が左から右に進むという前提でインデックスが構築されているためです。検索語の先頭にワイルドカードがあると、データベース ソフトウェアは基礎となるインデックス データ構造を使用できません (つまり、WHERE 句はsargableではありません)。この問題は、 に作成された別のインデックスと次のような SQL クエリを追加することで解決できます: 。これにより、ワイルドカードがクエリの右端に配置されます (これでSELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';reverse(email_address)SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');gro.aidepikiw@%）、reverse(email_address) のインデックスが満たすことができます。

ワイルドカード文字が%wikipedia.org%のように検索語の両側に使用されている場合、このフィールドで使用可能なインデックスは使用されません。代わりに、順次検索のみが実行され、時間が${\displaystyle O(N)}$かかります。

ビットマップ インデックスは特殊な種類のインデックスで、データの大部分をビット配列(ビットマップ) として保存し、これらのビットマップに対してビット単位の論理演算を実行することでほとんどのクエリに応答します。B + ツリーなどの最も一般的に使用されるインデックスは、インデックスの対象となる値が繰り返されないか、繰り返されても回数が少ない場合に最も効率的です。一方、ビットマップ インデックスは、変数の値が非常に頻繁に繰り返される場合を想定して設計されています。たとえば、顧客データベースの性別フィールドには通常、男性、女性、不明 (記録されていない) の 3 つの異なる値しか含まれていません。このような変数の場合、ビットマップ インデックスは、一般的に使用されるツリーよりもパフォーマンス面で大きな利点があります。

データベースの稠密インデックスは、データ ファイル内のすべてのレコードのキーとポインタのペアを持つファイルです。このファイル内のすべてのキーは、ソートされたデータ ファイル内のレコードへの特定のポインタに関連付けられています。重複キーを持つクラスター化インデックスでは、稠密インデックスはそのキーを持つ最初のレコードを指します。^[3]

データベースのスパース インデックスは、データ ファイル内のすべてのブロックのキーとポインターのペアを含むファイルです。このファイル内のすべてのキーは、ソートされたデータ ファイル内のブロックへの特定のポインターに関連付けられています。重複キーを持つクラスター化インデックスでは、スパース インデックスは各ブロック内の最も低い検索キーを指します。

逆キー インデックスは、インデックスに入力する前にキー値を反転します。たとえば、値 24538 はインデックスでは 83542 になります。キー値を反転することは、新しいキー値が単調に増加するシーケンス番号などのデータのインデックス作成に特に役立ちます。

逆インデックスは、コンテンツ ワードをそれを含むドキュメントにマッピングし、全文検索を可能にします。

プライマリ インデックスには、テーブルのキー フィールドと、テーブルの非キー フィールドへのポインターが含まれます。プライマリ インデックスは、データベースにテーブルが作成されるときに自動的に作成されます。

これは、順序付けフィールドでもキー フィールドでもないフィールドのインデックス作成に使用されます (ファイルがキー フィールドまたは主キー フィールドに基づいて編成されているという保証はありません)。データ ファイル内のタプルごとに 1 つのインデックス エントリ (高密度インデックス) には、インデックス付けされた属性の値と、ブロックまたはレコードへのポインターが含まれます。

データベースのハッシュ インデックスは、データ管理で最も一般的に使用されるインデックスです。主キーや電子メール アドレスなどの一意の値を含む列に作成されます。

データベース システムで使用される別の種類のインデックスは線形ハッシュです。

インデックスはさまざまなデータ構造を使用して実装できます。一般的なインデックスには、バランスツリー、B+ツリー、ハッシュなどがあります。^[4]

Microsoft SQL Serverでは、クラスター化インデックスのリーフノードは、非クラスター化インデックスの場合のように、他の場所にあるデータへの単なるポインタではなく、実際のデータに対応しています。 [5]各リレーションには、1つのクラスター化インデックスと多数の非クラスター化インデックスを含めることができます。 [ ^{6 ]}

通常、インデックスは複数のトランザクションやプロセスによって同時にアクセスされるため、同時実行制御が必要です。 原則として、インデックスは一般的なデータベース同時実行制御方法を利用できますが、インデックス専用の同時実行制御方法も存在し、これを一般的な方法と組み合わせて適用することで、大幅なパフォーマンス向上が実現します。

ほとんどの場合、インデックスは、必要なデータを読み取るデータ レコードをすばやく見つけるために使用されます。つまり、インデックスはテーブル内のデータ レコードを見つけるためにのみ使用され、データを返すために使用されるわけではありません。

カバーリング インデックスは、インデックス自体に必要なデータ フィールドが含まれており、必要なデータに回答できる特殊なケースです。

次の表を検討してください (他のフィールドは省略)。

ID 13 の名前を見つけるには、(ID) のインデックスが便利ですが、名前を取得するにはレコードを読み取る必要があります。ただし、(ID、名前) のインデックスには必要なデータ フィールドが含まれているため、レコードを検索する必要がなくなります。

カバーインデックスはそれぞれ特定のテーブル用です。複数のテーブルにまたがってJOIN/アクセスするクエリでは、複数のテーブルをカバーするインデックスを検討する可能性があります。^[7]

カバーリング インデックスはデータ取得を大幅に高速化できますが、追加のキーによりインデックス自体が大きくなり、データの挿入と更新が遅くなる可能性があります。このようなインデックス サイズを削減するために、一部のシステムではインデックスに非キー フィールドを含めることができます。非キー フィールド自体はインデックス順序の一部ではなく、リーフ レベルでのみ含まれるため、カバーリング インデックスの全体的なインデックス サイズが小さくなります。

これはSQLで次のように実行できます。^{[8] [9]}CREATE INDEX my_index ON my_table (id) INCLUDE (name);

ISO SQL 標準では物理的な側面がカバーされていないため、インデックスの作成方法を定義する標準はありません。インデックスは、ストレージ (テーブルスペースまたはファイル グループ) など、データベース概念の物理的な部分の 1 つです。RDBMS ベンダーはすべて、ソフトウェアの機能に応じて特定のオプションを含む構文を提供しています。 CREATE INDEX

• インデックスロック
• 転置インデックス – データベースインデックスの種類
• 検索エンジンのインデックス作成 – データ管理の方法