[解決済み] データベースのインデックス作成はどのように行われるのですか？[クローズド］

質問

データセットのサイズが大きくなるとインデックス作成が重要になりますが、データベースに依存しないレベルでインデックス作成がどのように機能するのか、どなたか説明していただけますか？

フィールドのインデックスを作成するクエリについては、以下を参照してください。 データベースのカラムにインデックスを付けるには .

どのように解決するのですか？

なぜ必要なのですか？

ディスクベースのストレージデバイスにデータを保存する場合、データはデータのブロックとして保存されます。これらのブロックは全体としてアクセスされるため、アトミックなディスクアクセス操作となる。ディスクブロックはリンクリストとほぼ同じ構造で、どちらもデータ用のセクションと次のノード（ブロック）の位置へのポインタを含み、連続的に格納する必要はない。

多数のレコードは1つのフィールドでしかソートできないという事実から、ソートされていないフィールドで検索するには、線形検索が必要であると言える。 (N+1)/2 ブロックアクセス（平均）、ここで N はテーブルのブロック数です。そのフィールドが非キーフィールドである場合（つまり、ユニークエントリを含まない場合）、テーブルスペース全体を N ブロックのアクセスになります。

一方、ソートされたフィールドでは、バイナリサーチが使用されることがあり、これには log2 N ブロックアクセスになります。また、非キーフィールドでソートされているため、一度高い値が見つかれば、残りのテーブルを重複して検索する必要はない。このように、性能は大幅に向上している。

インデックス作成とは何ですか？

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

インデックス作成の欠点は、インデックスが MyISAM エンジンを使用してテーブルに格納されるため、ディスク上に追加のスペースが必要になることです。

どのように機能するのですか？

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

フィールド名 データ型 ディスク上のサイズ
id (主キー) 符号なし INT 4 bytes
firstName Char(50) 50 bytes
lastName Char(50) 50 bytes
電子メールアドレス Char(100) 100 bytes

備考 : varchar の代わりに char を使用し、ディスク上の値を正確にサイズ指定できるようにしました。 このサンプルデータベースは、500万行を含み、インデックスが設定されていません。次に、いくつかのクエリのパフォーマンスを分析します。これらのクエリーは イド (ソートされたキー・フィールド) を使ったもの、および ファーストネーム (キー以外のソートされていないフィールド)。

例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フィールドで線形検索すると、平均で N/2 = 500,000 のブロックアクセスで値を見つけることができる。idフィールドはキーフィールドである。しかし、idフィールドもソートされているため、バイナリサーチを行うには、平均して log2 1000000 = 19.93 = 20 ブロックアクセスになります。これは飛躍的な改善であることが一目瞭然です。

今度は ファーストネーム フィールドはソートされておらず、キーフィールドでもないため、バイナリ検索は不可能です。 N = 1,000,000 ブロックのアクセスがあります。インデックス作成は、このような状況を改善することを目的としています。

インデックス・レコードは、インデックスされたフィールドと元のレコードへのポインタだけを含んでいるので、それが指す複数フィールドのレコードよりも小さくなるのは当然のことです。つまり、インデックス自体が必要とするディスクブロック数は元のテーブルよりも少なく、その分、反復処理に必要なブロックアクセス数も少なくなります。テーブルのインデックスのスキーマは ファーストネーム フィールドの概要は以下の通りである。

フィールド名 データ型 ディスク上のサイズ
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 ブロックになります。

今度は ファーストネーム フィールドは、パフォーマンスを向上させるためにインデックスを利用することができます。これにより、インデックスのバイナリ検索で、平均して log2 277778 = 18.08 = 19 ブロックアクセスになります。実際のレコードのアドレスを見つけるには、さらにブロック・アクセスで読み込む必要があり、その合計は 19 + 1 = 20 を見つけるのに必要な1,000,000ブロックアクセスとは比べものにならないほど、膨大な数のブロックアクセスが必要です。 ファーストネーム インデックスがないテーブルでマッチする。

どのような場合に使用するのですか？

インデックスを作成するには追加のディスクスペースが必要であり（上記の例では277,778ブロック、約28%の増加）、インデックスが多すぎるとファイルシステムのサイズ制限に起因する問題が発生することを考えると、インデックスを作成する正しいフィールドを選択するには慎重に考える必要があります。

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