面试题-为什么MySQL索引结构使用树而不是哈希？
加速查找速度的数据结构，常见的有两类：
(1)哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是O(1)；
(2)树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是O(lg(n))；
可以看到，不管是读请求，还是写请求，哈希类型的索引，都要比树型的索引更快一些，那为什么，索引结构要设计成树型呢？
索引设计成树形，和SQL的需求相关。
对于这样一个单行查询的SQL需求：
1 | select * from t where name=”Forest”; |
确实是哈希索引更快，因为每次都只查询一条记录。
但是对于排序查询的SQL需求：
- 分组：group by
- 排序：order by
- 比较：<、>
- …
哈希型的索引，时间复杂度会退化为O(n)，而树型的“有序”特性，依然能够保持O(log(n)) 的高效率。
PS：InnoDB并不支持哈希索引。