次のチュートリアルでは、B ツリーのデータ構造について学び、それを視覚化することを検討します。
それでは、始めましょう。
Bツリーとは何ですか?
の Bツリー です 特殊なタイプの多方向検索ツリー 、一般的に知られている Mウェイ 自らバランスを保つ木。これらのツリーはバランスのとれた構造のため、膨大なデータベースの操作と管理、検索の簡素化によく利用されています。 B ツリーでは、各ノードは最大で n 個の子ノードを持つことができます。 B ツリーは、データベース管理システム (DBMS) におけるマルチレベル インデックス作成の一例です。リーフ ノードと内部ノードの両方にレコード参照があります。 B ツリーは、すべてのリーフ ノードが同じレベルにあるため、バランス ストアド ツリーとして知られています。
次の図は B ツリーの例です。
図1。 次数 3 の A B ツリー
B ツリーのルールを理解する
B ツリーの重要なプロパティは次のとおりです。
- すべてのリーフ ノードは同じレベルにあります。
- B ツリー データ構造は、最小次数「d」という用語によって定義されます。 「d」の値は、ディスク ブロックのサイズによって異なります。
- ルートを除くすべてのノードは、少なくとも d-1 個のキーで構成されている必要があります。ルート ノードは少なくとも 1 つのキーで構成されます。
- すべてのノード (ルート ノードを含む) は、最大でも次のもので構成されます。 (2d-1) キー。
- ノードの子の数は、 その中に存在するキーの数を追加し、 。
- ノードのすべてのキーは昇順でソートされます。 2 つのキー k1 と k2 の間の子は、それぞれ k1 と k2 の間のすべてのキーで構成されます。
- 二分探索ツリーとは異なり、B ツリーのデータ構造はルートから拡大および縮小します。一方、二分探索木は下に向かって成長し、下に向かって縮小します。
- 他の自己平衡型二分探索ツリーと同様に、検索、挿入、削除などの操作に対する B ツリー データ構造の時間計算量は次のとおりです。 O(ログ?ン) 。
- B ツリーへのノードの挿入は、リーフ ノードでのみ行われます。
次の最小次数 5 の B ツリーの例を考えてみましょう。
図2. A B 次数 5 のツリー
注: 最小次数の値は、実際の B ツリーでは 5 よりはるかに大きくなります。
上の図では、すべてのリーフ ノードが同じレベルにあり、すべての非リーフ ノードには空のサブツリーがなく、子の数より 1 つ少ないキーで構成されていることがわかります。
B ツリー ルールのセット定式化は次のとおりです。
すべての B ツリーは、次のように知られる正の定数に依存します。 最小 、単一ノードに保持できるデータ要素の数を決定するために利用されます。
ルール 1: ルートにはデータ要素を 1 つだけ持つことができます (子がない場合はデータ要素がなくても構いません)。他のすべてのノードには少なくとも 最小 データ要素。
ルール 2: ノードに格納されるデータ要素の最大数は、次の値の 2 倍です。 最小 。
ルール 3: B ツリーの各ノードのデータ要素は、部分的に埋められた配列に格納され、最小のデータ要素 (インデックス位置) からソートされます。 0 ) を最大のデータ要素 (配列の最後に使用される位置) に変換します。
b+ ツリー
ルール 4: 非リーフ ノードの下にあるサブツリーの総数は、常にそのノード内のデータ要素の数より 1 つ多くなります。
- サブツリー 0、サブツリー 1、...
ルール5: リーフ以外のノードに関しては、次のようになります。
- インデックスのデータ要素がサブツリー番号のすべてのデータ要素より大きい 私 ノードの、および
- インデックスのデータ要素がサブツリー番号のすべてのデータ要素より小さいです i+1 ノードの。
ルール6: B ツリーのすべてのリーフの深さは同じです。したがって、B ツリーによって不均衡なツリーの問題が確実に防止されます。
B ツリー データ構造に対する操作
操作中に B ツリー データ構造のプロパティに違反しないようにするために、B ツリーを分割または結合することができます。 B ツリーで実行できる操作の一部を次に示します。
- B ツリー内のデータ要素の検索
- B ツリーへのデータ要素の挿入
- B ツリー内のデータ要素の削除
B ツリーでの検索操作
B ツリー内の要素の検索は、二分探索ツリー内の要素の検索と似ています。ただし、二分探索ツリーのように二方向 (左または右) の決定を行うのではなく、B ツリーは各ノードで m 方向の決定を行います。ここで、m はノードの子の数です。
B ツリー内のデータ要素を検索する手順:
ステップ1： 検索はルート ノードから始まります。検索要素 k をルートと比較します。
ステップ1.1: ルートノードが要素 k で構成されていれば検索は完了します。
ステップ1.2: 要素 k がルートの最初の値より小さい場合、一番左の子に移動し、その子を再帰的に検索します。
ステップ1.3.1: ルートに子が 2 つしかない場合は、右端の子に移動し、子ノードを再帰的に検索します。
ステップ1.3.2: ルートに 3 つ以上のキーがある場合は、残りのキーが検索されます。
ステップ2： ツリー全体を走査しても要素 k が見つからない場合、検索要素は B ツリーに存在しません。
例を使用して上記の手順を視覚化してみましょう。次の B ツリーでキー k=34 を検索したいとします。
クリック時のjQuery
図3.1。 特定の B ツリー
- まず、キーが k = 34 はルートノードにあります。キーはルートにないので、その子ノードに進みます。ルート ノードには 2 つの子があることもわかります。したがって、2 つのキー間で必要な値を比較します。
図3.2。 キー k がルートに存在しません - キー k がルート ノード (つまり 30) より大きいことがわかったので、ルートの右側の子の処理に進みます。
図3.3。 キー k > 30、右の子に移動 - 次に、キー k をノード上に存在する値、つまりそれぞれ 40 と 50 と比較します。キー k は左のキー、つまり 40 より小さいため、ノードの左の子に移動します。
図3.4。 鍵k<40, move to left child< li> - 40 の左の子の値が 34 (必要な値) であるため、キーが見つかったと結論付けることができ、検索操作が完了します。
図3.4。 キー k = 34、40 の左の子
上記の例では、キーが見つかるまでキーを 4 つの異なる値と比較しました。したがって、B ツリーでの検索操作に必要な時間計算量は次のようになります。 O(ログ?ン) 。
B ツリーでの挿入操作
データ要素を B ツリーに挿入するときは、まずその要素がツリー内にすでに存在するかどうかを確認する必要があります。データ要素が B ツリー内で見つかった場合、挿入操作は行われません。ただし、そうでない場合は、さらに挿入を進めます。リーフ ノードに要素を挿入する際には、次の 2 つのシナリオに注意する必要があります。
B ツリーにデータ要素を挿入する手順:
ステップ1： まず、B ツリーの順序に基づいてノード内のキーの最大数を計算します。
ステップ2： ツリーが空の場合は、ルート ノードが割り当てられ、ルート ノードとして機能するキーを挿入します。
ステップ 3: ここで、挿入に該当するノードを検索します。
ステップ 4: ノードがいっぱいの場合:
ステップ4.1: データ要素を昇順で挿入します。
ステップ4.2: データ要素がキーの最大数より大きい場合は、中央値で完全なノードが分割されます。
ステップ4.3: 中央キーを上に押して、左右のキーを左右の子として分割します。
ステップ5: ノードがいっぱいでない場合は、ノードを昇順で挿入します。
例を使用して上記の手順を視覚化してみましょう。次数 4 の B ツリーを作成する必要があるとします。B ツリーに挿入する必要があるデータ要素は次のとおりです。 5、3、21、11、1、16、8、13、4、9 。
- m は 3 に等しいため、ノードのキーの最大数は = m-1 = 3-1 = 2 。
- を挿入することから始めます 5 空っぽの木の中。
図4.1。 5を挿入します - 次に、ツリーに 3 を挿入します。 3 は 5 より小さいため、同じノード内の 5 の左側に 3 を挿入します。
図4.2。 挿入3 - ここで 21 をツリーに挿入します。21 は 5 より大きいため、同じノード内の 5 の右側に挿入されます。ただし、ノード内のキーの最大数は 2 であることがわかっているため、これらのキーの 1 つが分割するために上のノードに移動されます。したがって、中央のデータ要素である 5 が上に移動し、3 と 21 がそれぞれその左側と右側のノードになります。
図4.3。 挿入21 - ここで、次のデータ要素、つまり 5 より大きく 21 より小さい 11 を挿入します。したがって、11 は、キーとして 21 で構成されるノードの左側にキーとして挿入されます。
図4.4。 挿入11 - 同様に、次のデータ要素 1 をツリーに挿入します。見てわかるように、1 は 3 未満です。したがって、キーとして 3 で構成されるノードの左側にキーとして挿入されます。
図4.5。 1を挿入します - ここで、11 より大きく 21 より小さいデータ要素 16 をツリーに挿入します。ただし、そのノード内のキーの数が最大キー数を超えています。したがって、ノードが分割され、中央のキーがルートに移動します。したがって、16 が 5 の右側に挿入され、11 と 21 が 2 つの別々のノードに分割されます。
図4.6。 挿入16 - データ要素 8 は、11 の左側にキーとして挿入されます。
図4.7。 8を挿入 - 16 より小さく 11 より大きい 13 をツリーに挿入します。したがって、データ要素 13 は 8 と 11 で構成されるノードの右側に挿入する必要があります。ただし、ツリー内のキーの最大数は制限されるため、 2 のみの場合は分割が発生し、中央のデータ要素 11 が上のノードに移動され、8 と 13 が 2 つの別々のノードに移動されます。ここで、上記のノードは 5、11、16 で構成され、やはり最大キー数を超えます。したがって、別の分割が行われ、データ要素 11 がルート ノードになり、その子として 5 と 16 が作成されます。
図4.8。 挿入13 - データ要素 4 は 5 未満ですが 3 より大きいため、1 と 3 で構成されるノードの右側に挿入され、ノード内のキーの最大数を再び超えます。したがって、再び流出が発生し、3 が 5 の隣の上のノードに移動します。
図4.9。 挿入4 - 最後に、8 より大きく 11 より小さいデータ要素 9 が、8 で構成されるノードの右側にキーとして挿入されます。
図4.10。 9を挿入
上の例では、さまざまな比較を実行しました。最初の値はツリーに直接挿入されました。その後、すべての値をそのツリー内で使用可能なノードと比較する必要がありました。 B ツリーでの挿入操作の時間計算量は、ノードの数と に依存します。
Javaで文字列を入力する
B ツリーでの削除操作
B ツリー上のデータ要素の削除には、次の 3 つの主要なイベントが含まれます。
- 削除したいキーが存在するノードを検索し、
- キーを削除し、
- 必要に応じて、ツリーのバランスを調整します。
ツリーから要素を削除するときに、アンダーフローとして知られる状態が発生する場合があります。アンダーフローは、ノードが最小数未満のキーで構成されている場合に発生します。それは保持されるはずです。
以下は、削除/削除操作を視覚化する前に理解しておく必要がある用語の一部です。
B ツリーでの削除操作の主な 3 つのケースを次に示します。
ケース 1: キーの削除/削除はリーフ ノードにあります - このケースはさらに 2 つの異なるケースに分けられます。
1. キーの削除/除去は、ノードが保持すべきキーの最小数の特性に違反しません。
次の B ツリーからキー 32 を削除する例を使用して、このケースを視覚化してみましょう。
図 4.1: B ツリーからリーフ ノード キー (32) を削除する
ご覧のとおり、このツリーから 32 を削除しても、上記の特性に違反しません。
2. キーの削除/除去は、ノードが保持すべきキーの最小数の特性に違反します。この場合、左から右の順序で、隣接する兄弟ノードからキーを借用する必要があります。
まず、左隣の兄弟を訪問します。左の兄弟ノードに最小数を超えるキーがある場合、このノードからキーを借用します。
マージソート
それ以外の場合は、隣接する右の兄弟ノードから借用するかどうかを確認します。
次に、上記の B ツリーから 31 を削除する例を使用して、このケースを視覚化してみましょう。この場合、左側の兄弟ノードからキーを借用します。
図 4.2: Bツリーからリーフノードキー(31)を削除する
両方の隣接する兄弟ノードがすでに最小数のキーで構成されている場合、そのノードを左の兄弟ノードまたは右の兄弟ノードとマージします。このマージのプロセスは、親ノードを通じて実行されます。
上記の B ツリーからキー 30 を削除して、再度視覚化してみましょう。
図 4.3: Bツリーからリーフノードキー(30)を削除する
ケース 2: キーの削除/除去が非リーフ ノードにある - このケースはさらにさまざまなケースに分類されます。
1. 左の子ノードに最小数を超えるキーがある場合、削除された非リーフ/内部ノードは、順序どおりの先行ノードに置き換えられます。
B ツリーからキー 33 を削除する例を使用して、このケースを視覚化してみましょう。
図 4.4: Bツリーからリーフノードキー(33)を削除する
2. 右の子ノードに最小数を超えるキーがある場合、削除された非リーフ/内部ノードは、順序どおりの後続ノードに置き換えられます。
どちらかの子が最小数のキーを持っている場合は、Left 子ノードと Right 子ノードをマージします。
Java入力文字列
B ツリーからキー 30 を削除して、このケースを視覚化してみましょう。
図 4.5: Bツリーからリーフノードキー(30)を削除する
マージ後、親ノードのキーが最小数より少ない場合は、次のように兄弟を探すことができます。 ケース1 。
ケース 3: 以下の場合、木の高さは縮みます。ターゲット キーが内部ノードにあり、キーの削除によりノード内のキーが少なくなる (必要な最小数より少ない) 場合は、順序どおりの先行キーと後続キーを探します。両方の子が最小限の数のキーを持っている場合、借用は行われません。これはにつながります 事例2(3) つまり、子ノードをマージします。
鍵を借りる兄弟を再度探します。ただし、兄弟が最小数のキーでも構成されている場合は、親ノードとともにノードを兄弟とマージし、要件に従って子ノードを配置します (昇順)。
指定された B ツリーからデータ要素 10 を削除する例を使用して、このケースを視覚化してみましょう。
図 4.6: Bツリーからリーフノードキー(10)を削除する
上記の例の時間計算量は、キーを削除する必要がある場所によって異なります。したがって、B ツリーでの削除操作の時間計算量は次のようになります。 O(ログ?ン) 。
結論
このチュートリアルでは、B ツリーについて学習し、そのさまざまな操作をさまざまな例で視覚化しました。また、B ツリーのいくつかの基本的なプロパティとルールも理解しました。