MySQL データベース インデックスが B+ ツリーの使用を選択するのはなぜですか?

MySQL データベース インデックスが B+ ツリーを使用する理由をさらに分析する前に、データ構造のツリーについてまだよくわかっていない人が多いと思います。そこで、ツリーの進化のプロセスを浅い部分から深い部分まで段階的に探り、次に B ツリーを段階的に紹介し、MySQL データベース インデックスが B+ ツリーを使用する理由を説明します。

データ構造を勉強した人なら、一般的に最も基本的なツリーについてはある程度理解しているはずなので、ここでは、私たちのトピックに近い二分探索ツリーから始めます。

1. 二分探索木

（１）二分木の紹介：

二分探索木は順序付き二分探索木とも呼ばれます。二分探索木の一般的な特性を満たしており、空の木には次の特性があります。

1. いずれかのノードの左サブツリーが空でない場合、左サブツリーの値はルートノードの値よりも小さくなります。

2. いずれかのノードの右サブツリーが空でない場合、右サブツリーの値はルートノードの値よりも大きくなります。

3. 任意のノードの左と右のサブツリーも二分探索木です。

4. 等しいキー値を持つノードが存在しない。

上の図は、一般的な二分探索木です。順序探索法に従って、出力は小さい順、つまり 2、3、5、6、7、8 の順にソートできます。

上記のバイナリ ツリーを検索して、たとえばキー値が 5 のレコードを検索するには、まずキー値が 6 であるルートを検索します。6 は 5 より大きいため、6 の左のサブツリーを検索して 3 を見つけます。5 は 3 より大きいため、その右のサブツリーを検索します。合計 3 回の検索が実行されます。同じ要件を 2、3、5、6、7、8 の順序で 3 回検索する場合。同じ方法を使用して、キー値が 8 のレコードを検索します。今度は 3 回の検索が必要ですが、順次検索では 6 回の検索が必要です。平均検索回数を計算すると、順次検索の平均検索回数は (1+2+3+4+5+6)/6 = 3.3 回、二分探索木の平均検索回数は (3+3+3+2+2+1)/6 = 2.3 回となります。バイナリ検索ツリーの平均検索速度は、シーケンシャル検索よりも高速です。

（２）制限と適用

二分探索木は n 個のノードからランダムに構成されるため、場合によっては二分探索木が n 個のノードを持つ線形チェーンに退化します。以下のように表示されます。

上の図を見てください。ルート ノードが最小または最大の数である場合、バイナリ検索ツリーは完全に線形構造に退化します。上図の平均検索回数は（1+2+3+4+5+5）/6=3.16回となり、順次検索と同様となります。明らかに、このバイナリ ツリーのクエリ効率は非常に低いです。したがって、最高のパフォーマンスでバイナリ検索ツリーを構築するには、このバイナリ ツリーをバランスさせる必要があります (ここでのバランスは、このツリーの高さが前の入力の高さよりも高いという重要な特徴からわかります。同じノードの場合はバランスが取れていません)。これにより、バランスの取れたバイナリ ツリー AVL という新しい定義が生まれます。

2. AVLツリー

（１）はじめに

AVL ツリーはバランス条件付きのバイナリ検索ツリーです。バランス係数の差を使用してバランスが取れているかどうかを判断して、回転によってバランスを実現します。左右のサブツリーの高さは 1 を超えません。赤黒木と比較すると、厳密にバランスの取れたバイナリツリーであり、バランス条件を満たす必要があります (すべてのノードの左右のサブツリーの高さの差が 1 を超えない)。挿入操作と削除操作のどちらを実行する場合でも、上記の条件が満たされない限り、回転によってバランスを維持する必要があり、回転には非常に時間がかかります。このことから、挿入と削除の数は比較的少ないが、検索が多い状況では AVL ツリーが適していることがわかります。

