为什么MySQL数据库索引选择B+树

树是非常重要的一种数据结构，下面先讲几种常见的树结构，并分析它们为什么不适用于数据库索引。

AVL树

平衡二叉树的定义如下：首先符合二叉查找树的定义，其次必须满足任何节点的两个子节点的高度差不大于1。平衡二叉树的查找速度确实很快，但是维护一棵平衡二叉树的代价是非常大的，不管我们执行插入还是删除，一旦不满足条件就需要通过左旋和右旋来保持平衡性，所以AVL树适合用于插入删除次数比较少，但查找多的情况。

红黑树

红黑树是一种弱平衡二叉树，相对于AVL树来说它的旋转次数会变少，所以适用于插入删除操作比较频繁的情况。红黑树的五条定义：

• 所有节点不是红色就是黑色


• 根节点是黑色


• 叶子节点是null节点（空节点）且为黑色。


• 同一路径中，不存在连续的红色节点。


• 每个节点到它所能到的叶子节点经过的黑色节点数相同。

从根节点到叶子节点的所有路径中，最长路径不会超过最短路径的2倍，这保持了红黑树的弱平衡。在Java中，TreeMap、TreeSet都使用红黑树作为底层数据结构，JDK 1.8开始，HashMap也引入了红黑树：当冲突的链表长度超过8时，自动转为红黑树。

B+树

B+树是为磁盘或其他直接存取辅助设备设计的一种数据结构，在B+树中，非叶子节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层，所有记录都是按键值的大小顺序存放在同一层的叶子结点上，由各叶子结点指针进行连接，B+树的插入必须保证插入后的叶子结点依然有序。（图片来自：https://blog.csdn.net/cxu123321/article/details/105665056/）

所以为什么B+树更适合数据库索引呢？

分析：

数据库的数据一般存储在磁盘中，读取数据时需要访问磁盘，我们知道读取磁盘数据的时间是由磁盘定位的时间+数据读取时间，而且定位的时间要远大于读取的时间，二叉树类型的结构可以将查询速度提升到\(O(log_2 N)\)，但是最坏的情况要查找到二叉树的最深层，这在数据量很大时是不能接受的，B+树有高扇出性的特点，所以在这种情况下，矮胖的B+树相比于高瘦的AVL树（或者红黑树）就能减少访问的层数，提升查找效率。在数据库中，B+树的高度一般都在2-4层，这就是说查找某一键值的记录最多只需要2-4次IO。

那为什么采用B+树不用B树呢？

原因：

B树在提高了IO性能的同时并没有解决元素遍历效率低下的问题（B树因为分支结点同样存储着数据，所以如果要查找某个范围的数据，需要进行一次中序遍历）。为了解决这个问题，B+树应用而生，B+树的中间节点存储的只是叶子节点的索引，所有数据都存储在叶子结点中，所以只需要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，B树不支持这样的操作或者说效率太低。

参考：

https://blog.csdn.net/cxu123321/article/details/105665056/