MySQLデータベースインデックスの詳細な紹介

マインドマップ

シンプルな理解

インデックスは、本の目次のようなものと考えることができます。インデックスを使用すると、必要なデータをすばやく見つけることができます。これは、おおよそ次の図のようになります。インデックスは、右側のバイナリツリーのようなものです。各ノードは、特定のデータの物理アドレスを指します。まず、バイナリツリーを通じてデータの場所を見つけ、次に物理ディスクからデータを取得します。

ただし、バイナリツリーはそれぞれ特徴が異なり、インデックスとして適切なツリーを選択する必要があるため、それぞれのツリーの特徴について学習しましょう。

インデックスモデルの進化

二分探索木

バイナリ検索ツリーは配列に基づいており、バイナリ検索手法を使用して中間ノードをポインターとして使用します。このように、各ノードの左のサブツリーの値はノードの値よりも小さくなり、各ノードの右のサブツリーの値はノードの値よりも大きくなります。要素を検索するときに、ルートノードと比較した後、毎回検索範囲のほぼ半分を削除できるため、検索速度が大幅に向上します。

アドバンテージ：

挿入が簡単で、直列に配置する必要はありません

ツリーのユニークな機能を使用すると、検索が非常に便利になります

欠点:

毎回最大値を挿入するとリンクリストとなり、検索の複雑さが増します。

挿入する要素が増えるほどツリーが高くなり、クエリのパフォーマンスが低下します。

自己バランス型二分木

バイナリツリーと比較すると、自己バランスバイナリツリーでは、左または右に回転することで、左のサブツリーと右のサブツリーの高さの差が 1 を超えないことが保証されます。これにより、バイナリ検索ツリーをリンクリストに変換する問題が解決されます。

ただし、要素の数が増えると、ツリーの高さが非常に高くなりやすく、クエリの効率が低下します。この問題を解決するために、B ツリーが誕生しました。

Bツリー

B ツリーの最大の違いは、1 つのノードだけに限定されず、複数のノード、つまりマルチブランチツリーが許可されることです。そして、Bツリーのすべてのリーフノードは同じレベル、つまり同じ深さでなければなりません。

たとえば、次数 d の B ツリーが N 個のキーをインデックスする場合、ツリーの高さ h の上限は logn(N/2) です。キーのノード数を検索する漸近的な複雑さは O(logn((N+1)/2)) です。この点から、B-Tree は非常に効率的なインデックスデータ構造であることがわかります。

局所性原理

このマルチノード構造では、ディスクの事前読み取り機能も有効に活用できます。

ストレージメディアの特性上、ディスクアクセス自体はメインメモリよりはるかに遅くなります。機械的な動作消費に加え、ディスクアクセス速度はメインメモリの数百分の一になることがよくあります。したがって、効率を向上させるには、ディスクI/Oを最小限に抑える必要があります。この目標を達成するために、ディスクは厳密にオンデマンドで読み取られるのではなく、毎回事前に読み取られることがよくあります。必要なのが 1 バイトだけの場合でも、ディスクはこの位置から開始し、一定の長さのデータを順番に逆方向にメモリに読み込みます。この理論的根拠は、コンピュータサイエンスにおける有名な局所性原理です。つまり、あるデータが使用されると、通常、近くのデータがすぐに使用されるということです。プログラム実行中に必要なデータは通常集中しています。ディスクの順次読み取りは非常に効率的であるため (シーク時間は必要なく、回転時間もわずかしか必要ありません)、事前読み取りによって局所性を持つプログラムの I/O 効率を向上させることができます。

B ツリーでは、ノードのサイズがページと同じに設定されるため、各ノードは 1 回の I/O だけで完全にロードできます。この目標を達成するには、B ツリーの実際の実装で次の技術が必要です。<br /> 新しいノードが作成されるたびに、ページのスペースが直接要求されます。これにより、ノードが物理的にページに格納されることが保証されます。さらに、コンピューターのストレージ割り当てはページごとに調整されるため、ノードに必要な I/O は 1 つだけです。

しかし、B ツリーの各ノードにはデータ (インデックス + レコード) が含まれており、ユーザーのレコードデータのサイズはインデックスデータを大幅に超える可能性が高く、「有用なインデックスデータ」を読み取るためにより多くのディスク I/O 操作が必要になります。さらに、最下層のノード (A レコードなど) をクエリすると、「非 A レコードノード」のレコードデータがディスクからメモリにロードされますが、このレコードデータは役に立ちません。比較クエリのためにこれらのノードのインデックスデータを読み取るだけでよく、「非 A レコードノード」のレコードデータは役に立ちません。これにより、ディスク I/O 操作の回数が増えるだけでなく、メモリリソースも占有されます。

