常见面试题：为什么MySQL索引要用B+Tree呢？（看完你就能和面试官笑谈人生了）

为什么MySQL索引要用B+Tree呢？

要跟面试官回答该问题，就需要先跟面试官讲讲能够作为MySQL索引的结果有哪些。

参考文章：为什么 MySQL索引要用 B+tree

以下就是我的回答：

我们知道，索引的常用结构有：二叉树、红黑树、Hash表、B-Tree、B+Tree 这几种。

1）为什么不采用二叉树呢：

原因：因为假设此刻用普通二叉树记录id系列，我们在每插入一行记录的同时还要维护二叉树索引字段。如果此时找id = 7这一行记录需要找7次，这跟扫描全表也没有什么大的区别。显而易见，二叉树对于这种依次递增的数据列，其实是不适合作为索引的数据结构。

2）为什么不采用Hash表呢：

因为Hash索引不适用于范围查找。

3）为什么不采用红黑树呢：

因为当MySQL数据量很大的时候，索引的体积也会很大，可能内存放不下，所以需要从磁盘上进行相关读写，如果树的层级太高了，则读写磁盘的次数（I/O的交互）就会越多，性能就会越差。红黑树目前唯一的不足点就是它的树的高度是不可控的。

4）那为什么要用B+树，而不用B树呢：

B树 只适合随机检索，而B+树 同时支持随机检索和顺序检索；

B+树 空间利用率更高，可减少I/O次数，磁盘读写代价更低。 一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗。B+树 的内部结点并没有指向关键字具体信息的指针，只是作为索引使用，其内部结点比B树小，盘块能容纳的结点中关键字数量更多，一次性读入内存中可以查找的关键字也就越多，相对的，IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素；

B+树的查询效率更加稳定。B树 搜索有可能会在非叶子结点结束，越靠近根节点的记录查找时间越短，只要找到关键字即可确定记录的存在，其性能等价于在关键字全集内做一次二分查找。而在B+树 中，顺序检索比较明显，随机检索时，任何关键字的查找都必须走一条从根节点到叶节点的路，所有关键字的查找路径长度相同，导致每一个关键字的查询效率相当；

B-树 在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树 的叶子节点使用指针顺序连接在一起，只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树 不支持这样的操作；

增删文件（节点）时，效率更高。因为B+树 的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率。

总结：

① B树 的单个结点存储的元素比B+树多，自然在整个过程中的磁盘I/O交互就会比 B+树 多，增加了性能开销；

② 相对B-tree来说，B+树所有的查询最终都会在叶子结点上，这也是B+树性能稳定的原因的一个体现；

③ B+树所有的叶子结点都是通过双向链表相连，范围查询非常方便，这也是B+树最明显的优势。