MySQL索引之哈希索引

fuchenxuan 发布于2019-07-31 15:58 / 2305人阅读

摘要：哈希索引只有两种引擎支持，引擎默认支持哈希索引，如果多个值相同，出现哈希碰撞，那么索引以链表方式存储。要使或支持哈希索引，可以通过伪哈希索引来实现，叫自适应哈希索引。是为了防止哈希碰撞导致数据不准确。

0x00.About

索引（Index）是帮助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 16:27:10

服务器托管私有云 MySQL索引 mysql建立索引 mysql索引原理 mysql建立唯一索引

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/46545.html

MySQL学习笔记之索引

摘要：哈希索引哈希索引基于哈希索引实现，只有精确匹配所有所有列的查询才有效。哈希索引只支持等值比较查询。如果哈希冲突很多的话，一些索引维护代价也会很高。因为这些限制哈希索引只适用于某些特定的场合。建立聚簇索引的方式对主键建立聚簇索引。索引是存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。在数据量较小且负载较低时...

fou7 2019-08-27 14:26 评论0 收藏0
MySQL 的索引理解

摘要：搜索码指定的顺序于文件中记录的物理顺序不同的索引被称为非聚集索引或者辅助索引。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。参考资料卫星数据指的是索引元素所指向的数据记录，比如数据库的某一行。索引 @(数据库)[MySQL] 索引是什么？索引的解释数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询，更新数据库表中数据。值得注意的是...

阿罗 2019-07-31 17:59 评论0 收藏0
读书笔记之MySQL技术内幕

摘要：前言本文内容基本摘抄自技术内幕存储引擎，以供复习之用，没有多少参考价值。这样做是避免类似索引或数据的扫描操作会使缓冲池中的页被刷新出，从而影响缓冲池的效率。的操作发生在以下情况辅助索引页被读取到缓冲池时页追踪到该辅助索引页无可用空间。前言本文内容基本摘抄自《MySQL技术内幕 InnoDB存储引擎》，以供复习之用，没有多少参考价值。想要更详细了解请参考原书。第一章.MySQL体系...

fanux 2019-07-31 17:50 评论0 收藏0
图解MySQL | [原理解析] Adaptive Hash Index 是如何建立的

摘要：本期图解我们为大家解析一下是如何构建的。因此建立的第一关就是只为频繁使用的索引树建立。关卡该索引树上的某个检索条件要被经常使用显而易见，如果我们为了一个很少出现的检索条件建立，肯定是入不敷出的。Adaptive Hash Index（以下简称 AHI）估计是 MySQL 的各大特性中，大家都知道名字但最说不清原理的一个特性。本期图解我们为大家解析一下 AHI 是如何构建的。首先我们思考一下 ...

Tecode 2022-06-28 18:59 评论0 收藏0
关于MySQL的知识点与面试常见问题都在这里

摘要：但是这将严重影响程序的性能。垂直分区的优点在于可以使得行数据变小，在查询时减少读取的数，减少次数。此外，垂直分区可以简化表的结构，易于维护。垂直分区的缺点在于主键会出现冗余，需要管理冗余列，并会引起操作，可以通过在应用层进行来解决。 Java面试通关手册（Java学习指南，欢迎Star，会一直完善下去，欢迎建议和指导）：https://github.com/Snailclimb/Jav...

LeoHsiun 2019-08-15 18:19 评论0 收藏0