MySQL インデックス構造の深い理解

この記事では、mysql に関する関連知識を提供し、主にインデックス構造に関する関連問題を紹介します。なぜインデックス作成がこれほど高速になるのでしょうか?以下で見てみましょう。皆さんのお役に立てれば幸いです。

推奨学習: mysql チュートリアル

データベース ストレージ ユニット

まず、次のことを知っておく必要があります。永続化を実現するには、インデックスはハードディスクにのみ保存できますが、インデックスを介してクエリを実行すると、ハードディスクへの I/O 操作が発生するため、インデックスを設計する際には、インデックスの数を減らす必要があります。可能な限り検索を行うことで、I/O にかかる時間を削減します。

さらに、非常に重要な原則を知っておく必要があります。データベース管理の記憶域スペースの基本単位は ページ (Page) であり、複数の行レコード (Row) が 1 つのページに保存されます。 。

コンピュータ システムは、ディスク I/O の 先読み 最適化を実行します。I/O が実行されると、現在のディスク アドレスのデータに加えて、隣接するデータも実行されます。メモリ バッファ プールでは、各 I/O で読み取られるデータは 1 ページになります。InnoDB のデフォルトのページ サイズは 16KB です。
64 の連続したページは エクステント を形成し、1 つ以上のエクステントは セグメント を形成し、1 つ以上のセグメントは テーブルスペース を形成します。 InnoDB には 2 つのテーブル スペース タイプがあります。共有テーブル スペースとは、複数のテーブルが 1 つのテーブル スペースを共有することを意味します。独立テーブル スペースとは、各テーブルのデータとインデックスがすべて独立したテーブル スペースに格納されることを意味します。

データ ページの構造は次のとおりです (出典: Geek Time "MySQL Must Know"):

データ ページの 7 つの構造コンテンツは、次のように大別できます。次の 3 つのカテゴリ:

• ファイルの一般部分。ページ送信の完全性を検証するために使用されます。
  • ファイル ヘッダー: ページ情報を表します。FIL_PAGE_PREV および FIL_PAGE_NEXT は、ファイル ヘッダーで使用されます。それぞれ双方向リンク リストを形成し、前と次のデータ ページを指します。
  • ファイル ヘッダー: ページのステータス情報を記録します。
  • ファイル トレーラー: ページが完了したかどうかを確認します。
• データの保存に使用されるレコード部分records
  • 最大レコードと最小レコード (Infimum/Supremum): データ ページの最大レコードと最小レコードを表す仮想行レコード。
  • ユーザー レコードと空き領域: データ行レコードのコンテンツを保存するために使用されます。
• インデックス パーツ。レコードの取得効率を向上させるために使用されます。
  • ページ ディレクトリ:ユーザー レコードが保存される相対的な場所

詳細については、タオバオのデータベース カーネル月次レポートを参照してください

インデックス データの構造

当然のことながら、二分探索ツリー、二分平衡ツリーなど、検索アルゴリズムに関連するいくつかの一般的なデータ構造について考えます。実際、Innodb のインデックスは B Tree を使用して実装されています。なぜこのインデックスが実装されているかを見てみましょう。構造が選ばれました。

二分木の制限事項

二分探索木の定義を簡単におさらいしましょう。二分探索木では、検索対象のキーがルート ノードより大きい場合、検索でルート ノードが検索されます。右のサブツリー。キーがルート ノードより小さい場合は、キーが見つかるまで左のサブツリーを検索します。時間計算量は O(logn) です。たとえば、シーケンス [4,2,6,1,3,5,7] は次の二分探索ツリーを生成します:

ただし、一部の特殊なケースでは、二分木の深さはたとえば、[1,2,3,4,5,6,7] は次のツリーを生成します:

次の状況では、最悪の場合、 7回の確認で目的の結果が得られ、クエリ時間はO(n)となります。

この状況を最適化するために、平衡二分探索木 (AVL ツリー) が存在します。AVL ツリーとは、左右の部分木の高さの差が 1 を超えない木を指します。時間計算量は O(logn) であり、これはすでに理想的な検索ツリーですが、数千万行のレコードを持つデータベースでは、ツリーの深さは依然として非常に高く、依然として最も理想的な構造ではありません。

B ツリー

したがって、二分木から N 分木に拡張すると、N 分木によって木の深さが大幅に削減されることは容易に想像できます。実際、4 層のツリー構造はすでに数十テラバイトのデータをサポートできます。

B ツリー (バランス ツリー) は、このような N 分木です。B ツリーは B ツリーとも呼ばれ、次の定義を満たします:
B ツリーの次数を k とします (ノードが持つことができる子ノードの最大数)、

1. 各ディスク ブロックには、最大 k - 1 個のキーワードと子ノードへの k ポインタが含まれます。
2. リーフ ノードには、キーワードのみが含まれ、子ノード ポインタ
3. 各ノード内のキーワードは昇順に配置されます。各キーワードの左側のサブツリー内のすべてのキーワードはそれより小さく、右側のサブツリー内のキーワードはそれより小さくなります。すべてのキーワードは大きいです。それよりも。
4. すべてのリーフ ノードは同じレイヤー上にあります。

上で述べたように、各 I/O は 1 ページのサイズのディスク ブロックのデータを事前に読み取ります。ディスク ブロックの内容は I/O を表すために使用されます。 B ツリーの構造は次のとおりです (出典: Geek Time SQL が知っておくべき):

