Schema的优化和索引 - 索引的基础 - 索引的类型 - Hash索引

Hash索引

Hash索引是建立在Hash table至上的，并且它只对准确查找有效，也就是说，必须查找索引上的每一个列。对于每个行，存储引擎计算了索引列的Hash code。这个hash code是非常小，并且对于其他行不同的数值，这些Hash code也是不相同的。在索引中存储了hash code并且在hash table中存储了一个指针指向每一行。

 

在MySQL中，只有Memory存储引擎支持显式的Hash索引。虽然Memory表也可以使用B-Tree索引，但是它们是默认的索引类型是Hash索引。Memory引擎支持非唯一的Hash索引，这在数据库领域中是不寻常的。如果多个值有相同的Hash code，那么索引就会在在相同的hash table的实体中，使用一个linked list保存这些值所属行的指针。

 

说一个例子吧，假设表结构如下

 

 

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 |

+--------+-----------+

 

假设我们有一个hash的函数叫f(),它会返回如下值（这些都是例子，并不是真实的值）：

 

f('Arjen') = 2323

f('Baron') = 7437

f('Peter') = 8784

f('Vadim') = 2458

 

索引的数据结构为

 

Slot Value

2323 Pointer to row 1

2458 Pointer to row 4

7437 Pointer to row 2

8784 Pointer to row 3

 

要注意的是这个slot是有序的。但是行并不是有序。现在我们执行下面的查询

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

 

MySQL将会计算Peter的hash值，并且用它来找到索引中的指针。因为f(peter)=8784。MySQL会在索引中查找8784，也就找到了它的指针，指向行3。最后一步就是把行3的值和Peter做个比较。来确定是否是正确的行。

 

因为索引本身存储的就是比较短的Hash值，所以hash索引是压缩的。hasn值的长度和列的类型并没有什么关系。对一个tinyint创建一个hash索引的长度和一个值非常大列类型的长度是一样的。

 

因此查找是非常轻量和快速的。然而，hash索引有如下的限制：

 

 

• 因为索引仅仅包含了hash值和行的指针，而并不是数据本身，所以MySQL并不能使用在索引中的值，而去避免读取行。幸运的是，访问内存中的行是非常快的，因此一般来说不太会降低性能。
• MySQL不能对排序使用hash索引。因为它们没有存储排序后的行。
• Hash索引不支持部分键的匹配，因为它们计算的是整个索引值的hash值。所以如果你对（A,B）进行hash索引，并且你的查询仅仅以A的条件进行查询，此时Hash索引就会失效。
• Hash索引只支持是否相等的一些比较。比如=，IN(),<=>操作都可以。（注意<>和<=>不是一样的）。它们不能加速范围查询。比如WHERE PRICE>100。
• 在hash索引访问数据是非常快速的，除非有一些冲突（许多值有相同的hash值）。当冲突出现的时候，存储引擎必须找到每个linked list中的指针所指向的行，并且比较这些行的值和要查找的值作比较，直到找到正确的行。
• 如果有许多hash值冲突，那么索引的维护操作将会非常慢。比如，如果你在一个列上创建了一个索引并且索引值冲突很多，那么之后你从表中删除一个行，从索引找到正确的指针的消耗是非常大的。存储引擎会在Linked list中查找具有相同hash值每一行的指针，然后找到了再删除这个要删除行的引用。

这些限制导致了只有在特殊的情况下才能使用Hash索引。然而，它们如果符合了应用的需求，性能就会有梦幻般的提升。一个例子是关于数据仓库的，经典的star shema需要很多连接来查找表。Hash索引可以准确的找到哪张表是所需的。

除了Memory存储引擎是hash索引，NDB集群存储引擎也支持唯一的hash索引。这个功能主要针对于NDB集群索引，已经超出了本书的范围。

创建自己的hash索引

