MySQL索引的数据结构用B+树的原因

MySQL选择使用B+树做索引不是因为B+数好看，也不是因为B+数好吃，因为货比三家后发现B+数更合适而已。为什么合适，怎样才算合适，得看索引使用场景以及跟其他数据结构进行对比。

首先，索引的出现是为了让查询更高效，一个适用于大多数情形并能显著提升查询效率的数据结构才是最合适做索引的。

第一个上场的是hash。想想Java中的HashMap数据结构就知道，它的优点是通过key可以快速找到对应的数据，JDK8将红黑树加入后性能更上一层楼。那么为什么不适合做索引的数据结构呢？就一点直接让它pass了：不能支持范围查找。因为hash算法中散列是无序的。

第二个上场的是二叉搜索树。二叉查找树优点：有序，查询快。因为所有左子树都比根节点小，所有右子树都比根节点大，所以范围查找也很快。为什么会被pass呢？因为它可能会出现一种极端情况：变成一个链表，极度不平衡。比如主键id默认自增就会出现这种情况，此时索引毫无优化性能可言。

                                                                                  图：二叉搜索树

第三个上场的是红黑树。红黑树就是解决二叉搜索树倾斜的问题的，但是约束不够，解决的不够彻底，还是主键id自增这种常见场景下，在插入数据时红黑树虽然不会完全右倾，但是右倾趋势非常明显。

第四个上场的是平衡二叉搜索树。平衡因子等于1的时候，左右子树高度差不超过1，这样的二叉搜索树叫AVL，AVL的左右子树高度差约束使它拥有优秀的做索引的潜质：良好的查找性能（不存在极端情况）、支持快速的范围查找、有序。这里就需要考虑另一个问题了：数据库查询机制以及瓶颈。数据库查询瓶颈来自于磁盘IO，一次性从磁盘IO拿一条数据到内存和拿10条数据的消耗几乎时一样的。而二叉搜索数每个节点只存储一条数据，有没有更优的数据结构，一个节点上存多条数据呢？这样一次性可以读取到多条数据到内存就减少了IO访问频率。

B树就是一个节点可以存储两个key，B+树在B树的基础上，改变了节点里存的东西。B存储数据，而B+树存储数据对应的地址。B+树虽然在索引的基础上又加了一层类似于目录的东西，不过相对B树，它每层树中存储的key值更多了，树的高度更低，在数据量大的情况下更合适。