B+ 树通常用于数据库和操作系统的文件系统中,对内存与磁盘之间的交互提供了非常大的遍历,是一种常见的存储在磁盘的索引结构。

B+ 树的概念

基本概念

B+ 树是 B 树的一种变体,从某个程度上看,B+ 树可以认定是 B 树的升级版。

在 B+ 树中,关键字只存储在叶子结点,非叶子结点存储的是叶子结点所存储关键字的部分拷贝,所有的叶子结点也都在相同的高度,叶子结点本身按关键字大小从小到大链接。

因此,相对于 B 树而言,B+ 树更充分地利用了结点的空间,让查询速度更加稳定,其速度完全接近于二分查找。

B+ 树结构

特性

B+ 树拥有 B 树的大部分特性,但也具有独特的、与 B 树不同的特性,不同的地方有以下两点:

  • B+ 树的非叶子结点不直接存储数据的指针,所有数据的指针都存储在叶子结点
  • B+ 树叶子结点存储的数据从小到大有序排列,且相邻叶子结点之间具有链接

与 B 树的区别

与 B 树相比较,B+ 树具有以下特点:

  • B+ 树的非叶子结点不直接存储数据,存储的索引更多,树的层级更少,查询的速度更快
  • B+ 树所有数据的指针都存储在叶子结点,因此每次查找到数据的次数都相同,查询速度更稳定
  • B+ 树所有的叶子结点之间具有链接,构成了一个有序链表,查询范围区间的数据更方便
  • B+ 树遍历所有数据时只需要遍历所有叶子结点即可,相对 B 树遍历更快

为什么使用 B+ 树作为索引结构?

索引的本质是一种用于快速查找记录的数据结构,常见有二叉查找树、平衡二叉树、哈希表、B 树和 B+ 树等索引存储结构。

每一种索引结构都有其对应的应用场景,易用性也是选择的标准之一,这里讨论一下为什么选用 B+ 树作为索引存储结构。

为什么不采用二叉查找树?

二叉查找树索引

使用普通的二叉树查找作为索引结构具有一个致命的问题:当一直插入数据的时候,有可能会退化成链表结构,时间复杂度也会从 $O(\log n)$ 退化到 $O(n)$。

因此,普通的二叉查找树比较适合数据基本没有变动的情况,这样查找效率不会发生较大的变化。

为什么不采用平衡二叉树?

平衡二叉树索引

为了解决普通二叉查找树有可能退化成链表的问题,可以使用自平衡的二叉查找树代替,如 AVL 树、红黑树等。

红黑树常见的一种自平衡二叉查找树,但是也有一个问题:红黑树是一个近似平衡的二叉树,当数据量较大的时候,会出现树层级较大的情况。

当数据量非常大时,索引占用的空间也会非常大,索引还是得存储在磁盘上,如果树的层级较大,则进行磁盘 IO 的次数就会越多,性能就会越差。

因此,红黑树不适合作为存储在磁盘上的索引结构。

为什么不采用哈希表?

哈希表是一个支持快速查找的数据结构,其查找的时间复杂度是 $O(1)$,其也是最常见的索引存储结构之一。

但是哈希表也有其缺点,就是只存储键值对应关系的哈希表不支持范围查询,如果要做范围查询,需要做全量的数据扫描才行。

当然,如果是具有排序功能的哈希表,会非常适合作为存储在内存中的索引结果,如 Java 中的 TreeMap 对象。

为什么不采用 B 树?

使用 B 树可以解决红黑树层级较大的问题,通过一个结点可以存储多个元素,树变得更加矮胖,使得树的层级变得可控。

而且,通过给一个结点存储一页的数据量,最大化地优化操作系统和磁盘的交互,解决了多次磁盘 IO 的问题。

但是对应 B+ 树而言,B 树的层级仍然会比 B+ 树的高,且范围查询没有 B+ 树方便,这是舍弃 B 树而选择 B+ 树的主要原因。

当然,也有使用 B 树作为索引结构的数据库,如 MongoDB 等。