网站首页技术博客

【MySQL系列文章】3、哈希索引

洞天水月2021-04-22 14:35:25229人次阅读
摘要哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。存储的每一行数据,存储引擎对所有的索引列计算一个哈希码(hash code);哈希索引将所有的哈希码储存在索引中,同时在哈希表中保存指向每个数据行的指针。   由于索引本身只存储哈希值,所以索引的结构十分紧凑,这让哈希索引查找速度变得非常快的同时,也产生了一些限制: 1、哈希索引只包含哈希值和行

哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。存储的每一行数据,存储引擎对所有的索引列计算一个哈希码(hash code);哈希索引将所有的哈希码储存在索引中,同时在哈希表中保存指向每个数据行的指针。

 

由于索引本身只存储哈希值,所以索引的结构十分紧凑,这让哈希索引查找速度变得非常快的同时,也产生了一些限制:

1、哈希索引只包含哈希值和行指针,而不存储字段,所以不能使用中银中的值来避免读取行(覆盖索引)。不过,访问内存中的行的速度非常快,所以大部分情况下这一点对应能的影响并不明显。

2、哈希索引数据并不是按照索引值顺序存储的,所以也就无法用于排序。

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

4、哈希索引只支持等值比较查询,包括=,in(),<=>(至于<=> 和<> 是不同的操作,<=>与=类似区别在于null值的判断)

5、访问哈希索引的数据非常快,除非有很多哈希冲突(不同的索引列值却有相同的哈希值),当出现哈希冲突的时候,存储引擎必须遍历链表中所有的行指针,逐行进行比较,知道赵丹所有符合条件的行。

6、如果哈希冲突很多的话,一些索引维护操作的代价也会很高。例如,如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引,那么当从表中删除一行时,存储引擎需要遍历对应哈希链表中的每一行,找到并删除对应行的引用,冲突越多,代价越大。

因为以上种种限制,哈希索引只适用于某些特定场合。而一旦适合哈希索引,则他带来的性能提升将非常显著。

 

InnoDB引擎不支持hash索引,但是他有一个特殊的功能叫做“自适应哈希索引(adaptive hash index)”。当InnoDb注意到某些索引值被使用的非常频繁时,他会在内存中基于B-Tree索引之上再建立一个哈希索引,这样就让B-Tree索引也具有哈希索引的一些优点,比如快速的哈希查找。这是一个完全自动的、内部的行为,用户无法控制或者配置,不过如果有比较,完全可以关闭该功能。

 

创建自定义哈希索引。如果存储引擎不支持哈希索引,则可以模拟像InnoDB一样创建hash索引,这可以享受一些哈希索引的遍历,例如只需要很小的索引就可以为超长的建创建索引。

具体思路:在B-Tree基础上创建一个伪哈希索引。这和真正的哈希索引不是一回事,因为还是使用B-Tree进行查找,但是它使用哈希值而不是键值本身进行查找。你需要做的就是在查询的Where子句中手动指定使用的哈希函数。

下边是一个实例,例如要存储大量的URL,并需要根据URL进行搜索查找。如果使用B-Tree来存储URL,存储的内容就会很打,因为URL本身都很长。正常情况下会有如下查询:

select id from url where url = "http://www.phpblog.cn";

若删除原来URL列上的索引,而新增一个被索引的url_crc列,使用CRC32做哈希,就一颗使用下面的方式查询:

select id from url where url = "http:'//www.phpblog.cn" and url_crc = CRC32("http://www.phpblog.cn")

这样做性能会很高,因为mysql优化器会使用这个选择性很高而体积很小的基于url_crc列的索引来完成查找。即使有多个记录有相同的索引值,查找仍然很快,只需要根据哈希值做快速的整数比较就能找到索引条目,然后一一比较返回对应的行。另外一种方式就是对完整的URL字符串做索引,那样会非常慢。

 

这样实现的缺陷是需要维护哈希值。可以手动维护,也可以用触发器实现。

 

如果使用这种方式,记住不要使用md5()和SHA1()作为哈希函数。因为这两个函数计算出来的哈希值是非常长的的字符串,会浪费大量的空间,比较时也会更慢。SHA1()和MD5()是强加密函数,设计目标是最大限度消除冲突,但这里并不需要这样高的要求。简单哈希函数的冲突在一个可以接受的范围,同时又能够提供更好的性能。

 

如果数据表非常大,CRC32()会出现大量的哈希冲突,则可以考虑自己实现一个简单的64位哈希函数。这个自定义函数要返回整数,而不是字符串。一个简单的方法可以使用MD5()函数返回值的一部分作为自定义哈希函数。这可能比自己写一个哈希算法的性能要差,不过这样实现最简单:

select conv(right(md5('http://www.phpblog.cn'),16),16,10) as HASH64;

CONV 可以转变目标数据的进制,上边的案例将md5的后16位,从16进制转换成10进制数字。

文章评论