B+ TREE : 検索、挿入、削除 Opera例

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

A B+ ツリー 主に、複数のレベルで動的インデックスを実装するために使用されます。B ツリーと比較すると、B+ ツリーはツリーのリーフノードにのみデータポインターを格納するため、検索処理がより正確かつ高速になります。

B+ ツリーのルール

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

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

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

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

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

B+ ツリー vs. B ツリー

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

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

検索 Opera生産

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

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

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

検索 Operaアルゴリズム

 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."

出力:

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

インセット Opera生産

挿入操作には次のアルゴリズムが適用されます。

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

インセット Operaアルゴリズム

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 を追加します。
ここで、ツリーの右側の階層が作成され、右側のキーと値のノードに対する値以上の適用ルールを念頭に置いて、残りのデータ値がそれに応じて調整されます。

削除 Opera生産

B+ ツリーの削除手順の複雑さは、挿入および検索機能の複雑さを上回ります。

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

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

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

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

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

削除 Operaアルゴリズム

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

よろしければ：