哈希索引真的不能进行范围查找吗？

本文的问题来自于博主遇到的一个面试问题。博主与面试官的对线顺序如下：

面试官： 数据库的索引结构有哪些？ 我：B+索引，hash索引，fulltext索引? 面试官：那你对比说明一下B+索引和hash索引的优缺点？ 我：哈希索引的检索速度更快，但是只能进行全值匹配，不能进行范围匹配，balabala...（常见的面试题，之前肯定了解过背过）。 面试官：你确定hash索引不能进行范围匹配吗？ 我：？？？ 黑人问号脸 面试官：你回去再了解一下。

这是一个典型被面试官怼的场景对话，但是也引申出本文要讨论的核心问题: 哈希索引能否进行范围查找？

1.面试官在诈我？

我第一个反应就是难道面试官在诈我？我面试结束后上网查一查，网上千篇一律hash索引不支持进行范围匹配。所以一度认为让面试官演了一手。从小学就喜欢钻研的小明同学当然不能忍，直接用mysql进行了实验：

1.1首先创建一个表

采用memory作为存储引擎，因为innodb不支持hash索引 create table test2(id int)engine=memory; create index index_test using hash on test2(id);

1.2 插入五个测试数据

1.3 执行范围查找

select * from test2 where id>1 and id<5

1.4 执行结果

可以看到结果确实正确得到结果，因此可以得出结论，采用hash索引的mysql数据库确实能进行范围查找。

2. 全表扫描

后来经过我多方查证和确认，数据库不论怎样都可以通过全表扫描得出结果，即使此时hash索引失效。所以我认为是我当时关于hash索引得数据库不能进行范围查找的表述有有一定问题，让面试官抓到了把柄而被怼，甚至面试官本来之后准备问我一些关于索引失效的问题。

但是这依然没有解决Hash索引本身确实不能进行范围查找的问题

此时我又陷入了沉思。。。

3. 实现一个支持范围查找的Hash索引结构

重新回到Hash索引本身，hash索引之所以不能进行范围查找，是因为Hash操作并不能保证顺序性，所以值相近的两个数据，Hash值相差很远，被分到不同的桶中。

因此问题的关键在于如何在使用Hash索引的同时，依然保留数据值的大小顺序。

3.1 LRU缓存

首先我想到的就是LRU缓存的数据结构，在Java中可以通过LinkedHashMap的实现。他保留了插入的顺序。

利用这种思想我们可以在Hash索引的基础上，将所有数据通过链表有序的排列，每次添加新的值时有序插入，这样就可以执行范围查找了。

但是这会让插入的复杂度变为O(n),效率低下。

3.2 Redis的Zset

为了解决插入效率底的问题，我又想到了Redis中的Zset数据结构，通过Hash表和跳表实现有序集合。

通过这种思路改造Hash索引也可以在支持范围查找的的同时将插入的复杂度降低到O（logN）。

但是考虑到磁盘的IO影响，跳表并不能很好的控制IO的次数，平均IO次数也超过B+树，B+tree确实是最适合关系型数据库的索引结构。因此只有基于内存的Redis数据库使用了这种索引方式。

（怎么说了半天，最后本质上Hash索引还是不支持范围查找，只能依靠其他索引）

写到最后

这篇博客是记录博主心路历程，求求各位，评论，关注，点赞，可怜可怜