B+树实现详细步骤解析 _B+树实现

本文概述

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

B +树是B树的扩展, 它允许有效的插入, 删除和搜索操作。
在B树中, 键和记录都可以存储在内部节点和叶节点中。而在B +树中, 记录（数据）只能存储在叶节点上, 而内部节点只能存储键值。
B +树的叶节点以单链接列表的形式链接在一起, 以使搜索查询更高效。
B +树用于存储无法存储在主存储器中的大量数据。由于总是限制主存储器的大小, 因此B +树的内部节点（访问记录的键）存储在主存储器中, 而叶节点存储在辅助存储器中。
B +树的内部节点通常称为索引节点。下图显示了3级的B +树。

文章图片
B +树的优势

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

文章图片
B树VS B +树

序号	B树	B +树
1	搜索键不能重复存储。	可能存在冗余搜索键。
2	数据可以存储在叶节点以及内部节点中	数据只能存储在叶节点上。
3	由于可以在内部节点以及叶节点上找到数据, 因此搜索某些数据的过程较慢。	由于只能在叶节点上找到数据, 因此搜索相对较快。
4	内部节点的删除是如此复杂且耗时。	删除永远不会是一个复杂的过程, 因为元素将始终从叶节点中删除。
5	叶节点不能链接在一起。	叶子节点链接在一起, 使搜索操作更高效。

插入B +树步骤1：将新节点插入为叶节点
步骤2：如果叶子没有所需的空间, 请分割节点并将中间节点复制到下一个索引节点。
步骤3：如果索引节点没有所需的空间, 请分割该节点并将中间元素复制到下一个索引页。
范例：
将值195插入下图所示的5阶B +树中。

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

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

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

文章图片
B +树中的删除步骤1：从叶子中删除密钥和数据。
步骤2：如果叶节点包含的元素数量少于最小数量, 则向下合并该节点及其同级元素, 并删除它们之间的键。
步骤3：如果索引节点包含的元素数量少于最小数量, 则将该节点与同级元素合并, 然后向下移动它们之间的键。
例
从下图所示的B +树中删除密钥200。