データベースのインデックス作成はどのように機能しますか?[閉まっている]

https://stackoverflow.com/questions/1108

08-06-2019
|

質問

データセットのサイズが大きくなるにつれてインデックス作成が非常に重要になることを考えると、データベースに依存しないレベルでインデックス作成がどのように機能するかを誰か説明してもらえますか?

フィールドにインデックスを付けるクエリについては、次を参照してください。データベース列にインデックスを付けるにはどうすればよいですか.

解決

なぜ必要なのでしょうか?

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

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

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

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

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

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

どのように機能するのでしょうか?

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

Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

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

例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 アクセスをブロックします。インデックス作成が修正することを目的としているのは、この状況です。

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

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes

注記: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 のフィールドにインデックスを作成するとデータは半分に分割されますが、カーディナリティ 1,000 の場合は約 1,000 レコードが返されます。このようにカーディナリティが低いと、効率が線形ソートに低下し、カーディナリティがレコード番号の 30% 未満の場合、クエリオプティマイザーはインデックスの使用を回避し、事実上、インデックスがスペースの無駄になります。

他のヒント

初めて読みましたが、とても参考になりました。ありがとう。

それ以来、私はインデックス作成のマイナス面についていくつかの洞察を得ることができました。テーブルに書き込むと (UPDATE または INSERT) 1 つのインデックスを使用すると、実際にはファイルシステム内で 2 つの書き込み操作が行われます。1 つはテーブルデータ用で、もう 1 つはインデックスデータ (およびその再ソート (およびクラスター化されている場合はテーブルデータの再ソート)) 用です。テーブルとインデックスが同じハードディスク上にある場合は、さらに時間がかかります。したがって、インデックスのないテーブル (ヒープ) では、より迅速な書き込み操作が可能になります。(インデックスが 2 つある場合、最終的には書き込み操作が 3 回必要になるなど)

ただし、インデックスデータとテーブルデータ用に 2 つの異なるハードディスク上に 2 つの異なる場所を定義すると、時間コストの増加の問題を軽減または排除できます。これには、必要なハードディスク上の対応するファイルを含む追加のファイルグループの定義と、必要に応じてテーブル/インデックスの場所の定義が必要です。

インデックスに関するもう 1 つの問題は、データが挿入されるにつれて時間の経過とともに断片化することです。 REORGANIZE 役に立ちますが、それを実行するにはルーチンを作成する必要があります。

特定のシナリオでは、インデックス付きのテーブルよりもヒープの方が役立ちます。

例:- 競合する書き込みが多数あるが、レポート作成のための営業時間外の読み取りは毎晩 1 回だけである場合。

また、クラスター化インデックスと非クラスター化インデックスの区別もかなり重要です。

助けて頂きました：- クラスター化インデックスと非クラスター化インデックスとは実際には何を意味しますか?

インデックスは、データベース内の特定の列の検索を高速化するための単なるデータ構造です。この構造は通常、B ツリーまたはハッシュテーブルですが、他の論理構造にすることもできます。

典型的な例 「本の索引」

1000 ページの「本」を 100 のセクションに分割し、各セクションが X ページであるとします。

シンプルですね？

さて、索引ページがない場合、文字「S」で始まる特定のセクションを見つけるには、本全体をざっと読む以外に選択肢はありません。つまり:1000ページ

ただし、先頭にインデックスページがあれば、そこにあります。さらに、重要な特定のセクションを読むには、毎回、インデックスページに何度も目を通すだけで済みます。一致するインデックスを見つけたら、他のセクションをスキップしてそのセクションに効率的にジャンプできます。

ただし、1,000 ページに加えて、インデックスページを表示するためにさらに約 10 ページ必要になるため、合計 1,010 ページになります。

したがって、インデックスは、効率的な検索のために並べ替えられた順序でインデックス付き列の値とインデックス付き行へのポインタを格納する別のセクションになります。

学校では物事は簡単ですよね？:P

ここで、クエリを実行して、「Abc」という名前の従業員の詳細をすべて検索したいとします。

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

インデックスがなかったらどうなるでしょうか?

データベースソフトウェアは文字通り、Employee テーブル内のすべての行を調べて、その行の Employee_Name が「Abc」であるかどうかを確認する必要があります。また、その中に「Abc」という名前を持つすべての行が必要なので、「Abc」という名前を持つ行が 1 つだけ見つかったら、検索をやめるわけにはいきません。同じ名前を持つ行が他にも存在する可能性があるためです。 ABC. 。したがって、最後の行までのすべての行を検索する必要があります。つまり、このシナリオでは、「Abc」という名前の行を見つけるためにデータベースによって何千もの行が検査される必要があります。これはいわゆる フルテーブルスキャン

データベースインデックスがパフォーマンスにどのように役立つか

インデックスを持つことの重要な点は、調査する必要があるテーブル内のレコード/行の数を本質的に削減することで、検索クエリを高速化することです。インデックスは、テーブル内の特定の列の値を格納するデータ構造 (最も一般的には B ツリー) です。

B ツリーインデックスはどのように機能しますか?

B ツリーがインデックスのデータ構造として最も一般的である理由は、検索、削除、挿入がすべて対数時間で実行できるため、時間効率が高いという事実によるものです。また、B ツリーがより一般的に使用されるもう 1 つの主な理由は、B ツリー内に格納されているデータを並べ替えることができるためです。通常、RDBMS は実際にインデックスに使用されるデータ構造を決定します。ただし、特定の RDBMS を使用する一部のシナリオでは、インデックス自体を作成するときにデータベースで使用するデータ構造を実際に指定できます。

ハッシュテーブルインデックスはどのように機能しますか?

