一分钟掌握MySQL的InnoDB引擎B+树索引

2020 年 5 月 17 日
笔记

MySQL的InnoDB索引结构采用B+树，B+树什么概念呢，二叉树大家都知道，我们都清楚随着叶子结点的不断增加，二叉树的高度不断增加，查找某一个节点耗时就会增加，性能就会不断降低，B+树就是解决这个问题的。

B树和B+树

在一棵M阶B树中，每个节点最多有 M-1 个关键字，根节点最少可以只有一个关键字，非根节点最少有 Math.ceil(m/2)-1个关键字,下图是一棵阶数为3的树

看下图我们说说B树的特点，很明显一个节点存储的数据更多了，不需要很高的高度就可以存储更多的数据，把一个节点看作一个磁盘，我们发现查找一个数据时可以减少磁盘IO次数，B树的每个节点都有data域，

看下图我们说说B+树的特点，首先明确一点，B+树是在B树的基础上演化而来的，我们就说不同点，只有叶子节点才有data域，叶子节点包含所有的数据，叶子节点通过指针链接形成双向链表。

B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉，B树每个内节点有多个分支)，与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成，而CPU的速度非常快，所以B树的操作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少

为什么InnoDB选择B+树而不是B树呢

还是上面两张图，对照着看，我们能够得出一下结论

B+树的磁盘读取代价低，树每个节点都有data域，B+树只有叶子节才有，假设每个节点大小16KB，那么B+树比B树能存储更多的关键字，一次性读入内存的关键字的内存也会更多，B+树的高度也会比B树低,磁盘IO次数会更少。

B+树对范围查询更友好,方便遍历，B树叶子节点没有链接，而B+树叶子节点通过双向指针链接，可以很方便的进行范围查询，比如where条件中 age >=3 and age <20,,那么当找到3时就可以顺着指针找到20,而B树是不可以的。

B+树查询效率稳定性更好，在B+树中，由于分支节点并不是最终指向文件内容的节点，分支节点只是叶子节点的索引，所以对于任意关键字的查找都必须从根节点走到分支节点，所有关键字查询路径长度相同，每个数据查询效率相当。而对于B树而言，其分支节点上也保存有数据，对于每一个数据的查询所走的路径长度是不一样的，效率也不一样，B树稳定性不如B+树好

我们仔细想想我们SQL常见的查询中，总结起来是不是也就是等于查询，范围查询

InnoDB非主键索引怎么存储呢？

我们上面介绍的只是主键索引是这样存储的，那么非主键索引呢，其实非主键索引也B+树的，只有非主键索引的叶子节点存储的不是行记录数据，而是主键值，通过主键值再次索引获取所需要的数据。我画一个粗略的见图来表示

总结一下B+树索引

采用了多叉树的结构，降低了树的高度，减少了磁盘IO次数，通过对所有叶子节点通过指针双向链接，方便的提供了遍历所有数据的特性，同时数据也是严格有序的，方便范围查询,查询效率的稳定性也非常好。