データベースのインデックスはどのように機能しますか? [closed] 質問する

なぜそれが必要なのでしょうか?

ディスクベースのストレージ デバイスにデータを保存する場合、データはデータ ブロックとして保存されます。これらのブロックは全体としてアクセスされるため、アトミック ディスク アクセス操作になります。ディスク ブロックはリンク リストとほぼ同じように構成されています。どちらもデータ用のセクションと、次のノード (またはブロック) の場所へのポインターを含み、どちらも連続して保存する必要はありません。

多数のレコードを 1 つのフィールドでのみソートできるため、ソートされていないフィールドを検索するには、(N+1)/2ブロック アクセス (平均) を必要とする線形検索が必要であると言えます。ここNで、 はテーブルがまたがるブロックの数です。そのフィールドが非キー フィールド (つまり、一意のエントリが含まれていない) の場合、Nブロック アクセスでテーブル領域全体を検索する必要があります。

一方、ソートされたフィールドでは、ブロック アクセスを行うバイナリ検索を使用できますlog2 N。また、キーのないフィールドではデータがソートされるため、より高い値が見つかったら、テーブルの残りの部分で重複値を検索する必要はありません。そのため、パフォーマンスが大幅に向上します。

インデックスとは何ですか?

インデックスは、複数のフィールドで多数のレコードをソートする方法です。テーブル内のフィールドにインデックスを作成すると、フィールド値と、それに関連するレコードへのポインターを保持する別のデータ構造が作成されます。その後、このインデックス構造がソートされ、バイナリ検索を実行できるようになります。

インデックス作成の欠点は、これらのインデックスが MyISAM エンジンを使用してテーブルにまとめて保存されるため、同じテーブル内の多くのフィールドにインデックスが付けられると、このファイルが基盤となるファイル システムのサイズ制限にすぐに達してしまう可能性があることです。

どのように機能しますか?

まず、サンプルのデータベース テーブル スキーマの概要を説明します。

フィールド名 データ型 ディスク上のサイズ
id (主キー) 符号なしINT 4バイト
firstName Char(50) 50バイト
lastName Char(50) 50バイト
emailAddress Char(100) 100バイト

注: ディスク上の正確なサイズ値を可能にするために、varchar の代わりに char が使用されました。このサンプル データベースには 500 万行が含まれており、インデックスは作成されていません。ここで、いくつかのクエリのパフォーマンスを分析します。これらは、id (ソートされたキー フィールド) を使用するクエリとfirstName (キーのないソートされていないフィールド) を使用するクエリです。

例 1 -ソートされたフィールドとソートされていないフィールド

固定サイズのレコードのサンプル データベースでは、r = 5,000,000レコード長はR = 204バイトで、MyISAM エンジンを使用してテーブルに格納されます。このエンジンでは、デフォルトのブロック サイズB = 1,024バイトが使用されています。テーブルのブロック係数は、bfr = (B/R) = 1024/204 = 5ディスク ブロックあたりのレコード数です。テーブルを保持するために必要なブロックの総数は、N = (r/bfr) = 5000000/5 = 1,000,000ブロックです。

id フィールドがキー フィールドである場合、id フィールドの線形検索では、N/2 = 500,000値を見つけるためにブロック アクセスの平均が必要になります。ただし、id フィールドもソートされているため、log2 1000000 = 19.93 = 20ブロック アクセスの平均を必要とするバイナリ検索を実行できます。これは劇的な改善であることがすぐにわかります。

現在、firstNameフィールドはソートされておらず、キー フィールドでもないため、バイナリ検索は不可能であり、値も一意ではないため、正確なブロック アクセスを見つけるためにテーブルの最後まで検索する必要がありますN = 1,000,000。インデックス作成の目的は、この状況を修正することです。

インデックス レコードにはインデックス フィールドと元のレコードへのポインターのみが含まれているため、インデックス レコードが指すマルチフィールド レコードよりも小さくなるのは当然です。そのため、インデックス自体に必要なディスク ブロックは元のテーブルよりも少なくなり、反復処理に必要なブロック アクセスも少なくなります。firstName フィールドのインデックスのスキーマの概要を以下に示します。

フィールド名 データ型 ディスク上のサイズ
firstName Char(50) 50バイト
(レコードポインタ) 特別な4バイト

注: MySQL のポインターの長さは、テーブルのサイズに応じて 2、3、4、または 5 バイトになります。

例 2 -インデックス作成

r = 5,000,000インデックス レコード長がR = 54バイトで、デフォルトのブロック サイズが バイトであるレコードのサンプル データベースがあるとしますB = 1,024。インデックスのブロッキング係数は、bfr = (B/R) = 1024/54 = 18ディスク ブロックあたりのレコード数になります。インデックスを保持するために必要なブロックの合計数はN = (r/bfr) = 5000000/18 = 277,778ブロックです。

これで、 firstNameフィールドを使用した検索でインデックスを利用してパフォーマンスを向上できます。これにより、平均log2 277778 = 18.08 = 19ブロック アクセスでインデックスのバイナリ検索が可能になります。実際のレコードのアドレスを見つけるには、さらに読み取り用のブロック アクセスが必要で、合計ブロック アクセスは になります。これは、インデックスのないテーブルでfirstName の一致19 + 1 = 20を見つけるために必要な 1,000,000 ブロック アクセスとは大きく異なります。

いつ使用すればよいですか?

インデックスを作成するには追加のディスク領域が必要であり (上記の例から 277,778 ブロック追加され、約 28% 増加)、インデックスが多すぎるとファイル システムのサイズ制限から生じる問題が発生する可能性があるため、インデックスを作成する適切なフィールドを選択するには慎重に検討する必要があります。

インデックスはレコード内の一致するフィールドの検索を高速化するためにのみ使用されるため、出力のみに使用されるフィールドにインデックスを付けると、挿入または削除操作を行うときにディスク領域と処理時間が無駄になるだけなので、避けるべきです。また、バイナリ検索の性質を考えると、データのカーディナリティまたは一意性が重要です。カーディナリティが 2 のフィールドにインデックスを付けると、データが半分に分割されますが、カーディナリティが 1,000 の場合は約 1,000 件のレコードが返されます。カーディナリティがこのように低いと、効果は線形ソートにまで低下し、カーディナリティがレコード数の 30% 未満の場合、クエリ オプティマイザーはインデックスの使用を避けるため、事実上インデックスは領域の無駄になります。