MySQL でインデックス構造として B+ ツリーを使用する利点は何ですか?

序文

MySQL では、Innodb と MyIsam の両方がインデックス構造として B+ ツリーを使用します (ハッシュなどの他のインデックスはここでは考慮されません)。この記事では、最も一般的なバイナリ検索ツリーから始めて、さまざまなツリーによって解決される問題とそれらが直面する新しい問題について徐々に説明し、MySQL がインデックス構造として B+ ツリーを選択する理由を説明します。

1. 二分探索木（BST）：不均衡

バイナリ検索ツリー (BST) は、バイナリソートツリーとも呼ばれ、バイナリツリーに基づいて次の条件を満たす必要があります。任意のノードの左サブツリー上のすべてのノードの値がルートノードの値より大きくなく、任意のノードの右サブツリー上のすべてのノードの値がルートノードの値より小さくない。以下は BST です。

高速検索が必要な場合、クエリ時間はツリーの高さに依存し、平均時間計算量は O(lgn) であるため、BST にデータを保存するのが一般的な選択肢です。しかし、次の図に示すように、BST が曲がって不均衡になることがあります。このとき、BST はリンク リストに退化し、時間計算量は O(n) に退化します。

この問題を解決するために、バランスのとれた二分木が導入されました。

2. バランスバイナリツリー（AVL）：ローテーションに時間がかかる

AVL ツリーは厳密にバランスのとれた二分木です。すべてのノードの左サブツリーと右サブツリーの高さの差は 1 を超えることはできません。AVL ツリーの検索、挿入、削除は、平均の場合も最悪の場合も O(lgn) です。

AVL でバランスを実現するための鍵は回転操作にあります。挿入と削除によりバイナリ ツリーのバランスが崩れる場合があります。この場合、ツリーのバランスを再調整するには 1 回以上のツリー回転が必要です。データを挿入する場合、最大で 1 回の回転 (単一または二重の回転) のみが必要ですが、データを削除する場合はツリーのバランスが崩れます。AVL は、削除されたノードからルート ノードまでのパス上のすべてのノードのバランスを維持する必要があり、回転の順序は O(lgn) です。

AVL ツリーは、時間のかかるローテーションのため、データを削除するときに非常に非効率的です。削除操作が多い場合、バランスを維持するためのコストが、それがもたらす利点よりも高くなる可能性があるため、実際には AVL は広く使用されていません。

3. 赤黒木：木が高すぎる

AVL ツリーと比較すると、赤黒ツリーは厳密なバランスを追求するのではなく、大まかなバランスを追求します。つまり、ルートからリーフまでの最長パスが最短パスの 2 倍を超えないようにするだけです。実装の観点から見ると、赤黒木の最大の特徴は、各ノードが 2 つの色 (赤または黒) のいずれかに属し、ノードの色の分割が特定のルールを満たす必要があることです (特定のルールは省略します)。以下は赤黒木の例です。

AVL ツリーと比較すると、赤黒ツリーはツリーのバランスが悪く、高さも高いため、クエリ効率は低下します。ただし、赤黒木では色も導入されるため、削除効率は大幅に向上します。データの挿入または削除時には、基本的なバランスを確保するために O(1) 回転と色の変更のみが必要であり、AVL 木のような O(lgn) 回転は必要ありません。一般に、赤黒木の統計的パフォーマンスは AVL よりも高くなります。

したがって、実際のアプリケーションでは、AVL ツリーが使用されることは比較的まれですが、赤黒ツリーは非常に広く使用されています。たとえば、Java の TreeMap は、ソートされたキーと値のペアを格納するために赤黒木を使用します。Java8 の HashMap は、ハッシュ衝突の問題を解決するためにリンク リスト + 赤黒木を使用します (競合するノードが少ない場合はリンク リストが使用され、競合するノードが多い場合は赤黒木が使用されます)。

データがメモリ内にある状況 (前述の TreeMap や HashMap など) では、赤黒木のパフォーマンスは優れています。ただし、赤黒木は高くなりすぎるため、ディスクなどの補助記憶装置 (MySQL などのデータベースなど) 内のデータの処理には適していません。データがディスク上にある場合、ディスク IO が最大のパフォーマンス ボトルネックになるため、設計目標は IO 回数を最小限に抑えることです。ツリーが高くなるほど、追加、削除、変更、チェックに必要な IO 回数が増え、パフォーマンスに重大な影響を及ぼします。