B ツリーも順序付けされており、子ノード ポインターはキーワードより 1 大きい必要があるため、ノードのセクションは、図の例のように、ディスク ブロック 2 のように、各ノードには 2 つのキーと 3 つの子ノードがあり、最初のバイト ポイントのキーは 3 です。 、 5 は最初の子ノード 8 より小さく、2 番目の子ノードの 9、10 は 8 と 12 の間にあり、3 番目の子ノードの値 13、15 はそれ自体の 2 番目の子ノード 12 より大きくなります。

今 9 を見つけたいとします。手順は次のとおりです。

1. ルート ノードのディスク ブロック 1 (17,35) と比較すると、17 未満です。続行します。ポインタ P1 を検索するには、対応するディスク ブロック 2
2. がディスク ブロック 2 (8,12) と比較され、この 2 つの間に位置し、ディスク ブロック 6# に対応するポインタ P2 で検索を続けます。
## とディスク ブロック 6 (9, 10) を比較して 9

を見つけます。多くの比較操作が実行されましたが、事前読み取りにより、ディスク ブロックはメモリ内で実行され、ディスク I/O を消費しません。上記の操作は完了するまでに 3 I/O 回しか必要とせず、これはすでに理想的な構造です。

B-tree インデックス

B-tree は、B-tree をベースにさらに改良されたもので、B-tree との違いは次のとおりです。

B ツリーの構築方法では、親ノードのキーワードについて、左側のサブツリーのすべてのキーワードはそれより小さく、右側のサブツリーのすべてのキーワードはそれ以上になります。

非リーフ ノードはインデックス作成にのみ使用され、データ レコードは保存されません
1. 親ノードのキーワードは子ノードにも表示され、それらは最大値になります。子ノードの (または最小値)
2. すべてのキーワードが表示されます。リーフ ノードのうち、リーフ ノードは、小さいものから大きいものへと並べ替えられた、順序付けされたリンク リストを形成します。
3. #例は次のとおりです。この例では、親ノードのキーワードは子ノードの中での最小値です (出典: Geek Time SQL が知っておくべき):
4. 仮定 キーワード 16 を見つけるための検索手順は次のとおりです。

ルート ノード ディスク 1 (1,18,35) と比較し、16 は 1 と 18 の間にあり、ポインタ P1 を取得します。 、ディスク 2 を指します

ディスク 2 (1,8,14) を検索します。16 は 14 より大きいです。ポインタ P3 を取得します。ディスク 7 を指します

1. ディスク 7 (14,16, 17)、16
2. B ツリーの利点:
3. # 内部ノードはデータを保存しないため、各内部ノードが保存できるレコードの数は、B ツリーよりもはるかに多くなります。 B ツリーのそれです。ツリーの高さは低く、I/O は少なくなります。I/O のたびに読み取られるデータ ページには、より多くのコンテンツがあります。

範囲クエリをサポートできます。リーフ ノード

すべてのデータはリーフ ノードに保存されるため、クエリ効率がより安定します
2. HASH インデックス
3. MySQL のメモリ ストレージ エンジンのデフォルトのインデックス構造はハッシュインデックスです。ハッシュとは、特定のアルゴリズム（MD5、SHA1、SHA2など）を通過させ、任意の長さの入力を固定長の出力に変換するハッシュ関数と呼ばれる関数です。入力と出力は、次のように対応します。この記事ではハッシュ関数については詳しく説明しませんので、詳細については百度百科を参照してください。

ハッシュ検索効率はO(1)と非常に効率的です。Pythonのdict、golangのmap、javaのハッシュマップはすべてハッシュをベースに実装されています。RedisなどのKey-Valueデータベースも実装されています。ハッシュ。

正確な検索を行うには、B ツリー インデックスよりもハッシュ インデックスの方が効率的ですが、ハッシュ インデックスにはいくつかの制限があるため、最も主流のインデックス構造ではありません。

ハッシュ インデックスが指すデータは順序付けされていないため、ハッシュ インデックスは範囲クエリを実行できず、ORDER BY 並べ替えもサポートしません。

ハッシュは完全一致であるため、あいまいクエリは実行できません。

ハッシュ インデックスは、ジョイント インデックスの左端の一致原則をサポートしていません。ジョイント インデックスは、完全に一致する場合にのみ有効になります。ハッシュ インデックスは、各インデックスの個別のハッシュ値を計算するのではなく、インデックスをマージしてからハッシュ値を一緒に計算することによってハッシュ値を計算するためです。
1. インデックス付きフィールドに重複する値が多数ある場合、大量のハッシュ競合が発生し、クエリに非常に時間がかかります。
3. 上記の理由により、Mysql InnoDB エンジンはハッシュ インデックスをサポートしていませんが、メモリ構造には適応型ハッシュ インデックス機能があり、インデックス値が非常に頻繁に使用される場合、 in B ツリー インデックスに基づいて、
はクエリのパフォーマンスを向上させるためにハッシュ インデックスを自動的に作成します。

4. アダプティブ ハッシュ インデックスは、一種の「インデックスのインデックス」として理解できます。ハッシュ インデックスは、B ツリー インデックスにページ アドレスを格納し、対応するリーフ ノードを迅速に見つけるために使用されます。これは、innodb_adaptive_hash_index 変数を通じて表示できます。

   推奨学習: mysql チュートリアル

以上がMySQL インデックス構造の深い理解の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。