索引 - HASH索引详解 - 《MySQL》

自适应哈希索引（adaptive hash index）
创建自定义哈希索引。

哈希索引(hash index) 基千哈希表实现，只有精确匹配索引所有列的查询才有效注4。对千每一行数据，存储引擎都会对所有的索引列计算一个哈希码(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;
+-------+-----------+
| fname | lname     |
+-------+-----------+
| Arjen | lentz     |
| Baron | Schwartz  |
| Peter | Zaitsev   |
| Vadim | Tkachenko |
+-------+-----------+

假设索引使用假想的哈希函数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 fname FROM testhash WHERE fname='Peter';

MySQL 先计算'Peter'的哈希值，并使用该值寻找对应的记录指针。因为f(‘Peter’)=8784, 所以MySQL 在索引中查找8784, 可以找到指向第3 行的指针，最后一步是比较第三行的值是否为'Peter' ，以确保就是要查找的行。因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。
然而，哈希索引也有它的限制：

哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。
哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列(A,B) 上建立哈希索引，如果查询只有数据列A,则无法使用该索引。
哈希索引只支持等值比较查询，包括＝、IN(）、<=>（注意<>和<=>是不同的操作）。也不支持任何范围查询，例如WHERE ``price > 100 。
访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。

因为这些限制，哈希索引只适用于某些特定的场合。而且适合哈希索引，则它带来的性能提升将非常显著。举个例子，在数据仓库应用中有一种经典的“星型”schema, 需要关联很多查找表，哈希索引就非常适合查找表的需求。除了Memory 引擎外， NOB 集群引擎也支持唯一哈希索引（MySQL引擎支持的索引类型），且在NDB 集群引擎中作用非常特殊。

自适应哈希索引（adaptive hash index）

InnoDB 引擎有一个特殊的功能叫做“自适应哈希索引(adaptive hash index)” 。当InnoDB 注意到某些索引值被使用得非常频繁时，它会在内存中基千B-Tree 索引之上再创建一个哈希索引，这样就让B-Tree 索引也具有哈希索引的一些优点，比如快速的哈希查找。这是一个完全自动的、内部的行为，用户无法控制或者配置，不过如果有必要，完全可以关闭该功能。

创建自定义哈希索引。

如果存储引擎不支持哈希索引，则可以模拟像InnoDB 一样创哈希索引，这可以享受一些哈希索引的便利，例如只需要很小的索引就可以为超长的键创建索引。
思路很简单：在B-Tree 基础上创建一个伪啥希索引。这和真正的哈希索引不是一回事，因为还是使用B-Tree 进行查找，但是它使用哈希值而不是键本身进行索引查找。你需要做的就是在查询的WHERE 子旬中手动指定使用哈希函数。
下面是一个实例，例如需要存储大最的URL, 井需要根据URL 进行搜索查找。如果使用B-Tree 来存储URL, 存储的内容就会很大，因为URL 本身都很长。正常情况下会有如下查询：

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

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

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

这样做的性能会非常高，因为MySQL 优化器会使用这个选择性很高而体积很小的基于url_crc列的索引来完成查找（在上面的案例中，索引值为1560514994) 。即使有多个记录有相同的索引值，查找仍然很快，只需要根据哈希值做快速的整数比较就能找到索引条目，然后一一比较返回对应的行。另外一种方式就是对完整的URL 字符串做索引，那样会非常慢。这样实现的缺陷是需要维护哈希值。可以手动维护，也可以使用触发器实现。下面的案例演示了触发器如何在插入和更新时维护url_crc 列。首先创建如下表和触发器：

mysql> show create table url_tab \G;
*************************** 1. row ***************************
       Table: url_tab
Create Table: CREATE TABLE `url_tab` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `url` varchar(255) NOT NULL,
  `url_crc` int(10) unsigned NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

mysql> delimiter ||

mysql> create trigger url_tab_ins before insert on url_tab for each row begin set NEW.url_crc=crc32(NEW.url); end;||
Query OK, 0 rows affected (0.03 sec)

mysql> create trigger url_tab_upd before update on url_tab for each row begin set NEW.url_crc=crc32(NEW.url); end;||
Query OK, 0 rows affected (0.03 sec)

**********************插入测试数据验证**********************
mysql> insert into url_tab(url) values ("www.google.com"), ("www.alibaba.com");
Query OK, 2 rows affected (0.00 sec)

mysql> select * from url_tab;
+----+-----------------+------------+
| id | url             | url_crc    |
+----+-----------------+------------+
|  1 | www.google.com  |  526628817 |
|  2 | www.alibaba.com | 3700551893 |
+----+-----------------+------------+
2 rows in set (0.00 sec)

如果采用这种方式，记住不要使用SHAl( ）和MD5( ）作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大批空间，比较时也会更慢。SHAl( ）和MDS()是强加密函数，设计目标是最大限度消除冲突，但这里并不需要这样高的要求。简单哈希函数的冲突在一个可以接受的范围，同时又能够提供更好的性能。如果数据表非常大， CRC32( ）会出现大批的哈希冲突，则可以考虑自己实现一个简单的64 位哈希函数。这个自定义函数要返回整数，而不是字符串。一个简单的办法可以使用MD5() 函数返回值的一部分来作为自定义哈希函数。

mysql> SELECT CONV(RIGHT(MD5("http://www.mysql.com/"), 16), 16, 10) AS HASH64;
+---------------------+
| HASH64              |
+---------------------+
| 9761173720318281581 |
+---------------------+
1 row in set (0.00 sec)

处理哈希冲突。当使用哈希索引进行查询的时候，必须在WHERE 子句中包含常量值：

mysql> select * from url_tab where url="www.google.com" and url_crc=crc32("www.google.com");
+----+----------------+-----------+
| id | url            | url_crc   |
+----+----------------+-----------+
|  1 | www.google.com | 526628817 |
+----+----------------+-----------+
1 row in set (0.00 sec)

CRC32( ）返回的是32 位的整数，当索引有93 000 条记录时出现冲突的概率是1% 。下面是一个hash冲突的例子：

mysql> select * from url_tab where crc32("codding") = url_crc;
+----+---------+------------+
| id | url     | url_crc    |
+----+---------+------------+
|  3 | codding | 1774765869 |
|  4 | gnu     | 1774765869 |
+----+---------+------------+
2 rows in set (0.00 sec)