4. Bツリー: ディスクのために生まれた

B ツリーは、B ツリー (マイナス記号なし) とも呼ばれ、ディスクなどの補助記憶装置用に設計された多方向バランス検索ツリーです。バイナリ ツリーと比較すると、ツリーのリーフ以外の各ノードには複数のサブツリーを含めることができます。したがって、ノードの総数が同じ場合、B ツリーの高さは AVL ツリーや赤黒ツリーよりもはるかに小さくなり (B ツリーは「背が低くて太った男」です)、ディスク IO 回数が大幅に削減されます。

B ツリーを定義する上で最も重要な概念は順序です。m 順序の B ツリーの場合、次の条件を満たす必要があります。

• 各ノードには最大 m 個の子ノードが含まれます。
• ルート ノードに子ノードが含まれている場合、ルート ノードには少なくとも 2 つの子ノードが含まれます。ルート ノードを除く各非リーフ ノードには、少なくとも m/2 個の子ノードが含まれます。
• k 個の子を持つ非リーフ ノードには、k - 1 個のレコードが含まれます。
• すべてのリーフノードは同じレイヤーにあります。

B ツリーの定義は主に、子ノードと非リーフ ノードのレコードの数を制限することであることがわかります。

次の図は 3 次 B ツリーの例です。

B ツリーの利点は、ツリーの高さが小さいだけでなく、アクセスの局所性の原則を活用していることです。いわゆる局所性原理とは、あるデータが使用されるとき、近くのデータが短時間で使用される可能性が高くなることを意味します。 B ツリーは、同じノードに類似のキーを持つデータを格納します。データの一部がアクセスされると、データベースはノード全体をキャッシュに読み込みます。次に隣接するデータにアクセスすると、ディスク IO なしでキャッシュから直接読み取ることができます。つまり、B ツリーの方がキャッシュ ヒット率が高くなります。

B ツリーはデータベースでいくつかの用途に使用されています。たとえば、MongoDB のインデックスは B ツリー構造を使用しています。ただし、多くのデータベース アプリケーションでは、B ツリーのバリエーションである B+ ツリーが使用されています。

5. B+ツリー

B+ ツリーも多方向バランス検索ツリーです。B+ ツリーと B ツリーの主な違いは次のとおりです。

• B ツリーの各ノード (リーフ ノードと非リーフ ノードを含む) には実際のデータが格納されますが、B+ ツリーではリーフ ノードのみが実際のデータを格納し、非リーフ ノードはキーのみを格納します。 MySQL では、ここで言及される実際のデータは、行のすべてのデータ (Innodb のクラスター化インデックスなど)、行の主キーのみ (Innodb の補助インデックスなど)、または行のアドレス (MyIsam の非クラスター化インデックスなど) である場合があります。
• B ツリーのレコードは 1 回だけ表示され、繰り返して表示されませんが、B+ ツリーのキーは繰り返して表示されることがあります。つまり、リーフ ノードには必ず表示され、非リーフ ノードにも繰り返し表示されることがあります。
• B+ ツリーのリーフ ノードは、二重リンク リストによってリンクされます。
• B ツリーの非リーフ ノードでは、レコードの数は子ノードの数より 1 つ少なくなります。一方、B+ ツリーでは、レコードの数は子ノードの数と同じになります。

したがって、B+ ツリーには B ツリーに比べて次のような利点があります。

• **IO 回数が少ない: **B+ ツリーの非リーフ ノードには実際のデータではなくキーのみが含まれるため、各ノードに格納されるレコード数は B 数よりもはるかに多くなります (つまり、順序 m が大きくなります)。そのため、B+ ツリーの高さは低くなり、アクセスに必要な IO 回数が少なくなります。さらに、各ノードにはより多くのレコードが格納されるため、アクセス局所性原則がより有効に活用され、キャッシュヒット率が高くなります。
• **範囲クエリに適しています: **B ツリーで範囲クエリを実行する場合、最初に検索する下限を見つけ、次に上限が見つかるまで B ツリーを順番にトラバーサルします。一方、B+ ツリーで範囲クエリを実行する場合は、リンク リストをトラバースするだけで済みます。
• **より安定したクエリ効率: **B ツリーのクエリ時間の複雑さは 1 からツリーの高さ (それぞれルート ノードとリーフ ノードのレコードに対応) の間ですが、B+ ツリーのクエリの複雑さはすべてのデータがリーフ ノードにあるためツリーの高さで安定しています。

