模拟InnoDB的“自适应哈希索引功能”来优化查询

概述

在哈希列上建立一个索引,模拟InnoDB的“自适应哈希索引功能”。

InnoDB的“自适应哈希索引”的功能

当InnoDB察觉到某些索引值用得非常频繁时,它会在内存中基于B+Tree索引之上,建立一个哈希索引(也就是添加一个存放哈希值的虚拟列,将这个列加入B+Tree索引)。

使用场景

  • 在字段比较长时(如URL、文章等,虽然可以使用前辍索引,但是仍可以使用哈希值来优化查询速度)
  • 非InnoDB引擎。(上面说了InnoDB引擎有原生的优化)

使用方法

URL列为例:
1. 建立一个URL_crc列,使用CRC32函数计算哈希值。
2. URL列上的索引会影响后面的查询,将URL列上的索引删除。(虽然索引删除后仍可以创建,但行数极多的表创建索引时,会非常慢,且耗费很多硬件资源,所以整个添加哈希索引的过程应该有计划地,谨慎地,多方面思考地进行)
3. 在URL_crc列上建立B树索引。
4. 使用下列SQL语句查询

SELECT id FROM url
WHERE url="https://imdyc.com"
AND url_crc = CRC32("https://imdyc.com");

为了预防小概率出现的哈希碰撞,所以一定要加上url=”https://imdyc.com”这一条件。
另外无需考虑AND左右两边的条件执行顺序,因为MySQL查询优化器会先使用速度快的url_crc来进行查找。

这样做的缺陷是需要维护哈希值,在插入或改变url值时,url_crc也要随之改变可以使用触发器进行维护,我们继续进行第五步。

5.创建两个触发器
一个INSERT触发器

CREATE TRIGGER hash_crc_ins BEFORE INSERT ON table_user FOR EACH ROW BEGIN
SET NEW.url_crc=CRC32(NEW.url);

一个UPDATE触发器

CREATE TRIGGER hash_crc_upd BEFORE UPDATE ON table_user FOR EACH ROW BEGIN
SET NEW.url_crc=CRC32(NEW.url);

不建议采用SHA1()和MD5()作为哈希函数。因为这两个函数计算出来的哈希值时非常长的字符串,会浪费大量空间,比较时也会更慢。SHA1()返回40位十六进制,MD5()返回32位十六进制,CRC32()计算结果是32位二进制,以十进制的方式返回

哈希碰撞

使用CRC32()时,即使返回的哈希值有四十多亿个,因为所谓的生日悖论,出现哈希冲突的概率增长速度可能比想象中快得多:使用crc32(rand())进行随机插入时,十万行中有120个冲突,三十二万行则有748次冲突,最高只出现了2个值相等。(实验数据,仅供参考)估计出现3个值相等时,冲突次数已经达到数万次了吧。
因为哈希索引还是允许有一定的冲突值,所以在数据量不是非常大的时候,不必担忧查询性能会下降很多。
如果数据量实在是太大了,那可以牺牲一些存储空间为代价,从MD5()中截取一段64位(二进制)的字符串作为哈希值。

RIGHT(MD5('https://imdyc.com')16)

参考资料:Baron Schwartz《高性能MySQL 第3版》

文章后续可能会有更新,为了避免不必要的误会,转载请保留出处:https://imdyc.com/database/模拟innodb的自适应哈希索引功能来优化查询.html

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注