概述
数据库中经常用到的索引包括hash索引和B树索引。
定义
哈希索引（hash index）是基于hash表实现的。
当某列需要创建hash索引时，存储引擎会将该列所有的值分别通过hash函数生成一个hash编码，不同的值计算出来的hash编码也不一样。存储引擎将hash编码按顺序存储在索引中，同时在hash表中存储指向对应数据行的指针。若出现hash冲突，则使用链表存储不同的对应指针。
原理
hash散列
优势
- 访问hash索引一般比较快，因为是一次定位到具体hash编码。
- hash码一般比较精简，对于数据值比较长的情况下，能节省索引空间。
劣势
- hash索引无法进行范围查找，只能进行等值比较查询。
- hash索引是按照hash码顺序存储的，不是按照数据值顺序存储，所以无法进行排序。
- hash索引只包含hash码和对应行指针，不存储数据值。所以不能避免读取数据行的操作。
- hash索引无法进行部分列匹配查询，因为hash索引是使用全部数据值进行计算hash编码的。
- 当达到一定数据规模后，会产生hash冲突，若冲突严重时维护索引的成本会增高。每次都要遍历链表进行更新索引
结合优化
MySQL中InnoDB存储引擎有一个功能叫自适应哈希索引，它将B树索引和hash索引进行了结合。
思路
在内存中基于B树之上创建伪hash索引，即将原本存在B树节点上的数据值变成存储该数据值的hash码。
当进行数据查找的时候根据该数据值的hash码进行查找（在B树上），找到hash码后再根据对应hash表找到对应数据行。
应用优势
当数据值很长（比如URL），若完全以B树构建索引，则空间很大。若以上述方式构建索引（先将值hash，然后在构建成B树索引）则会节省空间。并且使用hash码在B树上查找也能增加效率（整数比较）。
缺点
为避免hash冲突造成的影响，where查询条件中一般需要包含该常量值。否则可能出现冗余/不正确的返回结果。
select id
from url
where url_crc = CRC32("www.baidu.com")
and url = "www.baidu.com"
// url_crc 为构建了自适应索引的列
网友评论