データ構造 - ツリー (III): 多方向検索ツリー B ツリー、B+ ツリー

多方向探索ツリー

1. 完全二分木の高さ: O(log2N)、ここで2は対数
2. 完全なM方向探索木の高さ: O(logmN)、ここでMは木の各レベルのノードの数の対数です。
3. M 方向検索ツリーは、メモリにロードするには大きすぎるデータ ストレージの問題を解決するために主に使用されます。各層のノード数を増やし、各ノードに格納するデータを増やすことで、1 つの層に格納できるデータ量が増え、ツリーの高さが減り、データ検索時のディスク アクセス回数が減ります。
4. したがって、各レイヤーのノード数が多くなり、各ノードに含まれるキーワードの数が増えるほど、ツリーの高さは低くなります。ただし、各ノードでデータを決定すると遅くなりますが、B ツリーはディスク パフォーマンスのボトルネックに重点を置いているため、単一ノードでのデータ検索のオーバーヘッドは無視できます。

Bツリー

B ツリーは M 方向検索ツリーです。B ツリーは主に、バイナリ ツリーがリンク リストに退化することで発生するパフォーマンスの問題と同様に、ツリーの高さが高くなる原因となる M 方向検索ツリーの不均衡を解決するために使用されます。 B ツリーは、ノードの分離、ノードのマージ、レイヤーがいっぱいになったときに親ノードを上方に分割して新しいレイヤーを追加するなど、各レイヤーのノードを制御および調整することで、M 方向検索ツリーのバランスを確保します。具体的なルールは以下のとおりです。

1. ルートノードの子ツリーの数は 2 から M の間であり、その他の非リーフノードの子ツリーの数は M/2 から M の間です。分割により子ツリーの数が M を超える場合は、親ノードを再帰的に上方に分割する必要があります。分割する必要のない親ノードが見つかったら、分割は停止します。ルートノードまで分割処理が続きます。ルートノードを分割する必要がある場合は、2 つのルートが生成されるため、この 2 つのルートを子ノードとして使用するために新しいルートを作成する必要があります。このとき、ツリーの高さは 1 増加します。
2. 各非リーフ ノードのキーワードの値は、左から右に向かって増加します。i 番目のキーワードは、サブツリー i+1 内の最小のキーワードを表します (ここで、i は、ルート ノードの場合は 1 から (2 から M) の間、その他の非リーフ ノードの場合は 1 から (M/2 から M) の間です)。
3. B ツリーのすべてのデータ項目はリーフ ノードに格納されます。非リーフ ノードにはデータは格納されません。非リーフ ノードには、検索方向を示すために使用されるキーワード、つまりインデックスのみが格納されます。これにより、より多くの非リーフノードがメモリにロードされ、データの検索が容易になります。
4. すべてのリーフ ノードは同じ深さにあり、各リーフ ノードには L/2 から L 個のデータ項目が含まれます。
   

サイズオプション: MとL

1. MはBツリーのパスの順序または数である。
2. Lは各リーフノードに格納できるデータ項目の最大数である。
3. B ツリーでは、各ノードはディスク ブロックであるため、M と L はディスク ブロックのサイズに基づいて決定する必要があります。

ディスクブロックサイズとMの計算

1. 各非リーフ ノードには、キーワードと子ツリーへのポインタが格納されます。具体的な数値は次のとおりです。M 次数の B ツリーの場合、各非リーフ ノードには M-1 個のキーワードと子ツリーへの M 個のポインタが格納されます。したがって、各キーワードのサイズが 8 バイト (Java の long 型は 8 バイト) で、各ポインタが 4 バイトの場合、M 次数 B ツリーの各非リーフ ノードには、8 * (M-1) + 4 * M = 12M - 8 バイトが必要です。
2. 各非リーフノード (ディスク ブロック) が 8K を超えるメモリ (つまり 8192) を占有しないことが規定されている場合、M の最大値は 683、つまり 683*12-8=8192 になります。
   

リーフノードデータ項目数 L

1. 各データ項目のサイズも 256 バイトの場合、ディスク ブロック サイズは 8K、つまり 8192 バイトであり、各リーフ ノードは L/2 から L のデータ項目を格納できるため、各リーフ ノードは最大で 8192/256 = 32 のデータ項目を格納でき、つまり L のサイズは 32 になります。
2. 5 次 B ツリーの構造は次のようになります。つまり、M と L は 5 に等しくなります。各非リーフ ノードには、M を含む最大 M-1=5-1=4 個のキーワード、つまりサブツリーへの 5 つのポインターが含まれます。 L が 5 の場合、各リーフ ノードには最大 5 つのデータ項目を格納できます。
   

B+ ツリー

B+ツリーの構造は基本的にBツリーと同じです。唯一の違いは、B+ツリーのリーフノードがポインターで接続されてリンクリストを形成するため、すべてのリーフノードをトラバースすること、つまり、検索キーワードの特定の範囲にあるすべてのデータ項目を取得することが容易であることです。 MySQL の InnoDB ストレージ エンジンは、インデックス実装として B+ ツリーを使用します。

上記は、編集者が紹介した多方向探索木 B ツリーと B+ ツリーの詳細な統合です。皆様のお役に立てれば幸いです。ご質問がある場合は、メッセージを残してください。編集者がすぐに返信します。また、123WORDPRESS.COM ウェブサイトをサポートしてくださっている皆様にも感謝申し上げます。