数据库底层索引长啥样，你心里没点B树吗？

写在前面

索引是对数据库值进行排序的一种存储结构，使用索引可提升数据库信息的访问效率，我们熟悉的MySQL采用B+树作为索引的底层存储结构，要知道MySQL采用B+树的原因，首先有必要介绍下树从二叉树到B树再到B+树的演变。

二叉树

二叉树

B树

如图为M阶B树(M=4)，从图中可以看出
1：根节点至少2个子节点。
2：每个节点key的数量为[M/2-1,M-1]，即最多有3路，并且升序排列。
3：每个节点存储key和data。
4：所有叶子节点在同一层。
5：每个叶子节点指向的外部指针都为NULL。

4阶B树

B+树

如图为M阶B+树(M=4)，从图中可以看出，与B树有所不同
1：非叶子节点不保存data，只保存索引。
2：某一节点有几个子节点，就有几个key。
3：所有key都在叶子节点出现。
4：所有叶子节点链接成一个有序的链表。

B+.png

从上面几张图可以看出，B树和B+树都是矮胖树，这对数据库索引结构的选择是非常重要的。
1：数据库为什么不选择二叉树？
二叉树的高度相比于B和B+树更高，高度越高，索引时IO次数越多，存取效率就会越低，所以不宜选做数据库的索引结构。
2：数据库为什么不选择B树，而选择B+树？
1：B+树每个叶子节点都有一个指向相邻叶子节点的指针。数据库的查询往往会有针对范围的查找，不可避免的需要遍历整棵树或者部分子树，B+树只需要遍历叶子节点就可以遍历整棵树，查询效率要远远高于B树。
2：非叶子节点不存储data，只存储key值，这样每个非叶子节点就可以存储更多的key，能读到内存中的key也就越多，内存操作的效率要远远高于磁盘I/O操作。

PS：关于索引的其他知识点记录一下。

聚簇索引（主键索引）

B+树的叶子节点存储的是完整的行数据。

二级索引（非主键索引）

叶子节点只存储了索引键值和主键值，如果查询字段包含索引以外的字段，则会根据主键回表查询。从mysql5.7开始，会先根据条件过滤掉部分行，再进行回表操作，这个过程叫做索引下推。

覆盖索引

如果使用普通索引，查询字段包含在索引字段中或者是主键，则不需要进行回表操作。