InnoDB 索引为什么要采用 B+tree 这种数据结构

InnoDB 索引为什么要采用 B+tree 这种数据结构？

一 B-tree

B树也称B-tree,它是一棵多路平衡查找树。

描述一颗B树时需要指定它的阶数，阶数表示了一个节点最多有多少个孩子节点，一般用字母 m 表示阶数。

1. 每个节点最多有 m 个子树，以及最多 m-1 个关键字）。
2. 根节点最少有 2 个子树，可以只有 1 个关键字。
3. 非根节点至少有 m/2 个关键字。
4. 每个节点中的关键字都升序排列。
5. 所有叶子节点都位于同一层。
6. 每个节点都存有索引和数据，也就是对应的 key 和 value。

   如下，是 B-tree：

   

所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。

二 介绍 B+tree 的数据结构？

B+tree 是在 B-tree 的基础上，新增加了两个要求：

1. B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点只存储索引，数据都存储在叶子节点。
2. B+树叶子节点保存了父节点的所有关键字和关键字记录的指针，每个叶子节点的关键字从小到大链接，构成一个链表结构。

   如下，是 B+tree：

   

三 B+tree 相比 B-tree 的优势

• 单一节点存储的元素更多，使得查询的 I/O 次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构了。
• 所有的查询都要查找到叶子节点，查询性能是稳定的，而 B-tree，每个节点都可以查找到数据，所以不稳定。
• B+tree，所有的叶子节点形成了一个有序链表，更加便于查找。

四 InnoDB 采用 B+tree 实现索引的原理

参考下图：

图片来源：《高性能 MySQL，P143》

B+tree 索引能够加快访问数据的速度，因为存储引擎不需要通过全表扫描来获取需要的数据，而是从索引的根节点进行搜索。根节点存放了指向子节点的指针，存储引擎通过这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，最终存储引擎就可以找到对应的值或者记录不存在。

参考资料

1. 《高性能 MySQL：第 3版》
2. 《面试官问你B树和B+树，就把这篇文章丢给他》