上記から、これは通常のバランスの取れた二分木であることがわかります。この図から、どのノードの左サブツリーと右サブツリー間のバランス係数の差も 1 を超えないことがわかります。

（２）制限事項

この高度なバランスを維持するためのコストは、そこから得られる効率性の向上よりも大きいため、実用的な用途は多くありません。より厳密な全体的バランスではなく、局所的なバランスを追求する赤黒ツリーを使用する場所が増えています。もちろん、アプリケーション シナリオで頻繁な挿入や削除は必要ないが、検索の要件が高い場合は、AVL の方が赤黒木よりも優れています。

（３）応用

1. Windows NT カーネルに広く存在します。

3. 赤黒木

（１）はじめに

バイナリ検索ツリーですが、各ノードにノードの色を表す追加ビットがあり、赤または黒になります。赤黒木では、ルートからリーフまでの任意のパス上のノードの色付け方法を制限することで、どのパスも他のパスの 2 倍の長さにならないようにします。弱バランス二分木です（バランスが取れているため、同じノード条件では、AVL木の高さは赤黒木よりも低いと推測できます）。厳密に要求されるAVL木と比較すると、回転回数が少なくなるため、検索、挿入、削除操作が多い場合は赤黒木を使用します。

（２）自然

1. 各ノードは赤または黒です。

2. ルートノードは黒です。

3. 各リーフ ノード (リーフ ノードはツリーの末尾の NULL ポインターまたは NULL ノード) は黒です。

4. ノードが赤の場合、その子ノードは両方とも黒です。

5. 任意のノードについて、リーフ ツリーの NULL ポインターへの各パスには、同じ数の黒いノードが含まれます。

6. 各パスには同じ黒いノードが含まれています。

（３）応用

1. C++ STL で広く使用されている Map と Set は、どちらも赤黒木を使用して実装されています。

2. 有名な Linux プロセス スケジューラ Completely Fair Scheduler は、プロセス制御ブロックの管理に赤黒木を使用します。プロセスの仮想メモリ領域は赤黒木に格納されます。各仮想アドレス領域は赤黒木のノードに対応します。左のポインタは隣接するアドレスの仮想ストレージ領域を指し、右のポインタは隣接する高アドレスの仮想アドレス空間を指します。

3. IO 多重化 epoll の実装では、赤黒ツリー構成を採用して sockfd を管理し、高速な追加、削除、変更、およびクエリをサポートします。

4. Nginx は、赤黒木を使用してタイマーを管理します。これは、赤黒木が順序付けられており、現在のタイマーとの距離が最小のタイマーをすばやく取得できるためです。

5. Java での TreeMap の実装。

4. B/B+ツリー

バイナリ検索木、AVL、赤黒木という上記の 3 種類の木について説明しましたが、MySQL がインデックスの実装として B+ 木を使用する理由はまだわかっていないようです。心配しないでください。まずは B 木とは何かについて説明しましょう。

（１）はじめに

MySQL のデータは、通常、ディスクに保存されます。データを読み取るときは、ディスクにアクセスするための操作が必要です。ディスクには、ディスクの回転と磁気アームの動きという 2 つの機械的な可動部品があります。プラッターの回転は市場に記載されている毎分の回転数であり、ディスクの移動はプラッターが指定された位置まで回転し、磁気アームを動かしてデータの読み取りと書き込みを開始することです。次に、ディスク上のブロックの位置を特定するプロセスがあり、位置決めはディスク アクセスの時間のかかる部分です。結局のところ、機械的な動きに費やされる時間は、電子的な動きに費やされる時間よりもはるかに長くなります。大量のデータがディスクに保存されている場合、位置決めは明らかに非常に時間のかかるプロセスですが、B ツリーを通じて最適化することで、ディスク読み取り時の位置決めの効率を向上させることができます。

