面试官：MySQL索引为什么要用B+树实现？
原因如下
- B+树能显著减少IO次数，提高效率
- B+树的查询效率更加稳定，因为数据放在叶子节点
- B+树能提高范围查询的效率，因为叶子节点指向下一个叶子节点
B+树是怎么来的？
在从一堆数据中查找指定的数据时，我们常用的数据结构是哈希表和二叉查找树，表本质上就是一堆数据的集合，所以MySQL数据库用了哈希表和B+树来实现索引
B+树是通过二叉查找树，再由平衡二叉树，B树（又名B-树）演化而来的，B+树中的B不是代表二叉（binary），而是代表平衡（balance），因为B+树是从最早的平衡二叉树演化而来，但是B+树不是一个二叉树。
二叉查找树和平衡二叉树
二叉查找树的效率和平衡二叉树的查找效率已经很高了，为什么不用这两种数据结构来实现索引呢？慢慢来分析
二叉查找树是带有特殊属性的二叉树，需要满足以下属性
- 非叶子节点最多拥有两个子节点
- 非叶子节值大于左边子节点、小于右边子节点
- 没有值相等重复的节点;
对上图这个二叉树进行查找，如查键值为5的记录&#x
下一篇：
链表和二叉树 指针和双指针