MySQL 索引类型之哈希索引

博主： keke996
发布时间：2021 年 03 月 15 日
1649次浏览
暂无评论
4234字数
分类：码农的故事

哈希索引(hash index)基于哈希表实现,只有精确匹配索引中所有列的查询才有效.对于每一行数据,储存引擎都会对所有的索引计算一个哈希码(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;

表中包含如下数据:
fname    lname

1. Arjen    Lentz
 2. Baron    Schwartz
 3. Peter    Zaitsev
 4. 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行的指针

注意每个槽的编号是顺序的,但是数据行不是.现在,来看如下查询:

SELECT lname FROM testhash WHERE fname='Peter';

MySQL先计算'Peter'的哈希值,并使用该值寻找对应的记录指针.因为f('Peter')=8784,suoyi MySQL在索引中查找8784,可以找到指向第3行的指针,最后一步比较第三行的值是否为'Peter',以确保就是要查找的行.

因为索引自身只需存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快.然而,哈希索引也有它的限制:

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

因为折现限值,哈希索引只使用于某些特定的场合.而一旦适合哈希索引,则它带来的性能提升将非常显著.举个例子,在数据仓库应用中有一种经典的"星型" schema,需要关联很多查找表,哈希索引就非常适合查找表的需求.

除了Memory引擎外,NDB集群引擎也支持唯一哈希索引,且在NDB集群引擎中作用非常特殊.

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

**创建自定义哈希索引.**如果存储引擎不支持哈希索引,则可以模拟像InnoDB一样创建哈希索引,这可以享受一些哈希索引的便利,例如只需要很小的索引就可以为超长的键创建索引.
思路很简单:在B-Tree基础上创建一个伪哈希索引.这和真正的哈希索引不是一回事,因为还是使用B-Tree进行查找,但是它使用的哈希值而不是键本身进行索引查找.你需要做的就是在查询的WHERE子句中手动指定使用哈希函数.

下面是一个实例,例如需要储存大量的URL,并需要根据URL进行搜索查找.如果使用B-Tree来储存URL,存储的内柔就会很大,因为URL本身都很长.正常情况下会有如下查询:

SELECT id FROM url WHERE url="http://www.mysql.com";
若删除原来URL列上的索引,而新增一个呗索引的url_crc列,使用CRC32做哈希,就可以使用下面的方式查询:

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列.首先创建如下表:

CREATE TABLE pseudohash(
    id int unsigned NOT NULL auto_incrememt,
    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 INSERT ON pseudohash FOR EACH ROW BEGIN 
    SET NEW.url_crc=crc32(NEW.url);
    END;
    //
    
    DELIMITER;

剩下的工作就时验证一下触发器如何维护哈希索引了.

如果采用这种方式,记住不要使用SHA1()和MD5()作为哈希函数.因为这两个函数计算处理啊的哈希值是非常长的字符串,会浪费大量空间,比较时也会更慢.SHA1()和MD5()是强加密函数,设计目标是最大限度消除冲突,单这里并不需要这样高的要求.简单哈希函数的冲突在一个可以接受的范围,同样又能提供更好的性能.

如果数据表非常大,CRC32()会出现大量的哈希冲突,则可以考虑自己实现一个简单的64位哈希函数.这个自定义函数需要返回证书,而不是字符串.一个简单的办法可以使用MD5()函数返回值的一部分来作为自定义哈线函数.这可能比自己写一个哈希算法的性能要差,不过这样实现最简单.

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

SELECT id WHERE url_crc=CRC32("http://www.mysql.com")
    AND url="http://www.mysql.com";
一旦出现哈希冲突,另一个字符串的哈希值也恰好是1560514994则下面的查询是无法正确工作的.
    SELECT id WHERE url_crc=CRC32("http://www.mysql.com")

因为所谓的"生日悖论"(生日悖论是指在不少于 23 个人中至少有两人生日相同的概率大于 50%。例如在一个 30 人的小学班级中，存在两人生日相同的概率为 70%。对于 60 人的大班，这种概率要大于 99%。从引起逻辑矛盾的角度来说，生日悖论是一种 “佯谬”。但这个数学事实十分反直觉，故称之为一个悖论。).
出现哈希冲突的概率增长速度可能比想象的要快的多.CRC32()返回的是32位的证书,当索引有93 000条记录是出现冲突的概率是1%.
要避免冲突问题,必须在WHERE条件中带入哈希值和对应列值.如果不是想查询具体指,例如只是统计记录数(不精确的),则可以不带入列值,直接使用CRC32()的哈希值查询即可.还可以使用如FNV64()函数作为哈希函数,这是移植自Percona Server的函数,可以以插件的方式在任何MySQL版本中使用,哈希值为64位,速度快,且冲突比CRC32()要小很多.

最后修改：2021 年 03 月 15 日 10 : 14 AM

随便看看就好,打赏个一毛两毛也不错

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

w4j1e
我想当个公交车司机，或者奶茶店兑奶茶粉的老板＞﹏＜
陶小桃Blog
境外的直接禁止访问，可以减少很多无畏的损失，这个地址是美国内华...
Lsnow
太惨了
W4J1e
今天也被刷了，从头天中午12点刷到第二天上午十点才收到又拍云的...
fish
牛，扫网段扫到了你的博客￣﹃￣

有趣的经历-坐火车1
浏览次数: 2366
有趣的经历-7
浏览次数: 2057
把孤独当做晚餐
浏览次数: 2049
很多事情真的是只有过了那个时间才能看明白
浏览次数: 1861
停电往事
浏览次数: 2549

MySQL 索引类型之哈希索引

keke996 • 2021 年 03 月 15 日

假如设计有如下表

CREATE TABLE testhash(
       fname varchar(50) NOT NULL,
       lname varchar(50) NOT NULL,
       KEY USING HASH(fname)
    )ENGINE=MEMORY;

表中包含如下数据:
fname    lname

1. Arjen    Lentz
 2. Baron    Schwartz
 3. Peter    Zaitsev
 4. 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行的指针

注意每个槽的编号是顺序的,但是数据行不是.现在,来看如下查询:

SELECT lname FROM testhash WHERE fname='Peter';

因为索引自身只需存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快.然而,哈希索引也有它的限制:

除了Memory引擎外,NDB集群引擎也支持唯一哈希索引,且在NDB集群引擎中作用非常特殊.

SELECT id FROM url WHERE url="http://www.mysql.com";
若删除原来URL列上的索引,而新增一个呗索引的url_crc列,使用CRC32做哈希,就可以使用下面的方式查询:

这样的实现缺陷是需要维护哈希值.可以手动维护,也可以使用触发器实现.下面的案例演示了触发器如何在插入和更新时维护url_crc列.首先创建如下表:

CREATE TABLE pseudohash(
    id int unsigned NOT NULL auto_incrememt,
    url varchar(255) NOT NULL,
    url_crc int unsigned NOT NULL DEFAULT 0,
    PRIMARY KEY(id)
    );

然后创建触发器.先修改一下语句分隔符,这样就可以在触发器定义中使用分号;

剩下的工作就时验证一下触发器如何维护哈希索引了.

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

MySQL 索引类型之哈希索引

发表评论取消回复

tp5.1中数据操作where条件的分组以及FIND_IN_SET的数组表达式

一个人吃饭真累

弄堂口的炸串

我手贱啊，改数据库没加where啊，全没了啊

教练，我想学画画

有趣的经历-坐火车1

有趣的经历-7

把孤独当做晚餐

很多事情真的是只有过了那个时间才能看明白

停电往事

MySQL 索引类型之哈希索引

发表评论 取消回复

MySQL 索引类型 之 哈希索引

发表评论取消回复

MySQL 索引类型之哈希索引