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

MySQL がデータを素早く取得できる理由を理解したい場合は、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 をよろしくお願いいたします。