ITPub博客

mysql hash索引

原创 作者:贺子_DBA时代 时间:2018-01-14 22:05:11 0 删除 编辑
   今天研究下mysql中索引,首先我应该知道的是,mysql中不同存储引擎的索引工作方式不一样,并且不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一种类型的索引,那么他们的实现原理也是不同的。不同的引擎对于索引有不同的支持:Innodb和MyISAM默认的索引是Btree索引;而Mermory默认的索引是Hash索引。
mysql中主要有哈希索引(hash index)、B-Tree索引,全文索引、以及空间数据索引(R-Tree);
今天主要讲下mysql中的哈希索引(hash index)
它是基于哈希表实现,只有精确匹配索引所有列的查询才有效,对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,大部分情况下不同的键值的行计算出来的哈希码是不同的,但是也会有例外,就是说不同列值计算出来的hash值一样的(即所谓的hash冲突),哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每一个数据行的指针,hash很适合做索引,为某一列或几列建立hash索引,就会利用这一列或几列的值通过一定的算法计算出一个hash值,对应一行或几行数据。
hash 索引的实现原理如下图:

针对上图的理解:
keys:代表创建索引的列值;
buckets: 就是计算出来的hash值和对应的数据的物理位置组成的hash表;
entries:就是代表具体的数据行;
创建hash索引后,会为每个键值通过特定的算法计算出一个哈希码(hash code),需要注意的是不同的键值计算出来的hash值可能是相同的,例上图上的 John Smith 和Sandra Dee算出来的hash值都是152,然后找到hash值为152在hash表中的存储数据的物理位置,这个位置对应着两条数据也(就是John Smith 521-1234 和Sandra Dee 521-9655),然后再次遍历这两条数据,找到需要的数据,这就解释了为啥hash冲突严重了,hash索引效率降低的原因。
hash索引检索数据的过程(摘杂网络)
当我们为某一列或某几列建立hash索引时(目前就只有MEMORY引擎显式地支持这种索引),会在硬盘上生成类似如下的文件:
hash值 存储地址
1db54bc745a1 77#45b5
4bca452157d4 76#4556,77#45cc…
hash值即为通过特定算法由指定列数据计算出来,存储地址即为所在数据行存储在硬盘上的地址(也有可能是其他存储地址,其实MEMORY会将hash表导入内存)。
这样,当我们进行WHERE age = 18 时,会将18通过相同的算法计算出一个hash值==>在hash表中找到对应的储存地址==>根据存储地址取得数据==>最后一步确定这行数据是否是需要查询的数据。
所以,每次查询时都要遍历hash表,直到找到对应的hash值,数据量大了之后,hash表也会变得庞大起来,性能下降,遍历耗时增加;
MySQLhash索引的适用情况:
检索时不需要类似B+树那样从根节点到叶子节点逐级查找,只需一次哈希算法即可立刻定位到相应的位置,速度非常快,但是哈希索引只适合某些特定的场景,而一旦适合哈希索引,则它带来的性能提升非常明显,除了memory引擎外,NDB引擎也支持唯一哈希索引;
innodb引擎有一个特殊的功能叫做自适应哈希索引,当innodb注意到某些索引值被使用的非常频繁时,它会在内存中基于btree索引之上再创建一个哈希索引,这样就让btree索引也具有哈希索引的一些优点,比如:快速的哈希查找,这是一个全自动的,内部的行为,用户无法控制或者配置,不过如果有必要,可以选择关闭这个功能(innodb_adaptive_hash_index=OFF,默认为ON)。
正是因为hash表在处理较小数据量时具有无可比拟的素的优势,所以hash索引很适合做缓存(内存数据库)。如mysql数据库的内存版本Memsql,使用量很广泛的缓存工具Mencached,NoSql数据库redis等,都使用了hash索引这种形式。当然,不想学习这些东西的话Mysql的MEMORY引擎也是可以满足这种需求的。
mysql hash索引的局限性:
(1)Hash 索引仅仅能满足"=","IN"和"<=>"的等值查询,不能使用范围查询。 
由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值,所以它只能用于等值的过滤,不能用于基于范围的过滤,因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系,并不能保证和Hash运算前完全一样。 
(2)因为哈希索引并不是按照索引值顺序存储的,所以Hash 索引无法被用来避免数据的排序操作。 由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值,而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样,所以数据库无法利用索引的数据来避免任何排序运算; 
(3)Hash 索引不能利用部分索引键查询,也就是针对组合索引,不支持最左匹配原则
对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用,也就是说,在数据列(A,B)上建立哈希索引,如果查询只有数据列(where A=)是无法使用该索引的。 
(4)Hash 索引在任何时候都不能避免表扫描。 
前面已经知道,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中,由于相同的列值计算出来的 Hash 值可能一样的,所以即使取满足某个 Hash 键值的数据的记录条数,也无法从 Hash 索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。 
(5)Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。 
对于选择性比较低的索引键(存在大量hash冲突,也就是大量重复值,可选择率高代表选出来的值/去重的值 比较大),如果创建 Hash 索引,那么将会存在大量记录指针信息和同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。
(6) 哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行(即不能使用哈希索引来做覆盖索引扫描),不过,访问内存中的行的速度很快(因为memory引擎的数据都保存在内存里),所以大部分情况下这一点对性能的影响并不明显。
(7)如果哈希冲突很多的话,一些索引维护操作的代价也会很高。例如,如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引,那么当从表中删除一行时,存储引擎需要遍历对应哈希值的链表中的每一行,找到并删除对应的引用,冲突越多,代价越大。
总结: 如果hash键值没有重复值,并且数据量较小时,通过hash索引检索数据还是比btree索引快的,但是当哈希值大量重复且数据量非常大时,其检索效率并没有Btree索引高的。哈希索引只适合某些特定的场景,而一旦适合哈希索引,则它带来的性能提升非常明显的,因为它不会像btree索引那样一级一级的去遍历检索得到数据。Hash索引结构的特殊性,让他的检索效率非常高,索引的检索可以一次定位,不像BTree索引需要从根节点到枝节点,最后才能访问到叶节点这样多次的I/O访问,所以Hash索引的查询效率要远高于BTree索引。

请登录后发表评论 登录
全部评论

注册时间:2014-05-12

  • 博文量
    214
  • 访问量
    1486084