mysql的索引结构为什么选用B+树?

问题：为什么索引结构默认使用B+Tree，而不是B-Tree，Hash，二叉树，红黑树？

哈希表

哈希表可以进行数据的快速检索。哈希表会使用哈希算法。

哈希算法：也叫散列算法，就是把任意值(key)通过哈希函数变换为固定长度的 key 地址，通过这个地址进行数据查询的数据结构。

算法时间复杂度分析来看，哈希算法时间复杂度为 O（1），检索速度非常快。比如查找 id=7 的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快。但是 Mysql 并没有采取哈希作为其底层算法。即hash算法针对范围查找效率太低，需要把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。

二叉查找数（BST）

二叉查找树支持快速查找数据，时间复杂度为O(logn)，并且可以解决范围查找的问题

如上图如果想找到id>5的数据，只需要找到节点6及其右子树的数据即可，范围查找比较容易实现。

普通二叉树的致命缺点：极端情况下会退化为线性链表，时间复杂度为O(n)，性能急剧下降
数据库表的主键id一般为自增，上述的线性结构查找问题必然出现，而且频率还很高

红黑树

二叉查找树不平衡，可以通过树节点的自动旋转和调整来解决，从而保证二叉树的查找性能。最常见的思路是平衡二叉树和红黑树。

红黑树可以自动调节树的结构，当二叉树不平衡时，红黑树会自动左右旋转和节点变色，保持基本的平衡，时间复杂度为O(logn)，但是红黑树也会出现“右倾”退化现象，只不过极端退化情况比平衡二叉树好，但是也没能达到预期

平衡二叉树（AVL）

先来考虑AVL 树的优点，它的查询效率为O(logn),不存在极端情况，可以进行范围查找和排序。
但是为什么不选取AVL树作为MySQL索引的数据结构？

主要是磁盘IO因素的影响。如果使用AVL树，每一个树节点，只存储一个数据。比对一次树节点，即进行一次磁盘IO操作，如果数据量大了，那磁盘IO的次数会很高，消耗大量的时间

所以，设计数据库索引的时候，还需要考虑怎么尽可能减少磁盘的IO次数。
由于磁盘读取1B和1KB的数据消耗的时间基本是一样的，所以可以在一个节点存储更多的数据，即一次磁盘IO读取更多数据，即可解决问题。所以就考虑到了B树。

B树

B 树的优点，优秀检索速度，时间复杂度：B 树的查找性能等于 O（h*logn），其中 h 为树高，n 为每个节点关键词的个数； 尽可能少的磁盘 IO，加快了检索速度； 可以支持范围查找。
B-Tree数据分布在各个节点之中，每个节点存储的数据量是有限的，MySQL希望一个节点可以尽可能多的存储数据，因此采用了B+树

B+树

• B树一个节点存储的是数据，一个节点中存储不了太多数据；B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。在 MySQL 数据库中数据页的大小是固定的，Innodb 引擎数据页默认大小为 16 KB。B+ 树这种做法是为了让树的阶数更大，让树更矮胖。进行查询的时候，磁盘 IO 次数就会减少，查询效率也会更快。

• B+数叶子结点采用链表串联，更便于范围查找。而B树需要中序遍历。