B ツリーを最適化できるのはなぜですか? B ツリーの特性に基づいて、マルチレベルの B ツリーを構築し、関連情報をできるだけ多くのノードに格納することで、レイヤーの数をできるだけ少なくし、後で情報をより速く見つけられるようにし、ディスク I/O 操作も少なくすることができます。さらに、B ツリーはバランスの取れたツリーであり、各ノードからリーフ ノードまでの高さは同じであるため、各クエリが安定していることも保証されます。

一般的に、B/B+ ツリーは、ディスクやその他のストレージ デバイス用に設計されたバランスのとれた多方向検索ツリーです (バイナリと比較すると、B ツリーの各内部ノードには複数のブランチがあります)。赤黒ツリーと比較すると、同じノード状況では、B/B+ ツリーの高さは赤黒ツリーの高さよりもはるかに小さくなります (以下の B/B+ ツリーのパフォーマンス分析で説明されています)。 B/B+ ツリーの操作時間は通常、ディスクへのアクセス時間と CPU 計算時間の 2 つの部分で構成されます。CPU は非常に高速なので、B ツリーの操作効率はディスクへのアクセス回数に依存します。キーワードの総数が同じ場合、B ツリーの高さが小さいほど、ディスク I/O にかかる時間は短くなります。

B ツリーは B ツリーであり、- は単なる記号であることに注意してください。

（２）Bツリーの特性

1. 任意の非葉ノードには最大で M 個の子ノードがあり、M>2 であると定義します。

2. ルートノードの息子の数は[2,M]である。

3. ルートノード以外の非リーフノードの息子の数は[M/2,M]である。

4. 各ノードは、少なくともM/2-1（切り上げ）で最大M-1個のキーワードを格納します（少なくとも2個のキーワード）。

5. 非リーフノードのキーワード数 = 子へのポインター数 - 1;

6. 非リーフノードのキーワード: K[1]、K[2]、…、K[M-1]; および K[i] < K[i+1];

7. 非リーフノードへのポインタ: P[1]、P[2]、…、P[M]。P[1]はキーがK[1]より小さいサブツリーを指し、P[M]はキーがK[M-1]より大きいサブツリーを指し、その他のP[i]はキーが(K[i-1]、K[i])に属するサブツリーを指します。

8. すべてのリーフノードは同じレイヤーに配置されます。

これは単なる単純な B ツリーです。実際には、B ツリー ノードには多くのキーワードがあります。たとえば、上の図では、ノード 35 はキー (インデックス) を表し、小さな黒いブロックは、このキーが指すコンテンツのメモリ内の実際の格納場所 (ポインター) を表します。

5. B+ツリー

（１）はじめに

B+ ツリーは、ファイル システムによって生成される B ツリーのバリエーションです (ファイル ディレクトリはレベルごとにインデックス付けされ、最下位のリーフ ノード (ファイル) のみにデータが格納されます)。リーフ以外のノードにはインデックスのみが格納され、実際のデータは格納されません。データはリーフ ノードに格納されます。これがファイル システム ファイルの検索方法ではないでしょうか。

ファイル検索の例を見てみましょう。3 つのフォルダー a、b、c があり、a には b が含まれ、b には c が含まれ、ファイル yang.c があります。a、b、c はインデックス (非リーフ ノードに格納) であり、a、b、c は検索対象となる yang.c のキーにすぎず、実際のデータ yang.c はリーフ ノードに格納されています。

リーフ以外のノードはすべてインデックス部分として考えることができます。

（２）B+木の特性（以下の特性はB木と異なる）

1. 非リーフノードのサブツリーポインタはキーワードの数と同じです。

2. 非リーフノードのサブツリーポインターp[i]は、キー値が[k[i]、k[i+1]]に属するサブツリーを指します。（Bツリーはオープン区間です。つまり、Bツリーではキーの重複が許可されませんが、B+ツリーでは重複が許可されます）。

3. すべてのリーフノードにリンクポインタを追加します。

4. すべてのキーワードはリーフ ノード (高密度インデックス) に表示されます (リンク リスト内のキーワードは順番に並んでいます)。

