mysql为什么使用B+树作为索引结构？

首先，mysql的基本存储结构是页：

各个数据页可以组成一个双向链表，每个数据页中的记录又可以组成一个单向链表。

如要查询： * from user where name=‘xxx’;

在没有索引时，查询数据需要先遍历双向链表找到所在的页，如果不是根据主键查询，只能再在所在的页遍历单向链表了。

使用索引之后的存储结构边得有序了：(现在根据二分查找，很快就能找到，时间复杂度近似O（logn）)

存储引擎最小存储单元是页，一个页的大小是16K。页可以存放数据页可以存放键值+指针，在B+ 树叶子节点存放数据，非叶子节点存放键值+指针。所以组织表通过非叶子节点的二分查找法以及指针确定在哪个页中，进而去数据页中查找需要的数据。

为什么选择B+树而不选择二叉树，B树？

算法中有一个二分法查询效率是比较高的，二分法在数据结构中有一种数据结构二叉树实现原理就是二分法，但是二叉树有一个不好的点就是当数据是依次增大或依次减小的时候就会形成一个链表，因此有了红黑树通过左旋和右旋进行平衡，但是还有缺陷就是树太高了，在查找数据时一次页的查找代表一次IO，树太高查询一个数据的IO次数就会很高。因此有了B树，虽然相对红黑树有改进，但是每个节点都存储有数据，由于CPU每次读取数据库的大小是一定的，所以耗费的性能也是比较高的。所以每次IO的数据更多一些，把数据读取到内存中，再进行排序花费的时间就小了，因此，B+ 树的磁盘页可以存储更多的节点元素。

B+树相比于B树的优点：

1、B+树的中间节点不存储元素，是纯索引，B树的中间节点存储元素，相比于B树来说，树更矮（意味着IO次数越少）。

2、B+数查询必须查找到叶子节点，B树只要找到节点就能找到数据。

3、对于范围查找来说，B+ 树只需要遍历叶子节点即可，而B树则要不断的进行中序遍历（在项目中范围查找也很常见）。

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

参考资料：