哈希(hash)比树(tree)更快，索引结构为什么要设计成树型？

加速查找速度的数据结构，常见的有两类：

哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是O(1)； 树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是O(lg(n))；

可以看到，不管是读请求，还是写请求，哈希类型的索引，都要比树型的索引更快一些，那为什么，索引结构要设计成树型呢

索引设计成树形，和SQL的需求相关。

对于这样一个单行查询的SQL需求： select * from t where name=”john”; 确实是哈希索引更快，因为每次都只查询一条记录。 所以，如果业务需求都是单行访问，例如passport，确实可以使用哈希索引。

但是对于排序查询的SQL需求： 分组：group by 排序：order by 比较：

哈希型的索引，时间复杂度会退化为O(n)，而树型的“有序”特性，依然能够保持O(log(n)) 的高效率。 任何脱离需求的设计都是耍流氓。 多说一句，InnoDB并不支持哈希索引。