5. 非リーフノードはリーフノードのインデックス（スパースインデックス）に相当し、リーフノードは（キーワード）データを格納するためのデータ層に相当します。

6. ファイル システムに適しています。

非リーフ ノード (5、28、65 など) は単なるキー (インデックス) です。リーフ ノード (5、8、9) に格納されている実際のデータは、実データまたは実データへのポインタです。

（３）応用

1. B ツリーと B+ ツリーは主に、MySQL などのファイル システムやデータベースのインデックス作成に使用されます。

6. B/B+ツリーのパフォーマンス分析

n 個のノードを持つバランスのとれた二分木の高さは H (つまり logn) ですが、n 個のノードを持つ B/B+ 木の高さは logt((n+1)/2)+1 です。

メモリ内ルックアップ テーブルとしては、特に m が大きい場合、B ツリーは必ずしもバランスのとれたバイナリ ツリーよりも優れているわけではありません。 B ツリーの検索操作の CPU 時間は O(mlogtn)=O(lgn(m/lgt)) であり、m/lgt>1 であるため、m が大きい場合、O(mlogtn) はバランスの取れたバイナリ ツリーの操作時間よりもはるかに長くなります。したがって、メモリ内で B ツリーを使用する場合は、より小さい m を使用する必要があります。 (通常は最小値 m=3 が採用されます。このとき、B ツリー内の各内部ノードは 2 つまたは 3 つの子を持つことができます。この 3 次 B ツリーは 2-3 ツリーと呼ばれます)。

7. B ツリーよりも B+ ツリーがデータベース インデックスに適しているのはなぜですか?

1. B+ ツリーのディスク読み取りおよび書き込みコストは低くなります。B+ ツリーの内部ノードにはキーワードの特定の情報へのポインタがないため、その内部ノードは B ツリーの内部ノードよりも小さくなります。同じ内部ノードのすべてのキーワードが同じディスク ブロックに格納されている場合、ディスク ブロックはより多くのキーワードを収容でき、メモリ内で一度に検索する必要があるキーワードが増えるため、相対的な IO 読み取りおよび書き込み時間が短縮されます。

2. B+ ツリーのクエリ効率はより安定しています。非終端点は、最終的にファイルの内容を指すノードではなく、リーフ ノード内のキーワードのインデックスのみであるためです。したがって、キーワード検索では、ルート ノードからリーフ ノードへのパスをたどる必要があります。すべてのキーワード クエリのパスの長さは同じであるため、各データのクエリ効率は同等になります。

3. B+ツリーのデータはリーフノードに格納され、ブランチノードはインデックスであるため、データベースをスキャンするのに便利です。リーフノードをスキャンするのは1回だけです。ただし、Bツリーのブランチノードにもデータが格納されているため、特定のデータを見つけるには、順序どおりにスキャンする必要があります。したがって、B+ツリーは間隔クエリに適しているため、B+ツリーは通常、データベースインデックスに使用されます。

追伸: 知乎で誰かがこう言っているのを見ましたが、一理あると思います。

データベース インデックスで B+ ツリーを使用する主な理由は、B ツリーは IO パフォーマンスを向上させるものの、非効率的な要素トラバーサルの問題を解決しないからだと考えられています。まさにこの問題を解決するために、B+ ツリーが作成されました。 B+ ツリーでは、ツリー全体をトラバースするためにリーフ ノードをトラバースするだけで済みます。さらに、範囲ベースのクエリはデータベースで非常に頻繁に使用されますが、B ツリーはそのような操作をサポートしていないか、または効率が悪すぎます。

要約する

以上がこの記事の全内容です。この記事の内容が皆様の勉強や仕事に何らかの参考学習価値をもたらすことを願います。123WORDPRESS.COM をご愛顧いただき、誠にありがとうございます。これについてもっと知りたい場合は、次のリンクをご覧ください。