Schema的优化和索引 - 索引的基础 - 索引的类型 - 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集群索引，已经超出了本书的范围。

（编辑：济南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!