如果存储引擎不支持hash索引，你可以在InnoDB中自己来模拟创建它们。将会给你一些可以有权访问的hash索引的可取的属性。比如对于非常长的键，一个非常小的索引。

思路很简单：在B-Tree索引之上创建一个伪Hash索引。它和准确的Hash索引有些不同，因为它还是使用B-Tree索引来查找。然而，它会使用键的hash值去查找，而不是键自己本身。你所要做的就是在WHERE条件中手动指定Hash函数。

一个比较合适的例子就是URL的查找。URL经常会使B-TREE索引非常之大，因为它们太长了。一般来说，你查询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上的索引，然会在索引中查找这个值（这个例子中 为1560514994）。即使有很多的行的url_crc相同，它也会通过整数比较的方法非常容易找到这些行，然后在检查它们，找到符合的URL.可选的方案是对url加索引，这会非常的慢。

这个方法的缺点就是需要维护hash值。你可以手动去做或者，在MySQL5.0以上版本使用触发器。下面的例子就是当你insert和update的时候通过触发器来维护crc_url.首先创建一个表

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。这些写起来比较方便

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;

+----+----------------------+------------+

| id | url | url_crc |

+----+----------------------+------------+

| 1 | http://www.mysql.com | 1560514994 |

+----+----------------------+------------+

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

mysql> SELECT * FROM pseudohash;

+----+-----------------------+------------+

| id | url | url_crc |

+----+-----------------------+------------+

| 1 | http://www.mysql.com/ | 1558250469 |

+----+-----------------------+------------+

如果你使用这种方法，不要使用SHA1()和MD5这些hash函数。这些返回了非常长的字符串。这会浪费空间和降低比较的速度。这两个函数密码性很强，也会消除冲突，但在这里这并不是我们的目标。简单的hash函数所造成的冲突是可容忍的并且还有良好的性能。

如果你的表中有很多行，CRC32函数可以造成太多的冲突。你可以自己实现64bit的hash函数。要确定的是，你使用的函数必须返回的是整型，并不是个字符串。实现64bit hash函数的方法是使用MD5所返回的一部分。这可能会比自定义函数的性能要差一些，但是必要时可以这么做。

mysql> SELECT CONV(RIGHT(MD5('http://www.mysql.com/'), 16), 16, 10) AS HASH64;

+---------------------+

| HASH64 |

+---------------------+

| 9761173720318281581 |

+---------------------+

Maatkit(http://maatkit.sourceforge.net)包含了一个自定义函数，实现了一个Fowler/Noll/Vo 64bit hash函数。它的速度也非常快。

处理hash冲突

如果你要使用hash来搜索的话，你必须要在WHERE条件中包含它hash之前的值。比如

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

-> AND url="http://www.mysql.com";

 

下面的语句就不是正确的。因为另一个URL的Hash值也是1560514994,这个语句会把它们都查找出来。

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

 

Hash的冲突情况增长的速度可能超出你的想象。这是由于所谓的Birthday Paradox所引起的。CRC32()返回的一个32bit整型值。因此可能93000值就会有1%的冲突。为了证明这点，我们把/usr/share/dict/words所有word写入到表中。结果写入了98,569行。已经有了一个冲突了。冲突会使以下的查询返回很多行

mysql> SELECT word, crc FROM words WHERE crc = CRC32('gnu');

+---------+------------+

| word | crc |

+---------+------------+

| codding | 1774765869 |

| gnu | 1774765869 |

+---------+------------+

 

正确的查询语句

mysql> SELECT word, crc FROM words WHERE crc = CRC32('gnu') AND word = 'gnu';

+------+------------+

| word | crc |

+------+------------+

| gnu | 1774765869 |

+------+------------+

 

为了避免冲突，你必须在where条件中同时指定这两个条件。如果冲突不是一个问题，就在WHERE条件后仅仅指定CRC32，这个情况下，你可能执行的是关于统计的语句而不需要准确的结果。这样还能获得更高的效率。