B+树实现详细步骤解析

本文概述

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

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

文章图片
B树VS B +树
序号 B树 B +树
1 搜索键不能重复存储。 可能存在冗余搜索键。
2 数据可以存储在叶节点以及内部节点中 数据只能存储在叶节点上。
3 由于可以在内部节点以及叶节点上找到数据, 因此搜索某些数据的过程较慢。 由于只能在叶节点上找到数据, 因此搜索相对较快。
4 内部节点的删除是如此复杂且耗时。 删除永远不会是一个复杂的过程, 因为元素将始终从叶节点中删除。
5 叶节点不能链接在一起。 叶子节点链接在一起, 使搜索操作更高效。
插入B +树 步骤1:将新节点插入为叶节点
步骤2:如果叶子没有所需的空间, 请分割节点并将中间节点复制到下一个索引节点。
步骤3:如果索引节点没有所需的空间, 请分割该节点并将中间元素复制到下一个索引页。
范例:
将值195插入下图所示的5阶B +树中。
B+树实现详细步骤解析

文章图片
190将在190之后插入195的右子树中。将其插入所需的位置。
B+树实现详细步骤解析

文章图片
该节点包含的元素数量大于最大数量, 即大于4, 因此将其拆分并将中间节点放置到父节点上。
B+树实现详细步骤解析

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

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

从下图所示的B +树中删除密钥200。
B+树实现详细步骤解析

文章图片
在195之后, 在190的右子树中显示200。删除它。
B+树实现详细步骤解析

文章图片
通过使用195、190、154和129合并两个节点。
B+树实现详细步骤解析

文章图片
现在, 元素120是节点中存在的违反B +树属性的单个元素。因此, 我们需要使用60、78、108和120进行合并。
【B+树实现详细步骤解析】现在, B +树的高度将减少1。
B+树实现详细步骤解析

文章图片

    推荐阅读