データ構造におけるBツリー：検索、挿入、削除

⚡ スマートサマリー

データ構造におけるBツリーは、ディスク上での高速な検索、挿入、削除操作のためにデータをソート状態に保つ自己平衡型ツリーです。本書では、Bツリーのルール、歴史、検索、挿入、削除アルゴリズムを例を交えて解説します。

🌲 自己バランス： Bツリーは、すべての葉を同じ高さに保ち、あらゆる動作中もバランスを維持します。
🔢 オーダー (m): 次数mは、ノードあたりの最大子ノード数(m)と最大キー数(m-1)を設定します。
🔍 サーチ： 検索はルートから始まり、キーを比較しながら左右に移動します。
➕ インサート： 挿入処理は正しい位置を見つけ、完全なノードをその中央のキーから分割します。
➖ 削除： 削除処理は、借用とマージを用いて、リーフ、内部、ルートの各ケースを処理します。

Bツリーとは何ですか?

Bツリー Bツリーは、特定のルールに基づいてデータを検索、挿入、削除することで、より高速かつメモリ効率の良い処理を実現する自己平衡型データ構造です。これを実現するために、Bツリーを作成する際には以下のルールに従います。

Bツリーは、データ構造における特殊なツリーの一種です。1972年にマクレイトとベイヤーによって初めて導入され、「高さバランス型m分岐探索木」と名付けられました。Bツリーは、データをソートされた状態で保持するのに役立ち、挿入、検索、削除などの様々な操作を短時間で実行できます。

B ツリーのルール

Bツリーを作成する際の重要なルールは以下のとおりです。

すべてのリーフは同じレベルで作成されます。
Bツリーは、次数（「オーダー」とも呼ばれる）の数によって決定されます（プログラマーなどの外部アクターによって指定されます）。 m これからも。の値 m データが主に配置されているディスク上のブロックサイズによって異なります。
ノードの左側のサブツリーには、サブツリーの右側よりも小さい値が含まれます。これは、ノードも左から右へ昇順で並べ替えられることを意味します。
ルートノードおよびその子ノードが保持できるキーの最大数は、次の式で計算されます。 m − 1 例えば：
```
m = 4
max keys: 4 − 1 = 3
```

ルートを除くすべてのノードは、以下の最小数のキーを含まなければならない。 [m/2] − 1 例えば：
```
m = 4
min keys: 4/2 − 1 = 1
```
ノードが持つことができる子ノードの最大数は、その次数に等しくなります。 m.
ノードが持つことができる最小の子供は、注文の半分であり、M/2です（天井値が取られます）。
ノード内のすべてのキーは昇順にソートされます。

B ツリーを使用する理由

Bツリーを使用する理由は以下のとおりです。

ディスクへの読み取り回数を減らします。
Bツリーは、ディスク容量に応じてサイズ（つまり、子ノードの数）を調整するように簡単に最適化できます。
これは、大量のデータを処理するために特別に設計された手法です。
これはデータベースやファイルシステムにとって便利なアルゴリズムです。
大量のデータを読み書きする場合に最適な選択肢です。

Bツリーの歴史

データはディスク上にブロック単位で保存されます。このデータがメインメモリ（またはRAM）に読み込まれると、データ構造と呼ばれます。
膨大なデータの場合、ディスク上の1つのレコードを検索するにはディスク全体を読み込む必要があり、ディスクへのアクセス頻度とデータサイズが大きいため、時間とメインメモリの消費量が増加します。
この問題を解決するために、レコードが存在するブロックに基づいてレコードの参照を保存するインデックステーブルが作成されます。これにより、時間とメモリの消費量が大幅に削減されます。
膨大なデータがあるため、マルチレベルのインデックステーブルを作成できます。
多段階インデックスは、キーイングにBツリーを使用して設計できます。ping データは自己バランスのとれた方法でソートされた。

検索 Opera生産

検索操作はBツリー上で最も単純な操作です。以下のアルゴリズムが適用されます。

