MySQL 模拟创建哈希索引

####简介
先看一张图：
![20170819182900071.jpg](https://0o0.me/usr/uploads/2018/05/4240976806.jpg)
这张图展示了 MySQL 各种引擎所支持的索引情况，可以看到，并不是所有的引擎都是支持`哈希索引`的。
InnoDB 有些特殊，图上虽然没有说它支持`哈希索引`，但给出了如下解释：
> **InnoDB utilizes hash indexes internally for its Adaptive Hash Index feature。**
* Performance benefits are not limited to giant tables with long-running queries. When the same rows are accessed over and over from a table, a feature called the Adaptive Hash Index takes over to make these lookups even faster, as if they came out of a hash table.

> * adaptive hash index
An optimization for InnoDB tables that can speed up lookups using = and IN operators, by constructing a hash index in memory. MySQL monitors index searches for InnoDB tables, and if queries could benefit from a hash index, it builds one automatically for index pages that are frequently accessed. In a sense, the adaptive hash index configures MySQL at runtime to take advantage of ample main memory, coming closer to the architecture of main-memory databases. This feature is controlled by the innodb_adaptive_hash_index configuration option. Because this feature benefits some workloads and not others, and the memory used for the hash index is reserved in the buffer pool, typically you should benchmark with this feature both enabled and disabled.

> * The hash index is always built based on an existing InnoDB secondary index, which is organized as a B-tree structure. MySQL can build a hash index on a prefix of any length of the key defined for the B-tree, depending on the pattern of searches against the index. A hash index can be partial; the whole B-tree index does not need to be cached in the buffer pool.

> * In MySQL 5.6 and higher, another way to take advantage of fast single-value lookups with InnoDB tables is to use the InnoDB memcached plugin. See Section 14.20, “InnoDB memcached Plugin” for details.

InnoDB 引擎有一个特殊功能叫做`自适应哈希索引(adaptive hash index)`，当 InnoDB 注意到某些索引值被频繁使用时，它会在内存中基于 B-Tree 索引之上再创建一个哈希索引，这就让 B-Tree 索引也具备了`哈希索引`的一些优点。这是一个完全自动的、内部的行为，用户是无法控制和配置的，但如果有必要，只能完全关闭该功能（这里说的完全关闭和前面的无法控制和配置应该是指用户无法指定哪些数据库或者哪些表开启或关闭该功能，只能完全关闭或者完全开启）[ 摘自《高性能 MySQL》]。
以上是 InnoDB 引擎自带的做法，对于其他不支持`哈希索引`的引擎呢？我们可以模拟像 InnoDB 一样的做法，但并不是真正意义上的`哈希索引`，因为使用的还是 B-Tree 索引，只是不再是用键本身来索引，而用哈希值来索引。
####模拟创建哈希索引的使用
[ 案例摘自《高性能 MySQL》]
对于以下表结构：
```mysql
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)
);
```
当我们要对 url 进行索引时，由于 url 的长度比较长，所以存储的内容就会很大，这时我们可以增加一个`url_crc`字段来存储`url`的哈希值，这个时候我们去掉原来`url`上的索引，在`url_crc`上添加索引（书中并未提及加索引，但我想肯定是要加的），此时相对于之前的索引速度会有明显提升，一个是对完整的 URL 做索引，而后者则是用整数哈希值做索引，显然数字的比较比字符串的匹配要高效得多。
但上面的做法也有一定的缺陷：需要额外维护`url_crc`字段，如添加、更新操作。
可以用代码手动维护，也可以用触发器。下面我们用触发器来实现：
```mysql
mysql> delimiter //
mysql> create trigger pseudohash_crc_ins before insert on pseudohash for each row begin
    -> set new.url_crc=crc32(new.url);
    -> end;
    -> //
	
mysql> create trigger pseudohash_crc_upd before update on pseudohash for each row begin
    -> set new.url_crc=crc32(new.url);
    -> end;
    -> //
```
插入一条数据做测试：
> insert into pseudohash(url) values('http://0o0.me');

检测结果：
```
mysql> select * from pseudohash;
+----+---------------+------------+
| id | url           | url_crc    |
+----+---------------+------------+
|  1 | http://0o0.me | 1454233175 |
+----+---------------+------------+
```
####哈希冲突问题
以上做法是的用的`crc32`哈希算法来生成哈希值，可以看到这个哈希值的范围是比较小的，对于大量数据的表哈希冲突的概率就会相对较大，可能有人会问那为什么不用`md5`、`sha1`这种冲突率小的哈希算法？原因是这两种算法得出的结果是一个较长的 a-f 0-9 组成的字符串，占用更大的空间，比较的速度也相对的更慢，所以一般不会采用。
假设以上的案例中以下两条记录的 url 哈希值是相同的（即冲突了）：
```
+----+------------------+------------+
| id | url              | url_crc    |
+----+------------------+------------+
|  1 | http://0o0.me    | 1454233175 |
+----+------------------+------------+
|  2 | http://baidu.com | 1454233175 |
+----+------------------+------------+
```
可能有人添加完伪哈希之后的查询语句会由以前的
> select * from pseudohash where url = 'http://0o0.me'

改成
> select * from pseudohash where url_crc = 1454233175

此时会发现本来想查询出 url = 'http://0o0.me' 记录的，却返回了两条记录，把 url = 'http://baidu.com' 的也返回了，所以对于哈希冲突问题，我们的 sql 语句应该写成如下：
> select * from pseudohash where url_crc = 1454233175 and url = 'http://0o0.me'

此时查询的结果将只有一条记录。有人可能会不理解为什么还要加上之前的条件，加上后是否会影响速度？
此时，将 sql 的执行过程在脑海中执行一遍就都懂了：
首先，根据`url_crc`扫描（列上面加了索引，所以速度会非常快，不会进行全表扫描），找到两条记录，然后在这两条记录里进行`url`字段的匹配，如果冲突的哈希值足够少，那么这个查询速度的影响还是非常小的。

MySQL 模拟创建哈希索引

发表评论：