MySQL中内置哈希索引及自定义哈希索引

1. 介绍

哈希索引是基于哈希表实现,只有精确匹配索引所有列的查询才有效。例如:

1
SELECT name FROM user WHERE url = 'https://pushy.site';

存储引擎会将索引列(这里的site)的所有行都计算一个哈希码,并存储在哈希表中,用来保存指向每个数据行的指针

TIM截图20190226175427.png

但是如果多个列的哈希值相同,索引将会以链表的形式存放多个记录指针到同一个哈希条目中。

2. 应用

2.1 内置索引

我们可以通过如下的SQL语句在创建表时生成url的索引:

1
2
3
4
5
CREATE TABLE user (
name VARCHAR(50) NOT NULL,
url VARCHAR(255) NOT NULL,
KEY USING HASH(url)
) ENGINE = MEMORY;

注意到,这里我们将表的引擎指定为Memory,因为在MySQL中,只有Memory引擎显式支持哈希索引。但是InnoDB引擎有一个特殊的功能叫做自适应哈希索引

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

执行完SQL语句之后,我们可以看到引擎为url列创建了哈希索引,且索引的方法为HASH

TIM截图20190226180621.png

接下来我们创建一个无索引但相同字段的表user_no_hash进行对比,这里我们同时向两张表插入一万条数据。因为我们需要剖析单条查询的速度,我们需要打开查询剖析工具,执行下面的SQL语句:

1
2
mysql> set profiling = 1;
Query OK, 0 rows affected, 1 warning (0.00 sec)

接下来在索引表中执行精确的条件查询:

1
2
3
4
5
6
7
mysql> select name from user where url = 'https://helloworld/8947';
+-------------+
| name |
+-------------+
| people 8947 |
+-------------+
1 row in set (0.00 sec)

然后在非建立索引表执行同样的查询语句:

1
2
3
4
5
6
mysql> select name from user_no_hash where url = 'https://helloworld/8947';
+-------------+
| name |
+-------------+
| people 8947 |
+-------------+

最后执行show profiles每条查询语句的剖析记录:

1
2
3
4
5
6
7
8
mysql> show profiles;                                                                           
+----------+------------+---------------------------------------------------------------------+
| Query_ID | Duration | Query |
+----------+------------+---------------------------------------------------------------------+
| 8 | 0.00038625 | select name from user where url = 'https://helloworld/8947' |
| 9 | 0.00705800 | select name from user_no_hash where url = 'https://helloworld/8947' |
+----------+------------+---------------------------------------------------------------------+
9 rows in set, 1 warning (0.00 sec)

可以看到,非索引表的查询时间大概是建立哈希索引的表查询时间的23倍左右,其实表中数据量还不是很大。在数据量越大的情况下,索引快速查询的效果更加明显。

2.2 自定义哈希索引

如果存储引擎不支持哈希索引的话,我们可以在B-Tree基础上创建一个伪哈希索引,唯一不同的是,需要做的就是在查询的 WHERE 子句中手动指定使用哈希函数

例如对于下面的查询语句来说,根据url进行条件查找,因为URL本身一般都很长,存储的内容较大,查找的速度也会低下:

1
SELECT id FROM pseudohash WHERE url = 'https://pushy.site';

自定义索引的做法是:新增一个被索引的url_crc列,使用CRC32作为哈希函数,使用下面的方式进行查询。AND条件是避免哈希冲突的情况出现,查找出多条记录

1
2
SELECT id FROM pseudohash WHERE url_crc = CRC32('https://pushy.site')
AND url = 'https://pushy.site';

不过这样实现的缺陷是需要维护哈希值,可以在插入和更新操作时手动维护:

1
2
INSERT INTO pseudohash (url, url_crc) 
VALUES ('https://example.com', CRC32('https://example.com'));

或者通过触发器来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
//

这样在插入记录时不用手动维护哈希值了:

1
INSERT INTO pseudohash (url) VALUES ('https://example.com');

3. 缺点

当然,哈希索引也有他的缺陷和限制:

  • 并不是按照索引值顺序存储的,所以无法用于排序;
  • 哈希索引只支持等值比较查询,包括=IN()<=>
  • 当有很多哈希冲突(不同索引列值却有相同的哈希值),会影响查询速度和提高维护代价。
Pushy wechat
欢迎订阅我的微信公众号