mysql哈希索引

文章标签: mysql,mysql索引
2015-1-7 19:21:32     33 人阅读    

         哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的査询才有效。对 于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是 一个较小的值,并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希 码存储在索引中,同时在哈希表中保存指向每个数据行的指针。


        在My SQL中,只有Memory引擎显式支持哈希索引。这也是Memory引擎表的默认索 引类型,Memory引擎同时也支持B-Tree索引。值得一提的是,Memory引擎是支持非 唯一哈希索引的,这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同, 索引会以链表的方式存放多个记录指针到同一个哈希条目中。
           下面来看一个例子。假设有如下表:

CREATE TABLE testhash (
fname VARCHAR(5〇) NOT NULL, lname VARCHAR(5〇) NOT NULL, KEY USING HASH(fname)
)ENGINE=MEMORY;


表中包含如下数据:

mysql> SELECT * FROM testhash;

fname    | lname
Arjen     | Lentz
Baron    | Schwartz
Peter     |Zaitsev
Vadim    | Tkachenko


假设索引使用假想的哈希函数f(),它返回下面的值(都是示例数据,非真实数据):


f(,Arjen')= 2323 f('Baron')= 7437 f('Peter')= 8784 ('Vadim1)= 2458
则哈希索引的数据结构如下:
槽(Slot)      值(Value)
2323           指向第1行的指针
2458          指向第4行的指针
7437           指向第2行的指针
8784          指向第3行的指针


        注意每个槽的编号是顺序的,但是数据行不是。现在,来看如下査询: mysql> SELECT lname FROM testhash WHERE fname='Peter';
MySQL先计算_Pete「_的哈希值,并使用该值寻找对应的记录指针。因为f(Tetef)=8784,所以MySQL在索引中查找8784,可以找到指向第3行的指针,最后一步是比较第三行的值是否为'Peter1,以确保就是要査找的行。


       因为索引自身只需存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引査找的速度非常快。然而,哈希索引也有它的限制:
哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避 免读取行。不过,访问内存中的行的速度很快,所以大部分情况下这一点对性能的 影响并不明显。


         哈希索引数据并不是按照索引值顺序存储的,所以也就无法用于排序。
         哈希索引也不支持部分索引列匹配査找,因为哈希索引始终是使用索引列的全部内 容来计算哈希值的。例如,在数据列(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子句中手动指定使用哈希函数。


           DM>下面是一个实例,例如需要存储大量的URL,并需要根据URL进行搜索査找。如果使 用B-Tree来存储URL,存储的内容就会很大,因为URL本身都很长。正常情况下会有 如下査询:
mysql> SELECT id FROM url WHERE url=nhttp://www.mysql.com";
若删除原来URL列上的索引,而新增一个被索引的u「l_crc列,使用CRC32做哈希,就 可以使用下面的方式査询:
mysql> SELECT id FROM url WHERE url="http://www.mysql.com"
-> AND url_crc=CRC32("http://www.mysql.com");


    这样做的性能会非常高,因为MySQL优化器会使用这个选择性很高而体积很小的基于 u「l_c「c列的索引来完成査找(在上面的案例中,索引值为1560514994)。即使有多个 记录有相同的索引值,査找仍然很快,只需要根据哈希值做快速的整数比较就能找到索 引条目,然后一一比较返回对应的行。另外一种方式就是对完整的URL字符串做索引, 那样会非常慢。


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

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=crcB2(NEW.url);
END; ~
//
CREATE TRIGGER pseudohash_crc_upd BEFORE UPDATE ON pseudohash FOR EACH ROW BEGIN SET NEW.url_crc=crc32(NEwTurl);
END; ~
//
DELIMITER ;


剩下的工作就是验证一下触发器如何维护哈希索引:
mysql> INSERT INTO pseudohash (url) VALUES ('http://www.mysql.com'); mysql> SELECT * FROM pseudohash;
+ +  +  +
| id | url | url_crc |
+ +   + +
| 1 | http://www.mysql.com | 1560514994 |
+ + + +
mysql> UPDATE pseudohash SET url='http://www.mysql.com/' WHERE id=l; mysql> SELECT * FROM pseudohash;
+ + +  +
| id | url | url_crc |
+ +  +  +
| 1 | http://www.mysql.com/ | 1558250469 |
+ +- + +
如果采用这种方式,记住不要使用SHA1()和MD5()作为哈希函数。因为这两个函数计算 出来的哈希值是非常长的字符串,会浪费大量空间,比较时也会更慢。SHA1()和MD5(> 是强加密函数,设计目标是最大限度消除冲突,但这里并不需要这样髙的要求。简单哈 希函数的冲突在一个可以接受的范围,同时又能够提供更好的性能。
如果数据表非常大,CRC32()会出现大量的哈希冲突,则可以考虑自己实现一个简单的 64位哈希函数。这个自定义函数要返回整数,而不是字符串。一个简单的办法可以使用 MD5()函数返回值的一部分来作为自定义哈希函数。这可能比自己写一个哈希算法的性 能要差(参考第7章),不过这样实现最简单:
mysql> SELECT C0NV(RIGHT(MD5(,http://www.mysql.com/'), 16), 16, 10) AS HASH64;
+---   +
| HASH64 |
+-  +
| 9761173720318281581 |
+ +
处理哈希冲突。当使用哈希索引进行査询的时候,必须在WHERE子句中包含常量值:
mysql> SELECT id FROM url WHERE url_crc=CRC32("http://_.mysql.com")
-> AND url="http://www.mysql.com";
一旦出现哈希冲突,另一个字符串的哈希值也恰好是1560514994,则下面的查询是无法 正确工作的。
mysql> SELECT id FROM url WHERE url_crc=CRC32("http://www.mysql.conT);
因为所谓的“生日悖论” ft5,出现哈希冲突的概率的增长速度可能比想象的要快得多。 CRC32()返回的是32位的整数,当索引有93 000条记录时出现冲突的概率是1%。例如 我们将中的词导入数据表并进行CRC32()计算,最后会有98 569行。 这就已经出现一次哈希冲突了,冲突让下面的查询返回了多条记录:
mysql> SELECT word, crc FROM words WHERE crc = CRC32('gnu,);
+ +- +
| word | crc |
+ +— +
丨 codding 丨 1774765869 丨
gnu I 1774765869 |
+  + +
正确的写法应该如下:
mysql> SELECT word, crc FROM words WHERE crc = CRC32(’gnu’)AND word = •gnu’;
+ +  +
| word | crc |
+ + +
| gnu | 1774765869 |
+ +--- ---+
      要避免冲突问题,必须在WHERE条件中带入哈希值和对应列值。如果不是想査询具体 值,例如只是统计记录数(不精确的),则可以不带入列值,直接使用CRC32()的哈希值 査询即可。还可以使用如FNV64()函数作为哈希函数,这是移植自Percona Server的函 数,可以以插件的方式在任何MySQL版本中使用,哈希值为64位,速度快,且冲突比 CRC32()要少很多。


原文地址:http://www.itmmd.com/201501/454.html
该文章由 萌萌的IT人 整理发布,转载须标明出处。

大型网站架构设计-Solr   上一篇
下一篇  jQuery教程(10)-DOM树操作之内容setter和getter方法

精彩回复
发表评论
姓名:       

《程序员app》专门为程序员量身定做!