MySQLが基礎データ構造としてB+ツリーを使用する理由

MySQL の基盤となるデータ構造が B+ ツリーであることは誰もが知っていますが、ではなぜ赤黒ツリーやその他のデータ構造を使用しないのでしょうか?

赤黒木は自己バランス型二分探索木です。Java8 のハッシュマップは、クエリ効率を最適化するために赤黒木を使用しています。赤黒木のクエリ効率は依然として比較的高いことがわかります。しかし、なぜ MySQL は最下層で赤黒木ではなく B+ 木を使用するのでしょうか?

次の図は、赤黒木を 1、2、3、4、5、6 に順番に挿入した後の状況を示しています。

次に、上記の赤黒ツリーに 7 を挿入します。

赤黒木は自己バランスが取れているものの、全体としては依然としてデータ全体が木の右側に偏っていることがわかります。さらにデータが追加されると、数百万または数千万のデータが追加された後、木のレベルは非常に高くなります。クエリを実行するときに、各追加レイヤーにさらに 1 つの IO が必要になります。ツリー レベルの数が増えると、検索効率が非常に低くなります。このとき、なぜもっとバランスの取れた AVL ツリーを使用しないのかと疑問に思う人もいるかもしれません。

1、2、3、4、5、6、7 を一度に挿入した後の AVL ツリーは次のようになります。

確かに見た目はずっと良くなり、ツリー レイヤーの数も減りましたが、AVL では根本的な問題は解決されていません。データ量が数百万、数千万に達すると、ツリー レイヤーの数はまだ比較的多くなります。AVL ツリーのバランスを維持するためのコストは言うまでもなく、AVL ツリー レイヤーの数だけでは要件を満たすことができません。

では、データ量が数百万、数千万、あるいはそれ以上に達したときに、レイヤーの数を少なく抑えることができるデータ構造とはどのようなものでしょうか?当然ですが、レイヤーの数を減らしたい場合は、各レイヤーにより多くのデータを保存する必要があります。バイナリ ツリーがどれだけバランスが取れていても、各ノードには 2 つのフォークしか存在できません。各レイヤーのデータ量はデータ構造によって制限されるため、バイナリ ツリーから選択することはできません。このとき、B ツリーの利点が反映されます。B ツリーの各ノードには複数の要素を格納でき、各要素にはフォークを設定できます。次の図は、B ツリーの各ノードに最大 3 つの要素を格納できることを示しています。

ツリーレベルが 2 レベルに削減されていることがわかります。各ノードに一度に格納できる要素の最大数が十分に大きければ、データ量が数千万に達したとしても、ツリーレベルを許容範囲内に抑えることができます。

しかし、B ツリーには別の問題があります。次の図は、B ツリー レベルが 3 レベルに達した場合の状況を示しています。

ここで要素 5 ～ 10 を取り出す必要がある場合、レイヤーごとのクエリで要素 5 を見つけ、他の要素がこのノードにないことがわかったら、ローカル順序トラバーサルで他の要素をクエリする必要があります。7 を見つけた後、同じ操作を実行して 8、9、10 を見つける必要があります。これにより IO 回数が増えるため、B+ ツリーが発生します。

B+ ツリーは、主に次の 2 つの側面から B ツリーを最適化したものです。

最初の最適化は、各リーフ ノード間に、隣接するノードを指す双方向ポインターを追加することです。これにより、前述の範囲クエリの問題が解決されます。範囲クエリが複数のノードにまたがる場合、ローカルの順序どおりのトラバーサルを必要とせずに、この双方向ポインターを通じて隣接するノードをすばやく見つけることができるため、IO 回数が削減されます。次の図は B+ ツリーを示しています。

しかし、探している要素がリーフノードにない場合はどうなるでしょうか?心配しないでください。B+ ツリーのもう 1 つの最適化は、リーフ ノードにツリーのすべての要素が含まれることです。 B+ ツリーの非リーフ ノードには、要素のデータやポインターは格納されなくなり、クエリを簡単に実行できるように完全な B+ ツリーを形成するための冗長インデックスとしてのみ機能します。上図の要素 15 は、非リーフ ノードだけでなく、リーフ ノードにも存在することがわかります。この設計では、多くの冗長なインデックスが必要になりますが、範囲クエリを実行するときに非リーフ ノードを上方向に検索する必要がなくなります。さらに、各レベルに格納できるインデックスの数が増えるため、データベースは IO を実行するたびに、より多くのインデックス要素をクエリできます。結局のところ、通常の状況では、データが占めるスペースは、インデックスが占めるスペースよりもはるかに大きくなります。 (InnoDB エンジンと MyISAM エンジンはどちらも B+ ツリーを使用しますが、InnoDB のクラスター化インデックスとデータは一緒に保存されるのに対し、MyISAM はクラスター化インデックスと対応するデータ ポインターを一緒に保存し、インデックスとデータは別々に保存されることに注意してください。MyISAM エンジンの B+ ツリーも、リーフ ノードにデータ ポインターのみを保存します。)

上記の分析から、MySQL の基盤レイヤーとして B+ ツリーが選択された理由は、IO 操作の数を減らすためであることがわかります。では、極端に進んでハッシュを使用してデータやインデックスを保存しないのはなぜでしょうか?実際、MySQL はハッシュ タイプのインデックスをサポートしています。

ただし、ハッシュ インデックスはハッシュ コードを格納するものであり、格納順序はインデックス列の値のサイズとは関係がないため、通常は使用されません。したがって、ハッシュ インデックスは正確な検索を実行する場合にのみ有効であり、範囲クエリでは完全なテーブル スキャンが実行されます。同時に、テーブル内のデータ量が非常に多い場合、ハッシュ衝突の数が増加し、単一の検索の効率が B+ ツリーよりも高くならない可能性があります。

簡単にまとめると、他のツリーと比較して、B+ツリーの各ノードはより多くの要素を格納できるため、クエリに必要なIO回数を大幅に削減できます。データやポインタを格納しない非リーフノードの設計により、各ノードに格納される要素の数を増やすことができ、リーフノードの双方向ポインタにより範囲クエリの効率を向上させることができます。

これで、MySQL が基礎データ構造として B+ ツリーを使用する理由に関するこの記事は終了です。MySQL B+ ツリーの詳細については、123WORDPRESS.COM の以前の記事を検索するか、次の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。