为什么MySQL使用B+而不是使用B树、二叉树、AVL树呢？（来龙去脉的去理解）

当你回答使用B+ 怎么怎么好的时候，其实这道面试题你就注定答不满分了，你应该是从一步步如果演变到使用B+来做MySQL的数据结构，下面就一步一步从二叉树——>AVL(平衡二叉树)——>B Tree（多路平衡查找树）——>B+ Tree的一个演变的过程来进行分析，为什么使用B+ Tree的？

（1）先从二叉树开始说起：

• 首先你得知道二叉树是什么吧：看下面的图一你就该很熟悉了吧
• 然后你得知道二叉树查询的时间复杂度是O(log2(n))，这样感觉其实二叉树的查询效率挺高的，但是他会出现另一种现象，就是下面的图二：
• 这样就导致了二叉树的查询效率不问题，如果运气好的话查询效率就很高，如果运气不好的话，就会出现图二的情况，因此在二叉树的基础上又进行的改进，演变出来了平衡二叉树（AVL树）

图一：

图二：

（2）然后到了平衡二叉树（AVL树）:

1. 首先你得知道平衡二叉树的定义吧：在满足二叉树的基础上，任意两个节点的两个子树的高度差不能超过1：就好比下面的这个图的一个效率很差的二叉树，比如5节点的左子树的高度是0，右字树的高度是2，，所以很明显不满足平衡二叉树的概念
   
2. AVL树主要是为了解决上面的图出现的情况，所以现在要把上图的二叉树转插入一个“9”节点然后换为一个平衡二叉树的情况就是下面的：
   
3. 可以看出平衡二叉树的缺点就是：（1）维护平衡过程的成本代价很高，因为每次删除一个节点或者增加一个节点的话，需要一次或者多次的左旋，右旋等去维护“平衡”状态，（2）然后是查询的效率不稳定，还是会有看运气的成分在里面，（3）然后是如果节点很多的话，那么这个AVL树的高度还是会很高的，那么查询效率还是会很低，
4. 还有就是节点存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性，也没有利用好磁盘IO的预读能力。因为操作系统和磁盘之间一次数据交换是已页为单位的，一页 = 4K，即每次IO操作系统会将4K数据加载进内存。但是，在二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能够填满4K的内容。幸幸苦苦做了一次的IO操作，却只加载了一个关键字，在树的高度很高，恰好又搜索的关键字位于叶子节点或者支节点的时候，取一个关键字要做很多次的IO。因此平衡二叉树也是不太符合MySQL的查询结构的。

（3）然后到了使用B Tree（多路平衡查找树）

5. 首先你也得知道B Tree的基本概念：所有的叶子节点的高度都是一样，这个保证了每次查询数据的时候都是稳定的查询效率，不会因为运气的影响
6. 然后B Tree中其实每个非叶子节点内的小节点内其实都是一个二元组[key, data]，key其实就是下图的那个25这种的，然后这个data其实对应的就是数据库中id等于25这条完整的数据记录的内存地址（因为在Myisam中他是数据和索引数据是分开的）

B树的特点：

1. 首先B Tree的每一个节点上其实是有date的，这个date其实就是
2. 然后是B Tree查询的效率不够稳定，他有可能在第一个节点中就查到了数据，并且返回
3. 他的键值其实都是分布在整棵树上的节点上的任何一个节点

（4）然后到了使用B+ Tree（多路平衡查找树）

5. 首先你要知道什么B+ Tree，其实他是专门为磁盘或者其他的直接存取辅助设备设计的一种平衡查找树，在B树中，所有的节点都是按照键值的大小顺序存放在同一层的叶子节点上，由各叶子节点的指针连接。

6. 下图的一颗B树，是一个高度为2，每一页可以放4条记录，扇出是5。
   
   重要的第一点：

7. 重要的第一点：B+ Tree有一个很大的改变就是他的每一个非叶子节点的内节点中都没有date这个概念了，都变成了key，因为他的date都放在了叶子节点上，这样的一个最大的好处就利用了局部性原理（当一个数据被用到时，其附近的数据也通常会马上被使用）与磁盘预读的特性（磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据【这个一定的长度就是一个节点的大小设置为16K】放入内存）

8. 接着上面的：预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

9. 重要的第二点：由于上面我们说的预读原理，因为B+ Tree中节点的内节点无 data 域，其实就是因为没有date域了，但是每次IO的页的大小是固定的，但是B+Tree中没有了date域，那么肯定每次IO读取若干个块块中包含的Key域的值肯定更多啊，B+树单次磁盘 IO 的信息量大于B树，从这点来看B+树相对B树磁盘 IO 次数少。

10. 数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

11. 为了达到这个目的在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

重要的第二点：

1. B+Tree中因为数据都在叶子节点，所以每次查询的时间复杂度是固定的，因为稳定性保证了
2. 而且叶子节点之间都是链表的结构，所以B+ Tree也是可以支持范围查询的，而B树每个节点 key 和 data 在一起，则无法区间查找。

参考索引：http://blog.codinglabs.org/articles/theory-of-mysql-index.html
局部性原理文章： https://blog.csdn.net/wwh578867817/article/details/50493940

到了这里相必你已经彻底知道了为什么使用B+ Tree来作为MySQL索引的数据结构了吧