数据表还有哈希索引，没听过？

2020-12-26 本文已影响0人岛上码农

哈希索引是基于哈希表构建的，仅在按列进行精确查找时有用。对于每一行，存储引擎都给指定的索引列生成了一个哈希值，这个哈希值与其他行相比，由于索引列的值不同而不同。存储引擎将这个哈希值存储在索引中，并且在哈希表中存储了一个指向数据行的指针。

在MySQL中，只有Memory存储引擎明确支持哈希索引，这是Memory数据表中默认的索引类型（该存储引擎也支持二叉树索引）。Memory存储引擎只是重复的哈希索引，这在数据库界中并不常见。如果不同行的索引列的值相同，它们也就有相同的哈希值，因此这些行的指针会通过链表存入同一个哈希表的索引中。
下面是一个例子：

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

数据表包括如下数据：

mysql> SELECT * FROM testhash;

fname	lname
Arjen	Lentz
Baron	Schwartz
Peter	Zaitsev
Vadim	Tkachenko

假设索引使用一个虚构的哈希函数f()，对应不同的fname返回的结果如下所示：

f('Arjen')= 2323
f('Baron')= 7437
f('Peter')= 8784
f('Vadim')= 2458

则索引的数据结构类型下面的表格：

Slot	Value
2323	指向第一行
2458	指向第4行
7437	指向第2行
8784	指向第3行

需要注意的是哈希值的Slot是有序的，但是数据行并不是有序的。假设我们执行下面的SQL：

mysql> SELECT lname FROM testhash WHERE fname='Peter';

MySQL首先会计算Peter字符串的哈希值，以用来找到对应的数据行。由于f('Peter')=8784，因此MySQL会找到8784对应的Slot，然后找到第3行，最后一个步骤是比较第3行的列的值是否与Peter一致。
由于索引自身只存储短的哈希值，因此哈希索引十分简洁。其结果是，查找起来像闪电一般快！有得有失，哈希索引还有一些限制：

由于索引仅仅包含哈希值和数据行指针，因此读取完索引后不能得到数据行的值。幸运的是，读取记忆行(in-memory rows)的速度很快，因此这个限制一般不会有什么影响。
MySQL无法使用哈希索引进行排序，因为他们并没有将数据行按序排列。
哈希索引不支持部分值匹配，这是因为他们是计算完整索引列值的哈希值。所以，如果你有一个索引在(A,B)上，那WHERE语句中如果只使用了A，索引不会有任何帮助。
哈希索引只支持相等的比较操作符，如=，IN()，和<=>（注意这个操作符和<>并不相同）。因此在范围查询时并不起作用，例如WHERE price > 100。
访问哈希索引的数据是很快，但是如果出现了哈希冲突（很多值拥有相同的哈希值）另说了。当有冲突时，存储引擎必须在数据行链表里逐个比较行的值是否与查询的值一致。
如果存在很多哈希冲突，一些索引的维护操作可能会很慢。例如，如果你在一个列创建了哈希索引，但这个列的差异性很低（相同值过多，存在很多哈希冲突）。如果要从数据表删除一行，通过索引找到这一行的代价可能会很高。存储引擎需要对索引指向的数据行链表进行遍历，知道找到要删除的行。

这些限制使得哈希索引只在特殊的场景中有用。然而，如果他们适用于应用需求，可以极大地改善性能。一个例子是在数据仓库应用中，一个典型的“star”事务需要连接很多表查询，这个时候如果建立哈希索引将十分高效。

除了Memory存储引擎明确支持哈希索引外，NDB集群存储引擎也支持唯一哈希索引。InnoDB存储引擎有个特性叫做自适应哈希索引。当InnoDB引擎发现有些索引值经常被访问，它就会在内存中构建二叉树之上的索引，这赋予了二叉树一些哈希索引的特性，例如快速的哈希查找。这个过程是全自动的，你不可以控制或配置，只是可以禁用这一特性。

如果你的存储引擎不支持哈希索引，也可以通过模仿InnoDB的方式实现哈希索引，这能够让你使用哈希索引的特性。例如给长内容的列建立小的索引。实现的思路比较简单：在标准的二叉树上创建一个伪哈希索引，这与真正的哈希索引并不完全一致，因为还是会用到二叉树索引进行查询。但是，它会用到哈希值进行查询，而不是索引列的值。你所需要做的就是在WHERE条件中手动指定一个哈希函数。

一个运用很好的例子是URL查询。URL通常会导致二叉树变得很大，这是因为URL通常比较长，你可能是这样查询URL的：

mysql> SELECT id FROM url WHERE url="http://www.mysql.com";

如果你把url列的索引去掉，而是新增一个url_crc列，然后就可以这样查询：

mysql> SELECT id FROM url WHERE url="http://www.mysql.com" AND url_crc=CRC32("http://www.mysql.com");

这会有效改善查询效率，这是因为MySQL查询优化器会发现url_crc列存储空间更小、且是索引，因此会进行索引查找。即便可能多个行都有相同的url_crc的值，但是通过整数比较找到这些行，再从这些行去查找匹配url行的效率会高很多。另一种方式是启用URL全文索引，但这样会更慢。

这种方式的一个缺陷是需要维护哈希值，你可以手动维护，或者在MySQL 5.0及更高版本，你可以使用触发器。下面的例子是在插入或更新时，如何启用触发器去维护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)
);

现在来创建触发器。我们需要临时修改语句的分隔符，以便于我们使用分号作为触发器的分隔符。

DELIMITER //

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;
//

DELIMITER ;

剩下要做的就是验证触发器确实维护了这个哈希值：

mysql> INSERT INTO pseudohash (url) VALUES ('http://www.mysql.com');
mysql> SELECT * FROM pseudohash;

如果看到在url_crc列上生成了一个整数的CRC值，那触发器就是正常的。

mysql> UPDATE pseudohash SET url='http://www.mysql.com/' WHERE id=1;
mysql> SELECT * FROM pseudohash;

然后，如果对应的url_crc的值发生了改变，就说明更新时触发器也正常工作了。

采用这种方式要避免使用SHA1或MD5，这是因为这两个方法返回的字符串很长，或导致空间浪费和比较查询时变慢。虽然有很多强加密方法设计去减少冲突，但是在这里不应该用。简单的哈希函数只要冲突可接受，性能会更好。如果你的数据表有很多行，而CRC32导致了过多的冲突，可以使用64位的哈希函数。确保这个哈希函数返回整数，而不是字符串。一种方式是只使用MD5函数的部分返回结果，虽然和你自己写的方法相比可能未必那么高效，但是相差不会太多。

如何处理哈希冲突

如果你使用哈希值查找数据，你应该在WHERE语句同时包括哈希值对应的原值：

mysql> SELECT id FROM url WHERE url_crc=CRC32("http://www.mysql.com")
 -> AND url="http://www.mysql.com";

下面的语句有可能不会正常工作，这是因为其他的行的URL也可能会拥有相同的CRC32值。

mysql> SELECT id FROM url WHERE url_crc=CRC32("http://www.mysql.com");

哈希冲突的增长速度会比你想像中的快，就像是潘多拉的盒子一样难以控制。CRC32返回一个32位的整数，因此在93000个不同值中冲突的概率会达到1%。这就是为什么查询的时候需要带上原列进行查询。为了减少冲突，可以使用FNV64函数生成哈希值，它是64位的，速度很快，并且产生的冲突会比CRC32少很多。

数据表还有哈希索引，没听过？

如何处理哈希冲突

猜你喜欢

热点阅读