B+ ツリーには欠点もあります。キーが繰り返されるため、より多くのスペースを占有します。ただし、パフォーマンス上の利点と比較すると、スペース上の欠点は許容できることが多いため、データベースでは B ツリーよりも B+ ツリーの方が広く使用されています。

6. B+ツリーのパワーを感じる

前述したように、赤黒木などのバイナリ ツリーと比較した B ツリー/B+ ツリーの最大の利点は、ツリーの高さが小さいことです。実際、Innodb の B+ インデックスの場合、ツリーの高さは通常 2 ～ 4 層です。具体的な見積もりをしてみましょう。

ツリーの高さは順序によって決まります。順序が大きいほど、ツリーは短くなります。順序は、各ノードが保存できるレコードの数によって決まります。 Innodb の各ノードはページ サイズが 16KB のページを使用しますが、そのうちメタデータは約 128 バイト (ファイル管理ヘッダー情報、ページ ヘッダー情報などを含む) のみを占め、ほとんどのスペースはデータの保存に使用されます。

• 非リーフ ノードの場合、レコードにはインデックス キーと次のレベルのノードへのポインターのみが含まれます。各非リーフ ノード ページに 1000 件のレコードが格納されると仮定すると、各レコードは約 16 バイトを占めます。この仮定は、インデックスが整数または短い文字列の場合に妥当です。これを拡張するために、インデックス列の長さは大きくしすぎないようにするという提案をよく耳にします。その理由は、インデックス列が長すぎると、各ノードに含まれるレコードが少なくなりすぎて、ツリーが高くなりすぎて、インデックスの効果が大幅に低下し、インデックスによって無駄なスペースが増えるためです。
• リーフ ノードの場合、レコードにはインデックス キーと値 (値は行の主キー、データの完全な行などです。詳細については前の記事を参照してください) が含まれ、データ量は大きくなります。ここでは、各リーフ ノード ページに 100 件のレコードが格納されていると想定しています (実際には、インデックスがクラスター化インデックスの場合、この数は 100 未満になる可能性があり、インデックスがセカンダリ インデックスの場合、この数は 100 よりはるかに大きくなる可能性があります。これは、実際の状況に基づいて推定できます)。

3 層の B+ ツリーの場合、最初の層 (ルート ノード) には 1 ページがあり、1000 件のレコードを格納できます。2 番目の層には 1000 ページがあり、1000 * 1000 件のレコードを格納できます。3 番目の層 (リーフ ノード) には 1000 * 1000 ページがあり、各ページには 100 件のレコードを格納できるため、1000 * 1000 * 100 件のレコード、つまり 1 億件のレコードを格納できます。バイナリ ツリーの場合、1 億件のレコードを保存するには約 26 層が必要です。

VII. 結論

最後に、さまざまなツリーによって解決された問題と、それらが直面する新しい問題をまとめてみましょう。

1. バイナリ検索木 (BST): ソートの基本的な問題を解決しますが、バランスを保証できないため、リンク リストに退化してしまう可能性があります。
2. バランスバイナリツリー (AVL): バランス問題は回転によって解決されますが、回転操作の効率が低すぎます。
3. 赤黒ツリー: 厳密なバランスを放棄し、赤黒ノードを導入することで、AVL 回転効率が低いという問題は解決されます。ただし、ディスクなどのシナリオでは、ツリーがまだ高すぎて、IO 時間も長すぎます。
4. B ツリー: バイナリ ツリーを多方向バランス検索ツリーに変更することで、ツリーが高すぎる問題が解決されます。
5. B+ ツリー: B ツリーに基づいて、非リーフ ノードはデータを格納しない純粋なインデックス ノードに変換され、ツリーの高さがさらに削減されます。さらに、リーフ ノードはポインターを使用してリンク リストに接続されるため、範囲クエリがより効率的になります。

上記は、MySQL のインデックス構造として B+ ツリーを使用する利点の詳細な内容です。MySQL B+ ツリー インデックス構造の詳細については、123WORDPRESS.COM の他の関連記事に注目してください。