ハッシュインデックスが使用される理由は、値を検索するだけの場合、ハッシュテーブルが非常に効率的であるためです。したがって、文字列と等しいかどうかを比較するクエリは、ハッシュインデックスを使用すると、非常に高速に値を取得できます。

たとえば、前に説明したクエリでは、Employee_Name 列に作成されたハッシュインデックスの恩恵を受けることができます。ハッシュインデックスの仕組みとしては、列の値がハッシュテーブルのキーとなり、そのキーにマップされる実際の値はテーブル内の行データへのポインタにすぎません。ハッシュテーブルは基本的に連想配列であるため、一般的なエントリは「Abc => 0x28939」のようになります。0x28939 は、Abc がメモリに格納されているテーブル行への参照です。ハッシュテーブルインデックスで「Abc」のような値を検索し、メモリ内の行への参照を取得する方が、テーブルをスキャンして Employee_Name 列の値が「Abc」であるすべての行を見つけるよりも明らかに高速です。

ハッシュインデックスの欠点

ハッシュテーブルはソートされたデータ構造ではなく、ハッシュインデックスでも対応できない種類のクエリが多数あります。たとえば、40 歳未満の従業員をすべて調べたいとします。ハッシュテーブルインデックスを使用してそれを行うにはどうすればよいでしょうか?ハッシュテーブルはキーと値のペアを検索する場合にのみ適しているため、それは不可能です。つまり、等しいかどうかをチェックするクエリです。

データベースのインデックスの中身は一体何でしょうか?これで、データベースインデックスがテーブル内の列に作成され、インデックスによってその特定の列に値が格納されることがわかりました。ただし、データベースインデックスには同じテーブルの他の列の値は格納されないことを理解することが重要です。たとえば、Employee_Name 列にインデックスを作成した場合、Employee_Age 列と Employee_Address 列の値もインデックスに格納されないことを意味します。他のすべての列をインデックスに格納するだけだと、テーブル全体のコピーをもう 1 つ作成するようなものになり、スペースが非常に多くなり、非常に非効率的になります。

データベースはインデックスをいつ使用するかをどのようにして判断するのでしょうか?「SELECT * FROM Employee WHERE Employee_Name = ‘Abc’ 」のようなクエリが実行されると、データベースはクエリ対象の列にインデックスがあるかどうかを確認します。Employee_Name 列にインデックスが作成されていると仮定すると、データベースは、検索対象の値を見つけるためにインデックスを使用することが実際に意味があるかどうかを判断する必要があります。これは、データベースインデックスを使用する方が実際には効率が低いシナリオがいくつかあるためです。、テーブル全体をスキャンするだけの方が効率的です。

データベースインデックスのコストはいくらですか?

これはスペースを必要とし、テーブルが大きくなるほどインデックスも大きくなります。インデックスに関するもう 1 つのパフォーマンスヒットは、対応するテーブルで行を追加、削除、または更新するたびに、同じ操作をインデックスに対して実行する必要があるという事実です。インデックスには、インデックスがカバーするテーブル列内のデータと同じ最新のデータが含まれている必要があることに注意してください。

一般的なルールとして、インデックスが付けられた列のデータが頻繁にクエリされる場合にのみ、テーブルにインデックスを作成する必要があります。

こちらも参照

簡単な説明!!!!!!!!!

インデックスは、テーブル内の特定の列の値を格納するデータ構造に他なりません。インデックスはテーブルの列に作成されます。

たとえば、名前、年齢、住所の 3 つの列を持つ User というデータベーステーブルがあるとします。User テーブルに数千の行があると仮定します。

ここで、「John」という名前のユーザーの詳細をすべて検索するクエリを実行するとします。次のクエリを実行するとします。

SELECT * FROM User 
WHERE Name = 'John'

データベースソフトウェアは文字通り、User テーブル内のすべての行を調べて、その行の名前が「John」であるかどうかを確認する必要があります。これには長い時間がかかります。
ここでインデックスが役に立ちます。「インデックスは、調査する必要があるテーブル内のレコード/行の数を本質的に削減することで、検索クエリを高速化するために使用されます」。
インデックスの作成方法

CREATE INDEX name_index
ON User (Name)

インデックスは列の値で構成されます(例:John) は 1 つのテーブルから取得され、それらの値はデータ構造に格納されます。
したがって、インデックスはおそらくユーザー名のアルファベット順に並べ替えられるため、データベースはインデックスを使用して John という名前の従業員を検索します。また、ソートされているため、「J」で始まるすべての名前がインデックス内で隣り合って表示されるため、名前の検索がはるかに高速になります。

ちょっとした提案です。インデックス作成には追加の書き込みと記憶領域が必要になるため、アプリケーションでより多くの挿入/更新操作が必要な場合は、インデックスなしのテーブルを使用することをお勧めしますが、より多くのデータ取得操作が必要な場合は、インデックス付きテーブルを使用する必要があります。

データベースインデックスは本のインデックスと考えてください。犬に関する本を持っていて、たとえばジャーマン・シェパードに関する情報を見つけたい場合、もちろん本のすべてのページをめくって探しているものを見つけることもできますが、もちろんこれには時間がかかりますし、それほど効率的ではありません。速い。もう 1 つのオプションは、本の索引セクションに移動し、探しているエンティティの名前 (この例ではジャーマンシェパード) を使用し、ページ番号を参照して探しているものを見つけることです。探しているものをすぐに見つけます。データベースでは、ページ番号は、エンティティが配置されているディスク上のアドレスにデータベースを指示するポインターと呼ばれます。同じジャーマンシェパードに例えると、次のようになります (「ジャーマンシェパード」、0x77129)。0x77129 は、ジャーマンシェパードの行データが保存されているディスク上のアドレスです。

つまり、インデックスは、クエリ検索を高速化するためにテーブル内の特定の列の値を格納するデータ構造です。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow