B+树实现详细步骤解析

本文概述

• B +树的优势
• B树VS B +树
• 插入B +树
• B +树中的删除

B +树是B树的扩展, 它允许有效的插入, 删除和搜索操作。

在B树中, 键和记录都可以存储在内部节点和叶节点中。而在B +树中, 记录（数据）只能存储在叶节点上, 而内部节点只能存储键值。

B +树的叶节点以单链接列表的形式链接在一起, 以使搜索查询更高效。

B +树用于存储无法存储在主存储器中的大量数据。由于总是限制主存储器的大小, 因此B +树的内部节点（访问记录的键）存储在主存储器中, 而叶节点存储在辅助存储器中。

B +树的内部节点通常称为索引节点。下图显示了3级的B +树。

B +树的优势

1. 可以在相同数量的磁盘访问中提取记录。
2. 与B树相比, 树的高度保持平衡并且较小。
3. 我们可以依次或直接访问B +树中存储的数据。
4. 键用于索引。
5. 由于数据仅存储在叶节点上, 因此搜索查询速度更快。

B树VS B +树

插入B +树

步骤1：将新节点插入为叶节点

步骤2：如果叶子没有所需的空间, 请分割节点并将中间节点复制到下一个索引节点。

步骤3：如果索引节点没有所需的空间, 请分割该节点并将中间元素复制到下一个索引页。

范例：

将值195插入下图所示的5阶B +树中。

190将在190之后插入195的右子树中。将其插入所需的位置。

该节点包含的元素数量大于最大数量, 即大于4, 因此将其拆分并将中间节点放置到父节点上。

现在, 索引节点包含6个子节点和5个键, 这违反了B +树的属性, 因此我们需要对其进行拆分, 如下所示。

B +树中的删除

步骤1：从叶子中删除密钥和数据。

步骤2：如果叶节点包含的元素数量少于最小数量, 则向下合并该节点及其同级元素, 并删除它们之间的键。

步骤3：如果索引节点包含的元素数量少于最小数量, 则将该节点与同级元素合并, 然后向下移动它们之间的键。

例

从下图所示的B +树中删除密钥200。

在195之后, 在190的右子树中显示200。删除它。

通过使用195、190、154和129合并两个节点。

现在, 元素120是节点中存在的违反B +树属性的单个元素。因此, 我们需要使用60、78、108和120进行合并。

现在, B +树的高度将减少1。