mysql インデックスが B+ ツリー構造を使用する理由について詳しく話しましょう

この記事は mysql の高度な研究であり、mysql がインデックス データ構造として B ツリーを使用する理由を紹介しています。

インデックスによりクエリの効率が向上します。私たちが読んでいる本と同じように、特定の章に直接進みたい場合、ページごとにめくる必要はありません。目次を参照して、そのページが記載されているページ番号を見つけるだけです。 [関連する推奨事項: mysql ビデオ チュートリアル ]

コンピューターでは、このディレクトリを保存するためのデータ構造が必要です。一般的なデータ構造には、ハッシュ テーブル、二分探索ツリー、二分残高が含まれます。ツリー ( AVL)、赤黒ツリー、では、Innodb と MyISAM が b ツリーを選択する理由。

1. ハッシュ テーブル

ハッシュ テーブルは、データの場所を示す添え字 0、1、2、3.... を持つ配列リンク リストです。データをハッシュ テーブルに保存する場合は、まずデータに対してハッシュ アルゴリズムを使用します (基本的なものはモジュロ演算です)。配列の長さが 13 の場合、モジュロ 13 の後は 0 ～ 12 になります。これは、次の値に対応します。計算された添字が同じ場合、リンク リストは添字の位置に続きます。

欠点:

1. ハッシュ ストレージを使用するには、すべてのデータ ファイルをメモリに追加する必要があり、より多くのメモリ領域を消費します。
2. ハッシュ検索は同等のクエリであり、非常に高速ですが、各データ間に範囲ルールがありませんが、実際の作業では範囲クエリに近く、ハッシュは適していません。

#mysql がハッシュ テーブルを使用しないとは直接言えませんが、ストレージ エンジンに基づいて判断する必要があります。メモリ ストレージ エンジンはハッシュ テーブルを使用します

2. 二分探索木

欠点:

図に示すように、極端な場合にはスキューの問題が発生する可能性があります。最終的にはリンクリスト構造になります。
1. ツリー ノードが深すぎるため、検索の IO が増加し、IO が検索のボトルネックになります

3. バイナリ バランス ツリー-AVL

ツリーのバランスを維持し、データの偏りを避けるためには、回転操作が必要です。左または右の回転によって、最も長いサブツリーと最も短いサブツリーの長さは 1 を超えることはできません。1 を超える場合は、

欠点:

1. データ量が多い場合、バランスを維持するため、1 ～ n 回の回転が必要です。この回転は比較です。パフォーマンスの無駄です。挿入と削除の効率は非常に低く、クエリの効率は非常に高くなります。

ブランチは 2 つしかなく、データ量が多い場合でもツリーの深さは非常に深いです。

4. 赤黒ツリー

最長のサブツリーは最短のサブツリーの 2 倍を超えることはできません。色の変更と回転により、挿入とクエリのバランスがとられます

赤黒ツリーは avl ツリーの変形であり、挿入パフォーマンスを向上させるためにクエリ パフォーマンスの一部が失われます。

欠点:

分岐が 2 つしかないため、データ量が多い場合でも深さが非常に深くなります

上記 3 つのバイナリ ツリーは、データが増加すると最終的にノードが多くなり、分岐が 2 つしかないため、IO の数も多くなります。 #解決方法 ブランチが 2 つしかなく、深さが深すぎるため、B ツリーがあり、ブランチを追加します

5. B-Tree

まず、B-subtract ツリーを読み取るのではなく、B-tree を読み取ります。

1. すべてのキー値はツリー全体に分散されます。
2. 検索は非リーフ ノードで終了する場合があり、キーワードの完全なセット内で検索が実行され、パフォーマンスは二分検索に近くなります。
3. 各ノードには最大 m 個のサブツリーがあります。
4. ルート ノードには少なくとも 2 つのサブツリーがあります。
5. ブランチ ノードには少なくとも m/2 のサブツリーがあります (ルート ノードとリーフ ノードを除くすべてのブランチ ノード)。
6. すべてのリーフ ノードは同じレイヤー上にあり、各ノードは最大 m-1 個のキーを持つことができ、昇順に配置されます。

上の図のように (図の一部のみが描画されています。実際には、p1、p2、p3 だけでなく、制限はありません)

