B+树：搜索、插入和删除 Opera系统蒸发散
陈莎拉
什么是 B+ 树？
A B+ 树 主要用于实现多级动态索引。与 B 树相比，B+ 树仅在叶节点存储数据指针，这使得搜索过程更加准确快捷。
B+ 树的规则
以下是B+树的基本规则。
- 叶子用于存储数据记录。
- 记录存储在树的内部节点中。
- 如果目标键值小于内部节点，则沿着其左侧的指针继续查找。
- 如果目标键值大于或等于内部节点，则沿着其右侧的指针继续前进。
- 根至少有两个子节点。
为什么使用 B+ 树
以下是使用 B+ 树的原因：
- 键的主要作用是引导用户找到正确的页面，从而帮助用户进行搜索。
- B+树使用“填充系数”来管理树的增加和减少。
- 在 B+ 树中，许多键可以很容易地放在内存页面上，因为它们没有与内部节点关联的数据。因此，它将快速访问叶节点上的树数据。
- 对所有元素进行全面完整扫描只需要一次线性扫描，因为 B+ 树的所有叶节点都相互连接。
B+ 树与 B 树
以下是 B+ 树和 B 树的主要区别。
| B+ 树 | B 树 |
|---|---|
| 搜索键可以重复。 | 搜索关键字不能重复。 |
| 数据仅保存在叶节点上。 | 叶节点和内部节点都可以存储数据。 |
| 存储在叶节点上的数据使得搜索更加准确、快捷。 | 由于数据存储在叶子节点和内部节点上，因此搜索速度较慢。 |
| 删除操作并不困难，因为元素只会从叶节点中移除。 | 删除元素是一个复杂且耗时的过程。 |
| 链接的叶节点使搜索变得高效且快速。 | 您不能链接叶节点。 |
搜索 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% 的元素被移动到新叶子进行存储。
- 新叶子的父节点与最小键值和树中的新位置精确链接。
- 将父节点拆分到更多位置以确保其得到充分利用。
- 为了获得更好的结果，中心键与该叶子的顶级节点相关联。
- 直到找不到顶层节点为止，继续迭代上述步骤中解释的过程。
插页 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 作为指针元素。
- 现在，树的正确层级结构已经创建完成，剩余的数据值由 kee 进行相应的调整。ping 请记住适用于右侧键值节点的大于或等于值的规则。
删除 OperaTION
B+ 树中删除过程的复杂性超过了插入和搜索功能的复杂性。
从 B+ 树中删除元素时适用以下算法：
- 首先，我们需要找到树中保存键和指针的叶子条目，然后如果叶子条目满足记录删除的确切条件，则从树中删除该叶子条目。
- 如果叶节点仅满足半满的条件，则操作完成；否则，叶节点具有最小条目数，不能删除。
- 左右两侧的其他链接节点可以清空任何条目，然后将其移至叶节点。如果这些条件不满足，则应将叶节点与其在树状结构中的链接节点合并。
- 当叶节点与其左右相邻节点合并时，叶节点或指向顶层节点的链接邻居中的值条目将被删除。
上面的例子说明了从特定阶的 B+ 树中删除元素的过程。
- 首先，在树中确定要删除元素的确切位置。
- 在此，待删除的元素只能在叶节点级别准确识别，而无法在索引位置准确识别。因此，删除该元素不会影响删除规则，而删除规则正是最小键值所代表的。
- 在上面的例子中，我们必须从树中删除 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 及其父节点中的值，则从兄弟节点借用键。
