Data Structures Algorithms 简明教程

B+ Trees

B+ 树是 B 树的扩展，旨在使插入、删除和搜索操作更有效率。

B+ 树的性质与 B 树的性质相似，不同之处在于 B 树可以在所有内部节点和叶子节点中存储键和记录，而 B+ 树则在叶子节点中存储记录，在内部节点中存储键。B+ 树的一个显著特性是，所有叶子节点都以单链表格式彼此连接，并且提供了一个数据指针来指向磁盘文件中存在的数据。这有助于以相等数量的磁盘访问来获取记录。

由于主内存的大小有限，因此 B+ 树充当了存储在主内存中无法存储的记录的数据存储。为此，内部节点存储在主内存中，而叶子节点存储在辅助内存存储中。

bplus trees

Properties of B+ trees

  1. B+ 树中的每个节点，根节点除外，最多容纳 m 个子节点和 (m-1) 个键，最少容纳 $\mathrm{\left \lceil \frac{m}{2}\right \rceil}$ 个子节点和 $\mathrm{\left \lceil \frac{m-1}{2}\right \rceil}$ 个键，因为树的阶数为 m 。

  2. 根节点必须至少有两个子节点和至少一个搜索键。

  3. B 树中的所有路径都必须在同一级别结束，即叶子节点必须在同一级别。

  4. B+ 树始终维护已排序数据。

Basic Operations of B+ Trees

B+ 树支持的操作是插入、删除和搜索，所有操作的时间复杂度为 O(log n) 。

它们与 B 树操作类似，因为将数据存储在此两种数据结构中的基本思想是相同的。然而，两者的不同之处在于，与 B 树不同，数据仅存储在 B+ 树的叶结点中。

Insertion operation

B+ 树的插入从叶结点开始。

Step 1 − 计算要添加到 B+ 树结点上的最大和最小键数。

calculate number of keys

Step 2 − 将元素一个接一个地插入叶结点，直到超过最大键数。

Insert elements

Step 3 − 将结点分成两半，其中左子结点包含最小键数，而剩余键存储在右子结点中。

node split

Step 4 − 但是，如果内部结点也超过了最大键属性，则将结点分成两半，其中左子结点包含最小键，而剩余键存储在右子结点中。但是，将右子结点中最小的数字设为父结点。

insert into b plus tree

Step 5 − 如果叶结点和内部结点都具有最大键，则它们都会以类似的方式分割，并且右子结点中的最小键添加到父结点中。

b plus tree order 4

Example

以下是该操作在各种编程语言中的实现 −