MySQL索引之哈希索引


mysql-log


0x00.About

索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

从MySQL逻辑架构来看,MySQL有三层架构,第一层连接,第二层查询解析、分析、优化、视图、缓存,第三层,存储引擎。

MySQL逻辑架构

索引通过分开查询片,节省了扫描查找时间,大大提升查询效率。

大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。

索引主要在存储引擎层上,不同的引擎也就有不同的B-Tree算法。



0x01.Hash Index

哈希索引只有Memory, NDB两种引擎支持,Memory引擎默认支持哈希索引,如果多个hash值相同,出现哈希碰撞,那么索引以链表方式存储。

但是,Memory引擎表只对能够适合机器的内存切实有限的数据集。

要使InnoDB或MyISAM支持哈希索引,可以通过伪哈希索引来实现,叫自适应哈希索引。

主要通过增加一个字段,存储hash值,将hash值建立索引,在插入和更新的时候,建立触发器,自动添加计算后的hash到表里。

直接索引

假如有一个非常非常大的表,如下:

CREATE TABLE IF NOT EXISTS `User` (
  `id` int(10) NOT NULL COMMENT '自增id',
  `name` varchar(128) NOT NULL DEFAULT '' COMMENT '用户名',
  `email` varchar(128) NOT NULL DEFAULT '' COMMENT '用户邮箱',
  `pass` varchar(64) NOT NULL DEFAULT '' COMMENT '用户密码',
  `last` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '最后登录时间',
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

这个时候,比如说,用户登陆,我需要通过email检索出用户,通过explain得到如下:

mysql> explain SELECT id FROM User WHERE email = ‘ooxx@gmail.com’ LIMIT 1;

+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | User  | ALL  | NULL          | NULL | NULL    | NULL | 384742 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+

发现 rows = 384742 也就是要在384742里面进行比对email这个字段的字符串。

这条记录运行的时间是:Query took 0.1744 seconds,数据库的大小是40万。

从上面可以说明,如果直接在email上面建立索引,除了索引区间匹配,还要进行字符串匹配比对,email短还好,如果长的话这个查询代价就比较大。

如果这个时候,在email上建立哈希索引,查询以int查询,性能就比字符串比对查询快多了。

Hash 算法

建立哈希索引,先选定哈希算法,这里选用CRC32。

《高性能MySQL》说到的方法CRC32算法,建立SHA或MD5算法是划算的,本身位数都有可能比email段长了。

INSERT UPDATE SELECT 操作

在表中添加hash值的字段:

mysql> ALTER TABLE User ADD COLUMN email_hash int unsigned NOT NULL DEFAULT 0;

接下来就是在UPDATE和INSERT的时候,自动更新 email_hash 字段,通过MySQL触发器实现:

DELIMITER |
CREATE TRIGGER user_hash_insert BEFORE INSERT ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
CREATE TRIGGER user_hash_update BEFORE UPDATE ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
DELIMITER ;

这样的话,我们的SELECT请求就会变成这样:

mysql> SELECT email, email_hash FROM User WHERE email_hash = CRC32(“F2dgTSWRBXSZ1d3O@gmail.com”) AND email = “F2dgTSWRBXSZ1d3O@gmail.com”;

+----------------------------+------------+
| email                      | email_hash |
+----------------------------+------------+
| F2dgTSWRBXSZ1d3O@gmail.com | 2765311122 |
+----------------------------+------------+

在没建立hash索引时候,请求时间是 0.2374 seconds,建立完索引后,请求时间直接变成 0.0003 seconds。

AND email = "F2dgTSWRBXSZ1d3O@gmail.com" 是为了防止哈希碰撞导致数据不准确。



0x02.Hash Index 缺点

哈希索引也有几个缺点:

  • 索引存放的是hash值,所以仅支持 < = > 以及 IN 操作
  • hash索引无法通过操作索引来排序,因为存放的时候经过hash计算,但是计算的hash值和存放的不一定相等,所以无法排序
  • 不能避免全表扫描,只是由于在memory表里支持非唯一值hash索引,就是不同的索引键,可能存在相同的hash值
  • 如果哈希碰撞很多的话,性能也会变得很差
  • 哈希索引无法被用来避免数据的排序操作



参考:

[1] Baron Scbwartz等 著,王小东等 译;高性能MySQL(High Performance MySQL);电子工业出版社,2010

[2] 《MySQL的B-Tree索引和Hash索引的区别》

[3] 《mysql 索引优化 btree hash rtree》


本文出自 夏日小草,转载请注明出处:http://homeway.me/2015/09/13/mysql-hash-index

-by小草

2015-09-13 15:49:10

Fork me on GitHub