B 树利用了空间局部性原理,对树的结构进行优化,使得即便树存放在磁盘上也能有不错的访问性能。下面我们来讨论最常见的 $\text {B}^+$ 树。

我们结合下图例子,理解一个 M=5 阶的 B+ 树的性质:

阶:一个树的最大子节点书。

  1. 数据只存放在叶子上。

    内部结点存放的是关键字,都是用来索引的。

  2. 中间结点最多存放 M-1 个关键字。

    这是因为一旦等于 M 个关键字,说明这个节点太满了,需要进行分割。

    关键字 i 代表 子树 i + 1 中的最小键。

    举个例子,下面的关键字 41,代表 41 右边那条线所指出的子树的最小值是 41。

    image-20211130224608638

  3. 根要么是叶子,要么有 2~M 个子节点。

    这确保了任意个元素都能存进去。

  4. 中间结点(除了根),拥有 $\lceil M / 2\rceil\sim M$ 个子结点。

    这是因为