个性化阅读
专注于IT技术分析

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+树插入1

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

B+树插入2

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

B+树插入3

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

B+树插入4

B +树中的删除

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

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

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

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

B+树删除1

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

B+树删除2

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

B+树删除3

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

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

B+树删除4
赞(0)
未经允许不得转载:srcmini » B+树实现详细步骤解析

评论 抢沙发

评论前必须登录!