B+ ツリー

MySQLは一般的にB+ツリーを使用してインデックス構造を実装します。Bツリーと比較して、B+ツリーには次の違いがあります。

リーフノード (最下層のノード) には実際のデータ (インデックス + レコード) が格納され、非リーフノードにはインデックスのみが格納されます。

すべてのインデックスはリーフノードに表示され、リーフノードは順序付けられたリンクリストを形成します。

非リーフノードのインデックスは子ノードにも存在し、子ノード内のすべてのインデックスの最大値 (または最小値) になります。

非リーフノードには子ノードと同じ数のインデックスが存在します。

B+ ツリーの非リーフノードには実際のレコードデータが格納されず、インデックスのみが格納されます。そのため、データ量が同じ場合、インデックスとレコードの両方を格納する B ツリーと比較すると、B+ ツリーの非リーフノードにはより多くのインデックスを格納できます。そのため、B+ ツリーは B ツリーよりも「短くて太い」ものになり、基になるノードを照会するためのディスク I/O 回数が少なくなります。

B+ はマルチブランチツリーであるため、冗長ノードが多数存在する場合でも、ノードの削除や挿入時に複雑なツリー変形が発生することはありません。

データベースでもB+ツリーをベースに最適化が行われ、シーケンシャルアクセスポインタが追加されます。この最適化の目的は、間隔アクセスのパフォーマンスを向上させることです。たとえば、キーが 18 から 49 までのすべてのデータレコードをクエリする場合、18 を見つけた後は、ノードとポインターをトラバースするだけですべてのデータノードに一度にアクセスできるため、間隔クエリの効率が大幅に向上します。 <br />B ツリーには、すべてのリーフノードをリンクリストで直列に接続する構造がないため、範囲クエリはツリーをトラバースすることによってのみ完了でき、複数のノードでのディスク I/O 操作が必要になります。範囲クエリの効率は、B+ ツリーほど良くありません。したがって、B+ ツリーは、データベースなど、範囲取得の数が多いシナリオに適しています。単一インデックスクエリが多数あるシナリオでは、NoSQL の MongoDB などの B ツリーを検討できます。

MySQL では、B+ ツリーのリーフノードは「双方向リンクリスト」によって接続されており、右方向と左方向の両方向にトラバースできるという利点があります。

クラスター化インデックスとセカンダリインデックス

クラスター化インデックス (主キーインデックス): データとインデックスを組み合わせます。インデックス構造のリーフノードには行データが格納されます。インデックスを見つけると、データも見つかります。

セカンダリインデックス (非主キーインデックス): データとインデックスを別々に格納します。インデックス構造のリーフノードには、主キー値が格納されます。

InnoDB はクラスター化インデックスを作成するときに、さまざまなシナリオに基づいてさまざまな列をインデックスとして選択します。

主キーがある場合は、デフォルトでクラスター化インデックスのインデックスキーとして使用されます。

主キーがない場合は、NULL値を含まない最初の一意の列をクラスター化インデックスのインデックスキーとして選択します。

上記の 2 つのケースがない場合は、InnoDB はクラスター化インデックスのインデックスキーとして暗黙的な自動インクリメント ID 列を自動的に生成します。

テーブル内のデータはクラスター化インデックスのリーフノードに格納されるため、InnoDB ストレージエンジンは必ずテーブルに対してクラスター化インデックスを作成します。また、物理的に保存されるデータのコピーは 1 つだけなので、クラスター化インデックスは 1 つしか存在できませんが、セカンダリインデックスは複数作成できます。

例えば、図中の（ID, k）の値は（100, 1）、（200, 2）、（300, 3）、（500, 5）、（600, 6）である。

クエリ時の違い:

ステートメントが select * from T where ID=500 の場合、つまり主キークエリメソッドの場合、ID の B+ ツリーのみを検索する必要があります。

ステートメントが select * from T where k=5 の場合、つまり通常のインデックスクエリメソッドの場合は、最初に k インデックスツリーを検索して ID 値 500 を取得し、次に ID インデックスツリーを再度検索する必要があります。このプロセスはテーブルリターンと呼ばれます。

つまり、非主キーインデックスに基づくクエリでは、もう 1 つのインデックスツリーをスキャンする必要があります。したがって、アプリケーションでは主キークエリを使用するようにしてください。

要約する

これで、MySQL データベースインデックスの詳細な紹介に関するこの記事は終了です。MySQL インデックスに関するより関連性の高いコンテンツについては、123WORDPRESS.COM の以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。

以下もご興味があるかもしれません: