Java プログラミング スキル - データ構造とアルゴリズム「多方向検索ツリー」

[[391530]]

二分木問題の分析

バイナリツリーは動作効率が高いですが、問題点もあります。次のバイナリツリーをご覧ください

バイナリツリーをメモリにロードする必要があります。バイナリツリーのノード数が少ない場合は問題ありません。ただし、バイナリツリーのノード数が多い場合 (たとえば 1 億)、次の問題が発生します。

1. バイナリ ツリーを構築する場合、複数の I/O 操作が必要となり (大量のデータがデータベースまたはファイルに保存されます)、ノードの数が膨大になるとツリーの構築速度に影響します。
2. ノードの数が多いとバイナリツリーの高さも非常に高くなり、操作速度が低下します。

多枝ツリー

1. バイナリ ツリーでは、各ノードにはデータ項目と最大 2 つの子ノードがあります。各ノードにさらに多くのデータ項目とノードを含めることができる場合、それは多方向ツリーです。
2. たとえば、2-3 ツリーと 2-3-4 ツリーは多分岐ツリーです。多分岐ツリーは、ノードを再編成し、ツリーの高さを減らすことで、バイナリ ツリーを最適化できます。
3. 例えば（下の2-3ツリー）は多分岐ツリーです

Bツリーの基本的な紹介

B-Tree ツリーは B ツリーであり、B は Balanced (バランス) の略です。 MySQL では、特定のタイプのインデックスは、次に示すように B ツリーまたは B+ ツリーに基づいています。

Bツリーの説明:

1. B ツリーの次数は、ノードの子ノードの最大数です。たとえば、2-3 ツリーの次数は 3 で、2-3-4 ツリーの次数は 4 です。
2. B ツリー検索: ルート ノードから開始して、ノード内のキーワード (順序付き) シーケンスに対してバイナリ検索を実行します。ヒットが見つかった場合、検索は終了します。ヒットしない場合は、クエリ キーワードが属する範囲に子ノードを入力します。対応する子ポインタが空になるか、すでにリーフ ノードになるまで繰り返します。
3. キーワード セットはツリー全体に分散されます。つまり、リーフ ノードと非リーフ ノードの両方にデータが格納されます。
4. 検索は非リーフノードで終了する可能性がある
5. その検索パフォーマンスは、キーワードのセット全体に対してバイナリ検索を実行するのと同等です。

B ツリーは、ノードを再編成し、ツリーの高さを減らし、I/O 読み取りと書き込みの数を減らすことで効率を向上させます。

1. 図に示すように、B ツリーはノードを再編成することでツリーの高さを削減します。
2. ファイル システムおよびデータベース システムの設計者は、ディスク事前読み取りの原則を使用して、ノードのサイズをページと同じサイズ (ページ サイズは通常 4k) に設定し、各ノードを 1 回の I/O だけで完全にロードできるようにします。
3. ツリーの次数 M (ツリー内の親ノードが持つ子ノードの最大数) を 1024 に設定します。600 億の要素のうち、必要な要素は最大 4 回の I/O 操作で読み取ることができます。B ツリーは、ファイル ストレージ システムやデータベース システムで広く使用されています。

B+ツリーの基本紹介

B+ ツリーは B ツリーのバリエーションであり、多方向検索ツリーでもあります。

B+ツリーの説明:

1. B+ ツリーの検索は基本的に B ツリーと同じです。違いは、B+ ツリーはリーフ ノードのみにヒットできることです (B ツリーは非リーフ ノードにヒットできます)。そのパフォーマンスは、キーワード セット全体に対するバイナリ検索と同等です。
2. すべてのキーワードは、リーフ ノードのリンク リストに表示されます (つまり、データはリーフ ノード (高密度インデックスとも呼ばれます) にのみ存在します)。また、リンク リスト内のキーワード (データ) は順序付けられています。
3. 非リーフノードをヒットすることは不可能です。
4. 非リーフ ノードはリーフ ノードのインデックス (スパース インデックス) に相当し、リーフ ノードは (キーワード) データを格納するためのデータ レイヤーに相当します。
5. ファイルインデックスシステムに適しています。
6. B ツリーと B+ ツリーにはそれぞれ独自のシナリオがあります。B+ ツリーが B ツリーよりも完全に優れているとは言えませんし、その逆も同様です。

B*ツリーの基本紹介

B* ツリーは B+ ツリーのバリエーションであり、B+ ツリーのルート以外のノードとリーフ以外のノードに兄弟へのポインターを追加します。

Bツリーの説明: *

1. B* ツリーでは、非リーフ ノード キーワードの数が少なくとも (2/3)*M であること、つまり最小ブロック使用量が 2/3 であることが定義されていますが、B+ ツリーの最小ブロック使用量は 1/2 です。
2. 最初の特性から、B* ツリーでは新しいノードが割り当てられる確率が B+ ツリーよりも低く、スペース利用率が高いことがわかります。

2-3 ツリーの基本的な紹介（最も単純な B ツリー）

2-3 ツリーは最も単純な B ツリー構造であり、次の特性があります。

1. 2-3 ツリーのすべてのリーフ ノードは同じレベルにあります。 （Bツリーであればこの条件は満たされます）
2. 2 つの子ノードを持つノードは 2 ノードと呼ばれます。2 ノードには子ノードがないか、子ノードが 2 つあります。
3. 3 つの子ノードを持つノードはトリプル ノードと呼ばれます。トリプル ノードには子ノードがないか、または 3 つの子ノードがあります。
4. 2-3は2つのノードと3つのノードで構成されるツリーです。

2-3 ツリー挿入ルール:

1. 2-3 ツリーのすべてのリーフ ノードは同じレベルにあります。 (B ツリーである限り、この条件は満たされます)。
2. 2 つの子ノードを持つノードは 2 ノードと呼ばれます。2 ノードには子ノードがないか、子ノードが 2 つあります。
3. 3 つの子ノードを持つノードはトリプル ノードと呼ばれます。トリプル ノードには子ノードがないか、または 3 つの子ノードがあります。
4. ルールに従ってノードに数字が挿入されたとき、上記の 3 つの要件を満たせない場合は、解体する必要があります。まず上に向かって解体します。上層がいっぱいの場合は、現在の層を解体します。解体後も、上記の 3 つの条件が満たされている必要があります。
5. 3 ノードのサブツリーの値のサイズは、依然として (BST バイナリ ソート ツリー) の規則を満たしています。