B+ツリー：検索、挿入、削除 Operaン
サラ・チェン
⚡ スマートサマリー
B+ツリーは、リンクされたリーフノードにのみデータポインタを格納する多階層の動的インデックスであり、検索の精度と速度を向上させます。本書では、B+ツリーのルール、Bツリーとの違い、検索、挿入、削除操作について解説します。
B+ ツリーとは何ですか?
A B+ ツリー B+ツリーは、主に複数レベルでの動的インデックス作成に利用されます。B-ツリーと比較して、B+ツリーはデータポインタをツリーのリーフノードにのみ格納するため、検索処理の精度と速度が向上します。
B+ ツリーのルール
以下は、B+ツリーに関する基本的なルールです。
- リーフはデータ レコードを保存するために使用されます。
- レコードはツリーの内部ノードに格納されます。
- ターゲットキーの値が内部ノードの値より小さい場合、そのノードのすぐ左にあるポインタが辿られます。
- ターゲットキーの値が内部ノードの値以上である場合、そのすぐ右隣のポインタが辿られます。
- ルートには少なくとも XNUMX つの子があります。
B+ ツリーを使用する理由
B+ツリーを使用する理由は以下のとおりです。
- キーは主に、適切なページへ誘導することで検索を支援するために使用されます。
- B+ツリーは、「フィルファクター」を使用してツリー内の増減を管理します。
- B+ ツリーでは、内部ノードに関連付けられたデータがないため、多数のキーをメモリのページに簡単に配置できます。 したがって、リーフ ノード上のツリー データに迅速にアクセスします。
- B+ツリーのすべての葉ノードは互いにリンクされているため、すべての要素を包括的にスキャンするには、1回の線形パスだけで済みます。
B+ ツリー vs. B ツリー
B+ツリーとBツリーの主な違いは以下のとおりです。
| B+ ツリー | Bツリー |
|---|---|
| 検索キーは繰り返して使用できます。 | 検索キーは重複できません。 |
| データはリーフ ノードにのみ保存されます。 | リーフノードと内部ノードの両方がデータを保存できます。 |
| リーフ ノードにデータが保存されると、検索がより正確かつ高速になります。 | リーフノードと内部ノードにデータが保存されているため、検索速度が遅くなります。 |
| 要素は末端ノードからのみ削除されるため、削除は難しくありません。 | 要素の削除は複雑で時間のかかるプロセスです。 |
| リンクされたリーフ ノードにより、検索が効率的かつ迅速になります。 | リーフノードをリンクすることはできません。 |
検索 Opera生産
B+ツリーでは、検索は最も簡単に実行できる手順の一つであり、迅速かつ正確な結果が得られます。
次の検索アルゴリズムが適用されます。
- 必要なレコードを見つけるには、次のコマンドを実行する必要があります。 二分探索 ツリー内の利用可能なレコードについて。
- 検索キーと完全に一致した場合、対応するレコードがユーザーに返されます。
- 親ノード、現在のノード、またはリーフノードで検索しても正確なキーが見つからない場合は、ユーザーに「見つかりません」というメッセージが表示されます。
- 検索プロセスを再実行すると、より適切で正確な結果が得られます。
検索 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. If 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を追加します。
- ここで、ツリーの右階層が作成され、残りのデータ値はそれに応じて調整されます。ping 右側のキーと値のノードに対して、等しいかそれ以上の値であるという適用ルールを念頭に置いてください。
削除 Opera生産
B+ ツリーの削除手順の複雑さは、挿入および検索機能の複雑さを上回ります。
B+ ツリーから要素を削除するときには、次のアルゴリズムが適用されます。
- まず、キーとポインタを保持しているツリー内のリーフエントリを特定し、そのリーフエントリがレコード削除の条件を完全に満たしている場合は、ツリーからリーフエントリを削除する必要があります。
- リーフノードが半分しかデータが入っていないという条件を満たしている場合、操作は完了します。そうでない場合、リーフノードには最小限のエントリしかなく、削除できません。
- 左右にリンクされた他のノードは、任意のエントリを削除してリーフノードに移動できます。これらの条件が満たされない場合は、ツリー階層内でリーフノードとそのリンクされたノードを結合する必要があります。
- リーフノードが左右の隣接ノードとマージされると、リーフノードまたはリンクされた隣接ノード内の、トップレベルノードを指す値のエントリは削除されます。
上記の例は、特定の次数を持つB+ツリーから要素を削除する手順を示しています。
- まず、削除する要素の正確な位置がツリー内で特定されます。
- ここでは、削除対象要素はインデックス位置ではなく、リーフレベルでのみ正確に識別できます。したがって、要素は削除ルール（最小キーの値）に影響を与えることなく削除できます。
- 上の例では、ツリーから 31 を削除する必要があります。
- インデックスとリーフの中で、31 のインスタンスを見つける必要があります。
- インデックスノードとリーフノードの両方で31が利用可能であることがわかります。したがって、両方のインスタンスから31を削除します。
- しかし、42を指すインデックスを埋める必要があります。次に、25以下の右側の子を見て、最小値を取得し、それをインデックスとして配置します。したがって、存在する唯一の値である42がインデックスになります。
削除 Operaアルゴリズム
1) Start at the root and go up to the 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とその親ノードの値を調整します。
