B+ 树

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

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

B+ 树的叶子节点通过单向链表连接在一起，以使搜索查询更有效。

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

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

B+ 树的优点

1. 记录可以以相等的磁盘访问次数获取。
2. 与 B 树相比，树的高度保持平衡且较低。
3. 我们可以顺序访问也可以直接访问存储在 B+ 树中的数据。
4. 键用于索引。
5. 搜索查询速度更快，因为数据仅存储在叶子节点中。

B 树与 B+ 树对比

B+ 树中的插入

步骤 1: 将新节点插入为叶子节点。

步骤 2: 如果叶子节点没有足够的空间，则分裂节点并将中间节点复制到下一个索引节点。

步骤 3: 如果索引节点没有足够的空间，则分裂节点并将中间元素复制到下一个索引页。

示例

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

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

该节点包含的元素多于最大允许元素数（即 4 个），因此分裂节点并将中位数节点向上移至父节点。

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

B+ 树中的删除

步骤 1: 从叶子节点删除键和数据。

步骤 2: 如果叶子节点包含的元素少于最小允许元素数，则将该节点与其兄弟节点合并，并删除它们之间的键。

步骤 3: 如果索引节点包含的元素少于最小允许元素数，则将该节点与其兄弟节点合并，并将它们之间的键向下移动。

示例

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

200 存在于 190 的右子树中，在 195 之后。将其删除。

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

现在，节点中只剩下元素 120，这违反了 B+ 树的性质。因此，我们需要使用 60、78、108 和 120 合并它。

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