データ構造の B TREE: 検索、挿入、削除 Opera例

B ツリーのルール

ここでは、B_Tree を作成するための重要なルールを説明します。

• すべてのリーフは同じレベルで作成されます。
• 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-Treeを使用する理由は次のとおりです。

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

Bツリーの歴史

• データはブロック内のディスクに保存されます。このデータは、メインメモリ（またはRAM）に持ち込まれた場合、データ構造と呼ばれます。
• データが膨大な場合、ディスク内の 1 つのレコードを検索するにはディスク全体を読み取る必要があり、ディスク アクセス頻度とデータ サイズが高いため、時間とメイン メモリの消費量が増加します。
• これを克服するために、レコードが存在するブロックに基づいてレコードのレコード参照を保存するインデックス テーブルが作成されます。これにより、時間とメモリの消費が大幅に削減されます。
• 膨大なデータがあるため、マルチレベルのインデックス テーブルを作成できます。
• B ツリーを使用してマルチレベル インデックスを設計し、自己バランス型でデータを並べ替えることができます。

検索 Opera生産

検索操作は、B ツリー上で最も単純な操作です。

次のアルゴリズムが適用されます。

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

インセット Opera生産

B ツリーは自己均衡型ツリーであるため、任意のノードだけにキーを強制的に挿入することはできません。

次のアルゴリズムが適用されます。

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

TIP	挿入アルゴリズムに関して、次のことは真実ではありません。 ノードがいっぱいであるため、ノードが分割され、新しい値が挿入されます。

上記の例では：

• ノード内の適切な位置でキーを検索します。
• ターゲットノードにキーを挿入し、ルールを確認します
• 挿入後、ノードには最小数 (1) 以上のキーがありますか? この場合、はい、そうです。 次のルールを確認してください。
• 挿入後、ノードには最大数の 3 を超えるキーが含まれていますか? この場合、いいえ、そうではありません。 これは、B ツリーがルールに違反しておらず、挿入が完了したことを意味します。

上記の例では：

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

上記の例では：

• ノードのキーが最大値未満です
• 1 が 3 の隣に挿入されていますが、昇順ルールに違反しています
• これを修正するには、キーを並べ替えます。

同様に、13 と 2 はノードの最大キー未満ルールを満たすため、ノードに簡単に挿入できます。

上記の例では：

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

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

削除 Opera生産

削除操作には、挿入操作や検索操作よりも多くのルールがあります。

次のアルゴリズムが適用されます。

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

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

• Target リーフノードに min 個以上のキーがあります。
• これを削除してもB Treeの所有権を侵害するものではありません
• Target リーフノードにあり、キーノードは最小である
• これを削除するとB Treeの所有権を侵害することになります
• Target ノードは、すぐ左のノードまたはすぐ右のノード（兄弟）からキーを借りることができます。
• 兄妹は言うだろう はい 最小数を超えるキーがある場合
• キーは親ノードから借用され、最大値は親に転送され、親ノードの最大値はターゲットノードに転送され、ターゲット値が削除されます
• Target リーフノードにありますが、兄弟ノードに最小数を超えるキーはありません
• キーを検索する
• 兄弟ノードと最小限の親ノードをマージします。
• キーの合計が最小値を超えるようになります
• ターゲットキーは最小限の親ノードに置き換えられます

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

• 順序どおりの先行者または順序どおりの後続のいずれかを選択します
• 順序どおりの先行者の場合、その左のサブツリーから最大のキーが選択されます。
• 次の後継者の場合、その右サブツリーからの最小キーが選択されます
• ターゲット キーの順序どおりの先行キーに最小キーよりも多くのキーがある場合にのみ、ターゲット キーを順序どおりの先行キーの最大値に置き換えることができます。
• ターゲット キーの順序どおりの先行キーに最小キーを超えるキーがない場合は、順序どおりの後続キーの最小キーを探します。
• ターゲット キーの順序どおりの先行キーと後続キーの両方のキーが min 未満の場合、先行キーと後続キーをマージします。

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

• 順序どおりの先行サブツリーの最大の要素と置換します。
• 削除後、ターゲットのキーが最小値未満の場合、ターゲット ノードは兄弟の親を介して兄弟から最大値を借用します。
• 親の最大値はターゲットによって取得されますが、兄弟の最大値のノードも使用されます。

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

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

上記の例では：

• ターゲット ノードには削除するターゲット キーがあります
• ターゲットノードには、最小キー以上のキーがあります
• キーを削除するだけです

上記の例では：

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

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

• ターゲット ノードは、順序どおりの後続ノード (右の兄弟) を持たないため、直接の兄弟 (この場合は順序どおりの先行ノード (左の兄弟)) からキーを借用します。
• Inorderの前任者の最大値は親に転送され、親は最大値をターゲットノードに転送します（以下の図を参照）

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

• ターゲット ノードは、順序どおりの先行ノード (左の兄弟) が最小キーと等しいキーを持っているため、直接の兄弟 (この場合は順序どおりの後続ノード) (右の兄弟) からキーを借用します。
• 順序後続ノードの最小値が親に転送され、親は最大値をターゲット ノードに転送します。

以下の例では、ターゲット ノードには、ターゲット ノードにキーを与えることができる兄弟がありません。 したがって、統合が必要です。

そのようなキーを削除する手順を参照してください：

• ターゲット ノードを親キーとともにその直接の兄弟のいずれかとマージします
• 親ノードからのキーは、マージする XNUMX つのノード間の兄弟となるように選択されます。
• マージされたノードからターゲットキーを削除します

削除 Opera擬似コード

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 ツリーから削除されます。

まとめ

• B ツリーは、ディスクからのデータの検索、挿入、削除を効率化するための自己バランス型データ構造です。
• B ツリーは指定された程度によって規制されます
• B ツリーのキーとノードは昇順に配置されます。
• B ツリーの検索操作は最も単純なもので、常にルートから開始され、ターゲット キーがノード値より大きいか小さいかをチェックすることから始まります。
• B ツリーの挿入操作はかなり詳細で、最初にターゲット キーの適切な挿入位置を見つけて挿入し、さまざまなケースに対して B ツリーの有効性を評価し、それに応じて B ツリー ノードを再構築します。
• B ツリーの削除操作では、まず削除するターゲット キーを検索し、それを削除し、ターゲット ノード、兄弟、親の最小キーと最大キーなどのいくつかのケースに基づいて有効性を評価します。