検索対象のキー（値）を「k」とする。
ルートから検索を開始し、再帰的に下方向に移動します。
kがルート値より小さい場合は左部分木を検索し、kがルート値より大きい場合は右部分木を検索します。
ノードに見つかった k がある場合は、単純にノードを返します。
k がノード内に見つからない場合は、より大きなキーを持つ子まで下に移動します。
k がツリー内に見つからない場合は、NULL を返します。

インサート Opera生産

Bツリーは自己平衡木であるため、任意のノードにキーを強制的に挿入することはできません。以下のアルゴリズムが適用されます。

検索操作を実行し、適切な挿入場所を見つけます。
新しいキーを適切な場所に挿入します。ただし、ノードにすでに最大数のキーがある場合は、次のようにします。
ノードは、新しく挿入されたキーとともに、中央の要素から分割されます。
中央の要素は、他の XNUMX つの子ノードの親になります。
ノードはキーを昇順に再配置する必要があります。

💡ヒント: 以下は挿入アルゴリズムについて正しい説明：「ノードが満杯なので分割され、その後新しい値が挿入される。」キーが最初に挿入され、最大キー数を超えた場合にのみノードが分割されます。

上記の例では：

ノード内の適切な位置でキーを検索します。
対象ノードにキーを挿入し、ルールを確認します。
挿入後、ノードのキーの数は最小数である1以上ですか？この場合、はい、そうです。次のルールを確認してください。
挿入後、ノードは最大キー数である3を超えていますか？この場合、超えていません。つまり、Bツリーはどのルールにも違反しておらず、挿入は完了しています。

上記の例では：

ノードがキーの最大数に達しました。
ノードは分割され、中央のキーが残りの2つのノードのルートノードになります。
キーの数が偶数の場合、中央のノードは左バイアスまたは右バイアスによって選択されます。

上記の例では：

ノードには最大キー数よりも少ないキーしか含まれていません。
1は3の隣に挿入されているが、昇順の規則に違反している。
この問題を解決するために、キーをソートします。

同様に、13と2はノードの「最大キー数未満」というルールを満たしているため、ノードに簡単に挿入できます。

上記の例では：

ノードには最大キーに等しいキーがあります。
キーはターゲットノードに挿入されますが、最大キー数のルールに違反しています。
ターゲットノードが分割され、左バイアスによる中央のキーが新しい子ノードの親になります。
新しいノードは昇順で配置されます。

同様に、上記のルールとケースに基づいて、残りの値を B ツリーに簡単に挿入できます。

削除 Opera生産

削除操作には、挿入操作や検索操作よりも多くのルールがあります。以下のアルゴリズムが適用されます。

検索操作を実行し、ノードの中から目的のキーを見つけます。
以下のセクションで説明するように、ターゲットキーの位置に基づいて3つの条件が適用されます。

対象キーがリーフノードにある場合

Target リーフノードにあり、最小キー数よりも多くのキーが存在します。これを削除しても、Bツリーの特性は損なわれません。
Target これはリーフノードにあり、最小キーノードを持っています。これを削除すると、Bツリーの特性に違反します。
ターゲットノードは、すぐ左のノードまたはすぐ右のノード（兄弟ノード）からキーを借りることができます。
兄妹は言うだろうはい最小キー数より多い場合。
キーは親ノードから借用され、最大値が親ノードに転送され、親ノードの最大値がターゲットノードに転送され、ターゲットの値が削除されます。
Target はリーフノードにありますが、兄弟ノードには最小数を超えるキーがありません。キーを検索し、兄弟ノードおよび親ノードの最小値とマージします。これでキーの合計数が最小値を超え、ターゲットキーは親ノードの最小値に置き換えられます。

ターゲットキーが内部ノードにある場合

