金三银四精选java面试题-什么是Hash索引？

什么是Hash索引？

哈希索引（hash index）基于哈希表实现。哈希索引通过Hash算法将数据库的索引列数据转换成定长的哈希码作为key，将这条数据的行的地址作为value一并存入Hash表的对应位置。

在MySQL中，只有Memeory引擎显式的支持哈希索引，这也是Memory引擎表的默认索引结构，Memeory同时也支持B-Tree索引。并且，Memory引擎支持非唯一哈希索引，如果多个列的哈希值相同（或者发生了Hash碰撞），索引会在对应Hash键下以链表形式存储多个记录地址。

哈希索引还有如下特点：

• 哈希索引不支持部分索引列的匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列（A，B）上建立哈希索引，如果查询只有数据列A，则无法使用该索引。

• 哈希索引具有哈希表的特性，因此只有精确匹配所有列的查询对于哈希索引才有效，比如=、<>、IN(，因为数据的存储是无序的)，且无法使用任何范围查询。

• 因为数据的存储是无序的，哈希索引还无法用于排序。

• 对于精确查询，则哈希索引效率很高，时间复杂度为O(1)，除非有很多哈希冲突（不同的索引列有相同的哈希值），如果发生哈希冲突，则存储引擎必须遍历链表中的所有数据指针，逐行比较，直到找到所有符合条件的行。哈希冲突越多，代价就越大！

InnoDB到底支不支持哈希索引？

对于InnoDB的哈希索引，确切的应该这么说：

• InnoDB用户无法手动创建哈希索引，这一层上说，InnoDB确实不支持哈希索引;

• InnoDB会自调优(self-tuning)，如果判定建立自适应哈希索引(Adaptive Hash Index, AHI)，能够提升查询效率，InnoDB自己会建立相关哈希索引，这一层上说，InnoDB又是支持哈希索引的;

那什么是自适应哈希索引(Adaptive Hash Index, AHI)呢?

1、自适应即我们不需要自己处理，当InnoDB引擎根据查询统计发现某一查询满足hash索引的数据结构特点，就会给其建立一个hash索引；

2、hash索引底层的数据结构是散列表（Hash表），其数据特点就是比较适合在内存中使用，自适应Hash索引存在于InnoDB架构中的缓存中（不存在于磁盘架构中）.