B+ 树：搜索、插入和删除 Operations 示例
陈莎拉
什么是 B+ 树？
A B+ 树 主要用于实现多级动态索引。与B-Tree相比，B+ Tree只将数据指针存储在Tree的叶子节点上，这使得搜索过程更加准确和快速。
B+ 树的规则
以下是 B+ 树的基本规则。
- 叶子用于存储数据记录。
- 它存储在树的内部节点中。
- 如果目标键值小于内部节点，则跟随其左侧的点。
- 如果目标键值大于或等于内部节点，则跟随其右侧的点。
- 根至少有两个子节点。
为什么使用 B+ 树
以下是使用 B+ 树的原因：
- 键主要用于引导至正确的叶子来帮助搜索。
- B+ 树使用“填充因子”来管理树的增加和减少。
- 在 B+ 树中，许多键可以很容易地放在内存页面上，因为它们没有与内部节点关联的数据。因此，它将快速访问叶节点上的树数据。
- 对所有元素进行全面扫描只需要一次线性遍历，因为 B+ 树的所有叶节点都相互链接。
B+ 树与 B 树
以下是 B+ 树与 B 树之间的主要区别
| B+ 树 | B 树 |
|---|---|
| 搜索键可以重复。 | 搜索关键字不能重复。 |
| 数据仅保存在叶节点上。 | 叶子节点和内部节点都可以存储数据 |
| 存储在叶节点上的数据使得搜索更加准确、快捷。 | 由于数据存储在 Leaf 和内部节点上，因此搜索速度很慢。 |
| 删除并不困难，因为元素仅从叶节点中删除。 | 删除元素是一个复杂且耗时的过程。 |
| 链接的叶节点使搜索变得高效且快速。 | 您不能链接叶节点。 |
搜索 OperaTION
在 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."
输出:
向用户显示与精确键匹配的记录集；否则，向用户显示失败的尝试。
插页 OperaTION
以下算法适用于插入操作：
- 节点中 50% 的元素被移动到新叶子进行存储。
- 新叶子的父节点与树中的最小键值和新位置准确链接。
- 将父节点拆分到更多位置以确保其得到充分利用。
- 现在，为了获得更好的结果，中心键与该 Leaf 的顶级节点相关联。
- 直到找不到顶层节点为止，继续迭代上述步骤中解释的过程。
插页 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 作为指针元素。
- 现在，创建了树的右侧层次结构，并通过牢记右侧键值节点的等于或大于值的适用规则来相应地调整剩余的数据值。
删除 OperaTION
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+树结构随着存储记录数量的增加/减少而增大和缩小。
- 将数据存储在叶子节点上，然后进行内部节点的分支，明显缩短了树的高度，减少了磁盘的输入输出操作，最终消耗更少的存储设备空间。
