MySQL Innodb インデックスメカニズムの詳細な紹介

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

インデックスは、ストレージエンジンがレコードをすばやく検索するために使用するデータ構造です。

2. インデックスにはどのようなデータ構造がありますか?

順次検索構造: この検索効率は非常に低く、複雑さは O(n) です。データ量が多い場合、クエリの効率は非常に低くなります。
順序付けられたデータ配置: バイナリ検索はハーフ検索とも呼ばれます。

一度比較すると、検索範囲が半分に減ります。 MySQL のデータは順序付けられたシーケンスではありません。

二分探索木: 左のサブツリーのキー値は常にルートのキー値よりも小さく、右のサブツリーのキー値は常にルートのキー値よりも大きくなります。順序付きトラバーサルによって得られたシーケンスは順序付けられたシーケンスですが、バイナリ検索ツリーが適切に構築されていない場合は、順次検索と変わりません。

バランスのとれた二分木: 二分探索木のバランスをとる必要がある場合は、バランスのとれた二分木が導出されます。バランスのとれた二分木は、まず二分探索木の定義を満たす必要があり、次に、任意のノードの 2 つのサブツリー間の高さの最大差が 1 である必要があります。明らかに、上記のツリーはバランスの取れた二分木ではありません。バランスの取れた二分木の例は次のとおりです。

バランスのとれたバイナリ検索ツリーの時間計算量は O(logN) です。クエリ速度は確かに非常に高速ですが、バランスのとれたバイナリツリーを維持するためのコストも非常に高くなります。通常、挿入または更新後にバランスをとるには、1 回以上の左回転と右回転が必要です。

B ツリー: B ツリーとバランスバイナリツリーの違いは、B ツリーがマルチウェイツリー (バランスマルチウェイ検索ツリーとも呼ばれる) であることです。

ルートノードには少なくとも 2 つの子ノード (各ノードには昇順に配置された M-1 個のキーがあります) があり、他のノードには少なくとも M/2 個の子ノードがあります。
リーフノードはすべて同じレイヤー上にあります。

B+ ツリー

B+ ツリーは B ツリーの変種であり、B ツリーとインデックスシーケンシャルアクセスメソッドから進化したものです (B ツリーは実際にはほとんど使用されません)。
B+ ツリーは、ディスクやその他の直接ストレージ補助デバイス用に設計されたバランス検索ツリーです。
B+ツリーでは、すべてのレコードノードがキー値の順序で同じレイヤーのリーフノードに配置され、リーフノードポインタによって接続されます。
すべてのクエリはリーフノードを見つける必要があり、クエリのパフォーマンスは安定しています。
すべてのリーフノードは、範囲クエリを容易にするために順序付けられたリンクリストを形成します。各リーフノードには隣接するリーフノードへのポインタが格納され、リーフノード自体はキーワードのサイズに応じて昇順にリンクされます（双方向リンクリスト）

3. Innodb がインデックスとして B+ ツリーを使用するのはなぜですか?

システムは、ディスクのブロック読み取り特性を効果的に利用して、同じディスクブロックを読み取りながらできるだけ多くのインデックスデータをロードし、インデックスヒット効率を向上させて、ディスク IO 読み取り回数を削減します (局所性原則とディスク事前読み取り)。
B+ ツリーのディスク読み取りおよび書き込みコストは低くなります。B+ ツリーの内部ノードにはキーワードの特定の情報へのポインタがないため (リーフノードのみがそれを格納)、その内部ノードは B ツリーよりも小さくなります。同じ内部ノードのすべてのキーワードが同じディスクブロックに格納されている場合、ディスクブロックはより多くのキーワードを収容でき、メモリ内で一度に検索する必要があるキーワードが増えるため、相対的な IO 読み取りおよび書き込み時間が短縮されます。
B+ツリーのクエリ効率はより安定しています。非終端点は、最終的にファイルの内容を指すノードではないため、リーフノード内のキーワードのインデックスにすぎません。したがって、キーワード検索では、ルートノードからリーフノードへのパスをたどる必要があります。すべてのキーワードクエリのパスの長さは同じであるため、各データのクエリ効率は同等になります。
B+ ツリーは範囲クエリをサポートしますが、B ツリーはサポートしません。