MySQL索引算法——哈希算法

曾经终败给现在 2022-05-12 15:40 302阅读 0赞

哈希索引  
哈希索引(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;

表中包含如下数据:  
![70][]  
  
假设索引使用假想的哈希函数f()，它返回下面的值(都是示例数据，非真实数据) :  
f(' Arjen')= 2323f

(' Baron')= 7437

f('Peter')= 8784

f('Vadim' )= 2458  
  
则哈希索引的数据结构如下:  
  
![70 1][]

注意每个槽的编号是顺序的，但是数据行不是。现在，来看如下查询:  
  
      mysql> SELECT 1name FROM testhash WHERE fname=' Peter' ;  
  
      MySQL先计算'Peter'的哈希值，并使用该值寻找对应的记录指针。因为f('Peter')=8784，所以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本身都很长。正常情况下会有如下查询:  
  
      mysql> SELECT id FROM url WHERE url="http: //ww.mysq1.com" ;  
  
      若删除原来URL列.上的索引，而新增-一个被索引的url\_ crc 列，使用CRC32做哈希，就可以使用下面的方式查询:

mysql> SELECT id FROM url WHERE url="http://www.mysq1. com"  
AND url\_ crc=CRC32("http://www.mysq1.com");  
  
这样做的性能会非常高，因为MySQL优化器会使用这个选择性很高而体积很小的基于url\_ crc列的索引来完成查找(在上面的案例中，索引值为1560514994)。即使有多个记录有相同的索引值，查找仍然很快，只需要根据哈希值做快速的整数比较就能找到索引条目，然后----比较返回对应的行。另外一种方式就是对完整的URL字符串做索引,那样会非常慢。  
  
这样实现的缺陷是需要维护哈希值。可以手动维护，也可以使用触发器实现。下面的案例演示了触发器如何在插入和更新时维护url\_ crc 列。首先创建如下表:  
  
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 BEGINET NEW.url\_ crc=crC32(NEW. url);END;/  
  
CREATE TRIGGER pseudohash\_ .CrC\_ upd BEFORE UPDATE ON pseudohash FOR EACH ROW BEGINSET NEW.url\_ crc=crc32(NEW.url);END;  
  
DELIMITER ;

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

![70 2][]  
      如果采用这种方式，记住不要使用SHA1()和MD5()作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大量空间，比较时也会更慢。SHA1() 和MD5()是强加密函数，设计目标是最大限度消除冲突，但这里并不需要这样高的要求。简单哈希函数的冲突在-一个可以接受的范围，同时又能够提供更好的性能。  
  
      如果数据表非常大，CRC32() 会出现大量的哈希冲突，则可以考虑自己实现-一个简单的64位哈希函数。这个自定义函数要返回整数，而不是字符串。一个简单的办法可以使用MD5()函数返回值的一部分来作为自定义哈希函数。这可能比自己写一个哈希算法的性能要差，不过这样实现最简单:  
  
    ![70 3][]  
  
      处理哈希冲突。当使用哈希索引进行查询的时候，必须在WHERE子句中包含常量值:  
  
      mysql> SELECT id FROM url WHERE url\_ crc=CRC32("http://www.mysq1. com")  
  
      AND url="http://www.mysql.com" ;  
  
      一旦出现哈希冲突，另一个字符串的哈希值也恰好是15605 14994，则下面的查询是无法正确工作的。  
  
      mysql> SELECT id FROM url WHERE url\_ crc=CRC32("http://www.mysql.com");  
  
      因为所谓的“生日悖论”，出现哈希冲突的概率的增长速度可能比想象的要快得多。CRC32()返回的是32位的整数，当索引有93 000条记录时出现冲突的概率是1%。例如我们将/usr/shareldictwords中的词导入数据表并进行CRC32()计算,最后会有98 569行。,这就已经出现一-次哈希冲突了，冲突让下面的查询返回了多条记录:

正确的写法应该如下:  
![70 4][]  
要避免冲突问题，必须在WHERE条件中带人哈希值和对应列值。如果不是想查询具体值，  例如只是统计记录数(不精确的)，则可以不带人列值，直接使用CRC32()的哈希值查询即可。还可以使用如FNV64()函数作为哈希函数，这是移植自Percona Server 的函数，可以以插件的方式在任何MySQL版本中使用，哈希值为64位，  速度快，且冲突比CRC32()要少很多。

[70]: /images/20220504/14b66259497e4ac2b0feedfc012fea52.png
[70 1]: /images/20220504/9c8cc7ac2631427bb2565df844a04100.png
[70 2]: /images/20220504/3118e0334b694469ab411f7ea41aef5a.png
[70 3]: /images/20220504/d4659fc0e6df43d4a2bdbebb2acb86b6.png
[70 4]: /images/20220504/8d4b47e1a843401ba3d314f649d20b37.png