MySQL 高性能索引(哈希索引)

  • A+
所属分类:MySQL

哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。

MySQL 中,只有 Memory 引擎显式支持哈希索引。这也是 Memory 引擎表的默认索引,Memory 引擎也支持 B-Tree 索引。值的一提的是,Memory 引擎是支持非唯一哈希索引的,这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同,索引会以链表的方式存放多个记录指针到同一个哈希条目中。

以下面的数据库结构为例:

CREATE TABLE testhash (
	
	fname VARCHAR(50) NOT NULL,
	lname VARCHAR(50) NOT NULL,
	KEY USING HASH(fname)

)ENGINE= MEMORY;

表中含有如下数据:

mysql > select * from testhash;

MySQL 高性能索引(哈希索引)

假设索引使用假想的哈希函数f(),它返回下面的值(以下为实例数据):

f('Arjen') = 2323

f('Baron') = 7437

f('Peter') = 8784

f('Vadim') = 2458

则哈希索引的数据结构如下:

槽(Slot) 值(Value)
2323 指向第1行的指针
2458 指向第4行的指针
7437 指向第2行的指针
8784 指向第3行的指针

需要注意的是,每个槽的编号是顺序的,但是数据行不是。现在,来看如下查询:

mysql > select lname from hashtest where fname = 'Peter';

MySQL 先计算‘Peter’的哈希值,并使用该值寻找对于的记录指针。因为 f('Peter') = 8784 ,所以 MySQL 在索引中查找 8784,可以找到指向第 3 行的指针,最后一步是比较第三方的值是否为‘Peter’,以确保就是要查找的行。

因为索引自身只需存储对于的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快。然而,哈希索引也有它的限制:

1.哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。不过,访问内存中的行速度很快,所以对性能的影响并不明显。

2.哈希索引数据并不是按照索引值顺序存储的,所以无法用来进行排序。

3.哈希索引也不支持部分索引列匹配查找。

4.哈希索引只支持等值比较查询,包括 = 、IN()、 <=>。也不支持范围查询。

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

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

思路也很简单: 在 B-Tree 基础上建立一个伪哈希索引。这和真正的哈希索引不是一回事,因为还是使用 B-Tree 进行查找,但是它使用哈希值而不是键本身进行索引查找。我们需要做的就是在查询的 WHERE 字句中手动指定使用哈希函数。

以存储 URL 为例。如果使用 B-Tree 来存储 URL,存储的内容就会很大,因为URL 本身会很长。正常情况下,会使用以下查询:

mysql > select id from url where url = 'http://xjwblog.com';

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

mysql > select id from url url = 'http://xjwblog.com' and url_crc = CRC32('http://xjwblog.com');

这样做的性能会非常高,因为 MySQL 优化器会使用这个选择性很高而体积很小的基于 url_crc 列的索引来完成查找。即使有多个记录有相同的索引值,查找仍然很快。

这样的缺陷是需要维护哈希值。可以收到维护,也可以使用触发器实现。下面以触发器为例,首先创建如下表:

CREATE TABLE pseudohash (
    
	id int UNSIGNED NOT NULL auto_increment,
	url VARCHAR(255) NOT NULL,
	url_crc int UNSIGNED NOT NULL DEFAULT 0,
	PRIMARY KEY (id)

);

然后创建触发器。

CREATE TRIGGER pseudohash_crc_ins BEFORE INSERT ON pseudohash FOR EACH ROW BEGIN SET NEW.url_crc = CRC32(NEW.url);
END;

CREATE TRIGGER pseudohash_crc_upd BEFORE UPDATE ON pseudohash FOR EACH ROW BEGIN SET NEW.url_crc = CRC32(NEW.url);
END;

接下来来验证触发器如何维护哈希索引:

mysql > insert INTO pseudohash (url) VALUES (' 

mysql > SELECT * from pseudohash;

MySQL 高性能索引(哈希索引)

mysql > UPDATE pseudohash set url = 'http://www.xjwblog.com' where id = 1;

mysql > SELECT * from pseudohash;

MySQL 高性能索引(哈希索引)

如果采用这种方式,记住不要使用 SHA1() 和 MD5() 作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串,会浪费大量的空间,比较时也会更慢。

如果数据量很大,CRC32() 会出现大量的哈希冲突,则可以考虑实现一个简单的64位哈希函数,这个函数要返回整数,而不是字符串。

avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: