B+ TREE : 検索、挿入、削除操作の例

B+ ツリーとは何ですか?

A B+ ツリー 主に、複数のレベルで動的インデックス作成を実装するために使用されます。 B- ツリーと比較して、B+ ツリーはツリーの葉ノードにのみデータ ポインタを保存するため、より多くの検索プロセスがより正確かつ高速になります。

B+ ツリーのルール

B+ Tree の重要なルールは次のとおりです。

  • リーフはデータ レコードを保存するために使用されます。
  • ツリーの内部ノードに保存されます。
  • ターゲット キーの値が内部ノードより小さい場合は、そのすぐ左側のポイントが追跡されます。
  • ターゲット キーの値が内部ノード以上の場合は、その右側のポイントが追跡されます。
  • ルートには少なくとも XNUMX つの子があります。

B+ ツリーを使用する理由

B+ Tree を使用する理由は次のとおりです。

  • キーは主に、適切なリーフに誘導することで検索を支援するために使用されます。
  • B+ Treeでは「フィルファクター」を利用してツリーの増減を管理します。
  • B+ ツリーでは、内部ノードに関連付けられたデータがないため、多数のキーをメモリのページに簡単に配置できます。 したがって、リーフ ノード上のツリー データに迅速にアクセスします。
  • B+ ツリーのすべてのリーフ ノードは相互にリンクされているため、すべての要素の包括的なフル スキャンを行うツリーには XNUMX 回の線形パスだけが必要です。

B+ ツリー vs. B ツリー

B+ ツリーと B ツリーの主な違いは次のとおりです。

B+ ツリー Bツリー
検索キーは繰り返して使用できます。 検索キーは重複できません。
データはリーフ ノードにのみ保存されます。 リーフノードと内部ノードの両方にデータを保存できる
リーフ ノードにデータが保存されると、検索がより正確かつ高速になります。 Searching は、リーフおよび内部ノードにデータが保存されているために遅くなります。
要素はリーフ ノードから削除されるだけなので、削除は難しくありません。 要素の削除は複雑で時間のかかるプロセスです。
リンクされたリーフ ノードにより、検索が効率的かつ迅速になります。 リーフノードをリンクすることはできません。

検索操作

B+ Tree では、検索は実行するのが最も簡単な手順の XNUMX つであり、そこから迅速かつ正確な結果が得られます。

次のことwing 検索アルゴリズムが適用されます:

  • 必要なレコードを見つけるには、次のコマンドを実行する必要があります。 二分探索 ツリー内の利用可能なレコードについて。
  • 検索キーと完全に一致した場合、対応するレコードがユーザーに返されます。
  • 親ノード、現在のノード、またはリーフ ノードの検索で正確なキーが見つからない場合は、「見つからないメッセージ」がユーザーに表示されます。
  • 検索プロセスを再実行すると、より適切で正確な結果が得られます。

検索操作アルゴリズム

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

出力:

正確なキーに対して一致したレコード セットがユーザーに表示されます。他のwise、失敗した試行がユーザーに表示されます。

挿入操作

次のことwing アルゴリズムは挿入操作に適用できます。

  • ノード内の要素の 50% は、保管のために新しいリーフに移動されます。
  • 新しいリーフの親は、最小キー値とツリー内の新しい位置に正確にリンクされます。
  • 完全に利用される場合に備えて、親ノードをさらに多くの場所に分割します。
  • ここで、より良い結果を得るために、中央のキーがそのリーフの最上位ノードに関連付けられます。
  • 最上位ノードが見つからなくなるまで、上記の手順で説明したプロセスを繰り返し続けます。

挿入操作アルゴリズム

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. Else, divide the node into more locations to fit more records.
      a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
      b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
      c. Divide the top-level node if it gets full of keys and addresses.
          i. Similarly,  insert a key in the center of the top-level node in the hierarchy of the Tree.
     d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore. 

3) Build a new top-level root node of 1 Key and 2 indicators.  

出力:

アルゴリズムによって要素が決定され、必要なリーフ ノードに正常に挿入されます。

挿入操作

上記の B+ ツリーのサンプル例は、以下の手順で説明されています。

  • まず、3 つのノードがあり、最初の 3 つの要素 (1、4、および 6) がノード内の適切な場所に追加されます。
  • 一連のデータの次の値は 12 で、これをツリーの一部にする必要があります。
  • これを実現するには、ノードを分割し、ポインター要素として 6 を追加します。
  • ここで、ツリーの右側の階層が作成され、右側のキーと値のノードに対する値以上の適用ルールを念頭に置いて、残りのデータ値がそれに応じて調整されます。

操作を削除

コムplexB+ ツリーの削除手順は、挿入および検索機能を上回ります。

次のことwing このアルゴリズムは、B+ ツリーから要素を削除するときに適用できます。

  • まず、キーとポインタを保持しているツリー内のリーフ エントリを見つける必要があります。 、リーフがレコード削除の正確な条件を満たしている場合、ツリーからリーフ エントリを削除します。
  • リーフノードが半分しか満たされていないという十分な要素を満たしていない場合、操作は完了します。他のwise、リーフ ノードには最小限のエントリがあり、削除できません。
  • 右側と左側にある他のリンクされたノードは、エントリを空にしてからリーフに移動できます。 これらの基準が満たされていない場合は、ツリー階層内のリーフ ノードとそのリンク ノードを結合する必要があります。
  • リーフ ノードをその右側または左側の隣接ノードとマージすると、最上位ノードを指すリーフ ノードまたはリンクされた隣接ノードの値のエントリが削除されます。

操作を削除

上の例は、特定の順序の B+ ツリーから要素を削除する手順を示しています。

  • まず、削除する要素の正確な位置がツリー内で特定されます。
  • ここで、削除される要素は、インデックスの配置ではなく、リーフ レベルでのみ正確に識別できます。 したがって、最小限のキーの値である削除ルールに影響を与えることなく、要素を削除できます。

操作を削除

  • 上の例では、ツリーから 31 を削除する必要があります。
  • Index と Leaf で 31 のインスタンスを見つける必要があります。
  • 31 はインデックス ノード レベルとリーフ ノード レベルの両方で使用できることがわかります。 したがって、両方のインスタンスから削除します。
  • ただし、42 を指すインデックスを埋める必要があります。次に、25 未満の右側の子に注目し、最小値を取得して、それをインデックスとして配置します。 したがって、42 が唯一の値として存在するため、それがインデックスになります。

削除操作のアルゴリズム

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) If n has at least ceil(m/2) keys, done!
            ii) If n has less than ceil(m/2) keys,
                If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

出力:

キー「K」が削除され、必要に応じて n とその親ノードの値を調整するために兄弟からキーが借用されます。

まとめ

  • B+ ツリーは自己バランス調整機能を備えています。 データ構造 正確かつ高速なSE実行のためにarchiNG、データの挿入および削除プロシージャ
  • リンクされたツリー構造を経由することで効率的に実行できるため、完全なデータまたは部分的なデータを簡単に取得できます。
  • B+ ツリー構造は、保存されるレコード数の増減に応じて拡大または縮小します。
  • リーフ ノードにデータを保存し、その後内部ノードを分岐すると、明らかにツリーの高さが短くなり、ディスクの入出力操作が減り、最終的にストレージ デバイス上の消費スペースが大幅に減ります。