MySQL为什么选择B+树作为索引实现的数据结构
前几天在微信群中有一个朋友抛出一道面试题：MySQL为什么选择B+树作为索引实现的数据结构？这个问题其实网上一搜有一堆的资料，甚至说它是面试必备八股也不过分。我当时在群里回答了这个问题，但事后觉得回答的不是很好，仔细思索几天后决定写一篇文章来回答这个问题，正好11月还没写文章。
要回答这个问题，其实一句话就够了：因为B+树是IO友好型的数据结构。我知道你听了肯定想打我，你这话不明不白的，我要是就回答这一句话面试官能给我过？别着急，我们一点一点的来解释这句话。
首先我们需要明白一个大前提：数据库的数据量很大，不可能将所有数据都放入内存的。这个前提有什么用呢？由于数据不可能全部放入内存，那就代表数据库的部分数据（甚至大多数数据）都是在磁盘上而不在内存中的。这时假设你做查询语句想查询一条数据，MySQL必然需要先找到那条数据，这条数据如果此时在内存中还好说，MySQL会从内存中找出来然后返回给你；但倘若不在内存中呢？那就代表MySQL要访问磁盘，从磁盘中将那条数据找出来然后返回给你。
我们知道访问内存的成本和访问磁盘的成本差距是非常大的，访问内存的时间大概在100ns左右，但如果访问一次机械硬盘（做一次随机读操作），大概在2ms左右，足足差了2万倍。因此我们上面说的IO友好型其实指的就是这种数据结构从磁盘查找数据的效率是最高的，时间是最快的。那如何保证效率是最高和时间最快呢？最核心的就是尽可能少的访问磁盘，别人找一条数据得访问5次磁盘，所以它需要2ms * 5 = 10ms，你找一条数据只需要访问2次磁盘，那么你就只需要2ms * 2 = 4ms，你就比别人快，效率比别人高。总而言之谁从磁盘中找数据访问磁盘的次数最少，谁就是IO友好型的，谁就能作为数据库索引实现的数据结构。
明白了这个道理后，我们再来看看为什么B+树是IO友好型的数据结构。
首先我们从最基本的线性数据结构说起，链表和数组。
想象一下如果MySQL存储每条记录按链表或者数组会怎么样？很明显链表和数组的线性结构导致了它们无法快速的查询。比如我让你给我找用户名是小明的记录，如果是数组或者链表你只能遍历查找。还是那句话，MySQL无法将所有数据都放入内存，因此很多查询都是从磁盘中加载的，假设使用链表作为数据结构，遍历的时候每获得一个节点的信息就是在做一次磁盘的读操作，这样查询一条记录平均要执行n/2次的IO读操作，假设你有10万条数据，你平均一次查询要做5万次的IO，这肯定是不行的。
这时候你可能会说了，用散列表（哈希表）啊，哈希表一个key就能对应一个value，这不是一查一个准？关于散列表的问题我们一会再说。
可以很容易得出结论：我们需要一种查询能力强的数据结构，当我们想找一条数据的时候，它能够用最少次的查询将数据找出来（前提是数据量很大），树是一种非常好的选择。
树有很多种，我们可以简单的将树分为二叉树和多叉树。所谓二叉树就是一个根节点最多只有两个子节点
如上图就是一个典型的二叉树，而且是一个平衡二叉树，这时我们假设想要搜索值为4的记录，只需要从头节点3开始搜索，4比3大，因此找右子节点5，4比5小，因此找左子节点，这样一下就找到了，我们共遍历了三个节点3->5->4，很明显，二叉树的搜索思路其实就是二分法的查找思路，因此在二叉树上搜索一条记录复杂度往往为O(logn)，假设现在还是10万条数据，则只需要搜索13~14次，这样就大大提高了搜索效率，而且O(logn)的查询性能也不会像链表数组一样随着总数而线性增长。
二叉树看起来已经不错了，但我们要知道，数据库内的一张表记录往往是亿级别的，当有1亿条数据时，二叉树就需要查询26次，也即26 * 2 = 52 ms。这个时间成本已经是非常高的了。我们想一下问什么二叉树需要搜索那么多次？归根究底还是二叉树太高了。我们假设要搜索的结果在树的叶节点上，搜索是从树根开始，每一次搜索就是向树的下一个层级寻找，这也就代表每一层树高都对应着一次搜索，1亿条数据需要搜索26次是因为2^26大约等于1亿，也即整个二叉树的高度是26，树的每一层高都成为搜索的必经之路。在搜索是读磁盘的时候，每一次的搜索都是巨大的耗时，因此缩减树的高度就异常的关键。
因此多叉树就成了数据库在设计索引时经常会选的一种数据结构。这个理由很简单，2^26≈1亿，10^8=1亿，如果一个根节点有10个子节点，那么树高只需要8层就能装下1亿条数据，这样搜索一条记录也只需要8次IO。
多叉树最经典的就是B树（也叫B-树）和B+树了，我们不妨把这两个数据结构一起拿过来比较：
上图为B树
上图为B+树。
B树与B+树主要的区别如下：
- B+树的非叶子节点不保存数据，只进行数据索引，而B树的叶子节点与非叶子节点都保存数据。
- B+树的一个节点的记录之间采用单向链表相连，而节点与节点间的记录采用双向链表相连。
这两点不同直接决定了我们采用B+树而不是B树，我们一个个来说为什么。
首先由于B+树的非叶子节点不存储数据，这就保证了B+树的非叶子节点很轻（占用的字节少），相反，B树的非叶子节点是很大很重的。这一点的区别影响非常大，我们假设现在B+树和B树保存1亿条数据都是4层，这时候B+树的前三层都是非叶节点只保存索引，因此它们很轻，MySQL数据库很可能将前三层的B+树节点都保存在内存中，这样在搜索的时候一层层往下搜，前三层都在内存不需要查磁盘，只有最后一层需要查磁盘，这时候查询一条数据可能是只做了一次IO。同样的道理对于B树，B树每个节点都太重了，内存必然不可能能够装满B树的三层结构，因此往往B树在内存中保存的节点是少于B+树的，这也就代表B树可能需要比B+树多做从磁盘中查询节点的情况。虽然B树每个节点上都有数据，很可能存在查到第二层的某个节点就找到数据然后直接返回了，反观B+树每一次都需要找到最后一层（因为只有叶节点才保存数据），但是我们要想到这种情况是非常非常少的。拿B树一个父节点有10个子节点来算，这就代表了第n层的节点数是第n-1层的10倍，也即将近90%的数据都是落在叶子节点层的。何况一般一个B+树节点往往具有大概1000条记录，1000亿条的数据也只需要四层就够了。因此即使是1000亿的数据，也只是最多做四次IO查询。
其次由于B+树的数据均存储在叶子节点，且节点间通过链表相连，这使得B+树的范围查找，排序查找，分组查找以及去重查找变得异常简单。而B-Tree 因为数据分散在各个节点，要实现这一点是很不容易的。
最后再说回散列表，散列表最大的问题是无法进行范围搜索，这一条基本就可以毙掉它了。
说完了这些你应该也就明白了MySQL为什么选择B+树作为索引实现的数据结构了吧，其实根本原因就是B+树是IO友好型的数据结构，它从很大量的数据中查询出一条数据是最快的，做IO的次数是最少的。
参考资料：