順序通りの先行要素または後続要素のいずれかを選択してください。
順序通りの先行ノードの場合、その左部分木から最大のキーが選択されます。
順序後継者の場合、その右部分木から最小のキーが選択されます。
ターゲットキーの順序通りの先行キーが最小キー数より多い場合のみ、ターゲットキーを順序通りの先行キーの最大値で置き換えることができます。
ターゲットキーの順序通りの先行要素が最小キー数を超えていない場合は、順序通りの後続要素の最小キーを探します。
ターゲットキーの順序どおりの先行キーと後続キーの両方のキーが min 未満の場合、先行キーと後続キーをマージします。

ターゲットキーがルートノードにある場合

順序通りの先行部分木の最大要素に置き換えます。
削除後、ターゲットのキー数が最小値未満になった場合、ターゲットノードは兄弟ノードの親ノードを介して、兄弟ノードから最大値を借りる。
親ノードの最大値がターゲットノードに引き継がれますが、兄弟ノードの最大値も使用されます。

それでは、例を使って削除操作を理解しましょう。

上記の図は、Bツリーにおける削除操作のさまざまなケースを示しています。このBツリーは次数5であり、これは、どのノードも持つことができる子ノードの最小数が3、最大数が5であることを意味します。一方、どのノードも持つことができるキーの最小数と最大数は、それぞれ2と4です。

上記の例では：

対象ノードには、削除対象のキーが含まれています。
対象ノードは、最小キー数よりも多くのキーを持っています。
キーを削除するだけです。

上記の例では：

対象ノードのキーは最小キー数と等しいため、条件に違反することになるため、直接削除することはできません。

次の図は、このキーを削除する方法を説明しています。

ターゲットノードは、直近の兄弟ノード（この場合は順序上の先行ノード（左の兄弟ノード））からキーを借りることになります。なぜなら、ターゲットノードには順序上の後継ノード（右の兄弟ノード）が存在しないからです。
順序付けされた先行ノードの最大値が親ノードに転送され、親ノードはその最大値をターゲットノードに転送します（下図参照）。

次の例は、順序どおりの後続から値を必要とするキーを削除する方法を示しています。

ターゲットノードは、直近の兄弟ノード（この場合は順序上の後継ノード（右の兄弟ノード））からキーを借りる。なぜなら、その順序上の先行ノード（左の兄弟ノード）のキーが最小キーと等しいからである。
順序後続ノードの最小値が親に転送され、親は最大値をターゲットノードに転送します。

以下の例では、ターゲットノードには、そのキーをターゲットノードに渡すことができる兄弟ノードが存在しません。そのため、マージが必要です。このようなキーを削除する手順については、以下を参照してください。

対象ノードを、親キーとともに、その直近の兄弟ノードのいずれかとマージします。
2つのマージノードの間に位置する親ノードのキーが選択されます。
マージされたノードからターゲットキーを削除します。

削除 Opera擬似 Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

出力： 最大の要素が B ツリーから削除されます。

よくあるご質問

はい。AIツールを使えば、指定された順序で挿入、分割、削除の手順を段階的に図解したりアニメーション化したりできます。これにより、学習者はツリーがどのように再バランスされるかを理解できますが、各手順をBツリーのルールに照らし合わせて確認する必要があります。

Bツリーとその派生技術は、AIシステムが依存する大規模なデータセットやベクトルストアのインデックスを作成するため、トレーニングデータや埋め込みに対する検索が高速に行われます。ディスク読み取りを削減するためにBツリーを使用するのは、モデルではなくデータベースです。

二分探索木のノードは最大で2つの子と1つのキーを持ちます。Bツリーのノードは多くのキーと多くの子、キーを保持できます。ping ツリーが短く、ディスク読み取り回数を削減できるため、データベースやファイルシステムに最適です。

検索、挿入、削除の各処理は、キーの数をnとした場合、O(log n)の時間で実行されます。各ノードは多数のキーを保持するため、ツリー構造は浅くなり、ディスクアクセス回数は非常に少なくなります。

データ構造におけるBツリー：検索、挿入、削除