B+ 树的定义和 B 树是类似的，B+ 树在数据结构上进行了一定的改进，它的特性使得它的某些场景下教 B 树有了显著的优势。本文笔者将对 B+ 树的定义、特点以及应用进行详细解析。
定义
B+ 树和 B 树的定义是类似的，它们都是平衡多路搜索树，在文件系统和数据库系统中都有大量的应用。只不过 B+ 树有以下几点独特的属性：
- B+ 树的非叶子结点不包含值（value），只存储键（key）
- B+ 树的叶子结点之间是互相连接的，B+ 树叶子结点这一层构成了一个双向链表（Doubly linked list）
- B+ 树的叶子结点这一层存储了所有数据的 key-links pairs，而 B 树的所有数据是散布在整棵树中的，B 树的叶子结点这一层只存储了数据全集的一部分。
B+ 树的查找、添加、删除算法和 B 树是类似的，可以参考笔者的上一篇博客进行了解：深入理解 B-Tree | caffcen’s blog，在此不在赘述。
特性
对于阶数为 m 的 B+ 树，它拥有如下性质：
- 每个节点最多有
m个子节点。 - 每个节点最多有
m-1个键值。 - 每个内部节点至少有
⌈m/2⌉个子节点，根节点除外。 - 根节点至少有 2 个子节点。
- 所有叶子节点出现在同一层级上，叶子结点与叶子结点之间有双向引用，叶子结点这一层构成了一条双向链表。
- 一个具有
k个子节点的非叶节点包含k-1个键值。 - 叶子结点这一层存储了所有数据（所有的 key-link pairs）
B-Tree vs. B+ Tree
B 树和 B+ 树的区别对比，可以参考 Stack Overflow 这个问题：database - What are the differences between B trees and B+ trees? - Stack Overflow
| B+ 树 | B 树 | |
|---|---|---|
| 非叶子节点数据存储情况 | B+ 树非叶子结点不保存 value，只存储 key | B 树所有结点都既保存 key 有存储 value |
| 叶子节点结构 | B+ 树叶子结点组成了一个 doubly-linked list | B 树叶子结点之间是没有引用可以访问彼此的 |
| 叶子结点数据存储情况 | B+ 树叶子结点包含了所有 key 的信息，及指向 key 所对应的 value 的指针 | B 树叶子结点则只保存了部分 key-value 信息 |
B+ 树适用场景
B+ 树非常适用于做文件系统索引和数据库索引，这是因为：
- B+ 树的磁盘利用率更高
- 这是因为 B+ 树内部节点仅存储 key，B 树内部节点既存储 key 又存储 value (link)，导致同样大小的磁盘空间可以容纳的 B+ 树内部节点要比 B 树多。这也就意味着如果使用 B+ 树索引，相同的查询需要的 IO 次数更少。
- B+ 树支持高效的范围查询
- 范围查询是非常常见的，因为 B+ 树叶子结点层构成了一个排好序的双向链表，因此对范围查询和整棵树的遍历是非常高效的。在 B 树结构中作范围查询的代价过高（类似在二叉搜索树中作范围查询，需要遍历整棵树），往往是无法接受的。
- B+ 树的查询效率是稳定且可预期的
- B+ 树的搜索最终会在叶子结点这一层结束，因为内部节点只存储 key 不存储 value (link)。所以每一次搜索的时间开销是相近且可预测的。
B+ 树在 MySQL InnoDB 存储引擎中的使用
最后讲一讲 B+ 树在 InnoDB 存储引擎中的使用，这样对帮助理解 InnoDB 索引结构和 B+ 树具体是如何使用的有直观的帮助。
InnoDB 是索引组织的，表都是根据主键顺序存放的，InnoDB 的数据文件本身既是索引文件，底层数据结构就是 B+ 树。因此这种表也被称为索引组织表（Index organized table）。
B+ 树在实际使用中，阶数 m 一般都很大，使得 B+ 树具有了很高的扇出性（fanout），因此即便存储大量的数据，整棵树的高度一般都在 2~4 层，也就是说一次搜索只需要 2 到 4 次 IO。
在 MySQL InnoDB 中，索引可以分为聚集索引和辅助索引（非聚集索引）。
- 聚集索引（clustered index）就是按照每张表的主键构造⼀棵 B+树，同时叶⼦节点中存放的即为整张表的⾏记录数据，也将聚集索引的叶⼦节点称为数据页。同 B+树数据结构⼀样，每个数据页都通过⼀个双向链表来进⾏链接。
- 辅助索引（Secondary Index，也称⾮聚集索引），叶⼦节点并不包含⾏记录的全部数据。叶⼦节点除了包含键值以外，每个叶⼦节点中的索引⾏中还包含了⼀个书签（bookmark）。该书签⽤来告诉 InnoDB 存储引擎哪⾥可以找到与索引相对应的⾏数据。由于 InnoDB 存储引擎表是索引组织表，因此 InnoDB 存储引擎的辅助索引的书签就是相应⾏数据的聚集索引键（key）。
MySQL InnoDB 是索引组织表，每张表只能有一个主键、一个聚集索引文件，但是可以有多个辅助索引。
通过聚集索引进行查询，就是在 B+ 树中进行搜索；通过辅助索引进行查询，则需要进行两次查询：
- 第一次查询从辅助索引中找到该辅助索引键对应的主键是什么；
- 第二次查询用主键从聚集索引中进行查询。
如果读者对聚集索引和辅助索引还有疑惑，可以阅读《MySQL 技术内幕——InnoDB 存储引擎》的 5.4 和 4.1 节。这里就不多赘述了。
Reference
- 《MySQL 技术内幕——InnoDB 存储引擎》
- 《Algorithms, 4th Edition》by Robert Sedgewick, Kevin Wayne
- database - What are the differences between B trees and B+ trees? - Stack Overflow
- B+ tree - Wikipedia