MySQL为什么选择使用B+树作为索引结构？
1. 可以先分析B+树的优势
- 矮胖： 随着数据量的增长，B+树的高度增长不会太快，使得磁盘的I/O次数减少
- 自平衡性： B+树是一种自平衡的二叉树，在新增和删除节点会进行分裂合并操作，以保证树的平衡，删除效率更高。
- 范围查询能力强：B+树的叶子节点之间通过双向链表连接，范围查询能力强，查询效率高。
2.再分析别的数据结构的劣势（二叉树、红黑树、B树、Hash表）
二叉树：
- 查询效率不稳定，二叉树可能退化成链表
- 随着数据量的增加，树的高度增长过快，层级比较深，从而增加I/O次数使得效率低下
红黑树：
本质也是一个二叉树（自平衡二叉树），在大数据量的情况下，层级比较深，会导致树的高度较高，检索速度慢
B-Tree(多路平衡查找树）
非叶子节点会存储数据，每页存储的键值对变少，导致树的层次变深，，从而增加I/O次数，使得效率低下
Hash表
哈希表是键值对的集合，通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O（1））。，但是为什么 MySQL 没有使用其作为索引的数据结构呢？
主要是因为 Hash 索引不支持顺序和范围查询。
举例：
假如我们要对表中的数据进行排序或者进行范围查询，那 Hash 索引可就不行了。并且，每次 IO 只能取一个。
试想一种情况:
SELECT * FROM tb1 WHERE id < 500;在这种范围查询中，优势非常大，直接遍历比 500 小的叶子节点就够了。而 Hash 索引是根据 hash 算法来定位的，难不成还要把 1 - 499 的数据，每个都进行一次 hash 计算来定位吗?这就是 Hash 最大的缺点了。