各ノードは 1 つのディスク ブロックを占有します。ノード上に昇順に配置された 2 つのキーワードと、サブツリーのルート ノードへの 3 つのポインタがあります。ポインタには、子ノードが配置されているディスク ブロック アドレスが格納されます。 ２つのキーワードで分割された３つの範囲フィールドは、３つのポインタが指すサブツリーのデータの範囲フィールドに対応する。ルートノードを例にとると、キーワードは 16 と 34 です。p1 ポインタが指すサブツリーのデータ範囲は 16 未満、p2 ポインタが指すサブツリーのデータ範囲は 16 ～ 34、データはp3 ポインタが指すサブツリーの範囲は 34 より大きいです。

キーワード 28 を見つけるプロセス:

1. ルート ノードに基づいて ディスク ブロック 1 を見つけ、メモリに読み込みます。 [最初のディスク I/O 操作]
2. 区間 (16, 34) のキーワード 28 を比較し、ディスク ブロック 1 のポインタ p2 を見つけます。
3. p2 ポインタに基づいて ディスク ブロック 3 を検索し、それをメモリに読み取ります。 [2 回目のディスク I/O 操作]
4. 区間 (25, 31) のキーワード 28 を比較し、ディスク ブロック 3 のポインタ p2 を見つけます。
5. ポインタ p2 に基づいて ディスク ブロック 8 を検索し、それをメモリに読み取ります。 [3 回目のディスク I/O 操作]
6. ディスク ブロック 8 のキーワード リストからキーワード 28 を見つけて終了。

欠点:

1. 各ノードにはキーがあり、データが含まれており、各ページのストレージ容量は限られています。データが大きい場合、各ノードのノードが保存できるキーの数は少なくなります。
2. 格納されるデータの量が多い場合、深さが大きくなり、ディスクへのクエリの IO 回数が増加するため、クエリのパフォーマンスに影響します。

6. B-tree

B-tree は B-tree に基づいた最適化であり、変更点は次のとおりです:

1. B ツリーの各ノードにはさらに多くのノードを含めることができます。これには 2 つの理由があります。1 つ目の理由は、ツリーの高さを減らすためです。2 つ目は、データ範囲を複数の間隔に変換するためです。間隔が増えるほど、データをより簡単に、より速く取得できます。
2. 非リーフ ノードはキーのみを保存し、リーフ ノードはキーとデータを保存します。
3. リーフ ノードのポインタは (ディスク先読みの特性に従って) 相互に接続されており、シーケンシャル クエリのパフォーマンスが高くなります。

#上に示すように: B ツリー上には 2 つのヘッド ポインタがあり、1 つはルート ノードを指し、もう 1 つはキーワードの最小リーフ ノードを指します。また、すべてのリーフ ノード (およびデータ ノード) の間にチェーン リング構造があるため、2 つのヘッド ポインタが存在します。 B ツリーには 3 つの検索操作があります。1 つは主キーの範囲検索とページング検索で、もう 1 つはルート ノードから開始するランダム検索です。

InnoDB と MyISAM のインデックスの違い

1. InnoDB の主キー インデックス

リーフ ノードには特定の行データが格納されます

2. InnoDB-非主キー インデックス

非主キー インデックスのリーフ ノードには主キー値が格納されます (したがって、クエリ データは基本的にテーブルに返される必要があります)

3. MyISAM

リーフ ノードは行データのアドレスを格納するため、追加のアドレス指定と 1 つ以上の IO

が必要です。

要約: mysql が B-tree を使用する理由

正確な記述: mysql の InnoDB および MyISAM ストレージ エンジンのインデックスが B-tree を使用する理由

• ハッシュ テーブル、等価クエリは非常に高速ですが、一般的な範囲検索を満たしておらず、隣接する 2 つの値の間に関係がなく、ハッシュはより多くのメモリを消費します。

• 二分木/バランス二分木/赤黒木などはすべて枝を 2 つだけ持ち、木の深さが 2 つしかないという共通点があります。データ量が多い場合はより深く、IO数を増やします。

• B ツリーはノードにデータを格納するため、1 ページに格納されるキーの数が減り、ツリーの深さが増加します。

• B ツリー内の非リーフ ノードのデータが削除されているため、ページ上のキーの数が増加し、リーフ ノードはリンクを通じて接続されています。範囲検索やページングに便利です。

#元アドレス: https://juejin.cn/post/6994810803643744269

著者: Jiさん

プログラミング関連の知識について詳しくは、

プログラミング ビデオ

をご覧ください。 ！

以上がmysql インデックスが B+ ツリー構造を使用する理由について詳しく話しましょうの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。