「Mysql索引原理（三）」Mysql中的Hash索引原理

2020-09-04 10:11:05 浏览数 (1)

Hash索引

概念

基于哈希表实现，只有匹配所有列的查询才有效。对于每一行数据，存储引擎都会对所有索引列计算一个哈希码，哈希码是一个较小的值，不同键值的行计算出的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时保存指向每个数据行的指针。

如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中去。

举例

代码语言：javascript复制
CREATE TABLE `testhash` (
  `fname` varchar(50) DEFAULT NULL,
  `lname` varchar(50) DEFAULT NULL,
  KEY `fname` (`fname`) USING HASH
) ENGINE=MEMORY;

为什么用MEMORY存储引擎，因为mysql只有MEMORY存储引擎显示支持哈希索引。 表包含数据:select * from testhash

假设索引使用哈希函数f()来生成哈希码： f('Arjen')=2323 f('Baron')=7437 f('Peter')=8784 f('Vadim')=2458 则，哈希索引的数据结构是：

哈希表中哈希码是顺序的，导致对应的数据行是乱序的。

看如下查询：

select lname from testhash where fname ='Peter'

Mysql首先计算Peter的哈希值是8784，然后到哈希索引中找到对应的行指针，根据指针找到对应的数据行。 索引只存储哈希码及行指针，所以索引的数据结构非常的紧凑，这也让哈希索引查找速度非常快，但是哈希索引也有他的限制。

哈希索引限制

  1. 哈希索引只保存哈希码和指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过访问内存中的行速度非常快（因为是MEMORY引擎），所以对性能影响并不大
  2. 哈希索引数据并不是按照索引值顺序存储的，所以无法用于排序
  3. 哈希索引不支持部分索引列查找，因为哈希索引始终是使用索引列的全部内容来计算哈希码。 如，在数据列（A,B）上建立哈希索引，如果查询只有数据列A，则无法使用该哈希索引
  4. 哈希索引只支持等值比较查询，包括=、IN()、<=>，不支持范围查询，如where price > 100
  5. 哈希冲突（不同索引列会用相同的哈希码）会影响查询速度，此时需遍历索引中的行指针，逐行进行比较。
  1. 如果哈希冲突很多，一些索引维护操作的代价会很高。

如果从表中删除一行，需要遍历链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。 总结：哈希索引限制多，只适用于一定的场合。而一旦适合哈希索引，它带来的性能提升将非常显著。

自定义哈希索引

在InnoDB中，某些索引值被使用的非常频繁的时候，它会在内存中基于B Tree的基础上再创建一个哈希索引，使其不必要在从根节点就行查找。完全自动的内部行为，用户无法配置或更改。

使用场景

为超长的键创建哈希索引。列值太长，导致索引体积过大，查询速度也会受到影响。

创建思路

增加一个额外哈希列，将列值映射成哈希值，对哈希列进行再进行索引。在where条件处手动指定使用哈希函数。

假设使用的是哈希函数hash()，查询语句如下：

代码语言：javascript复制
select * from table where 列B=
hash('https://blog.csdn.net/qq_26222859/article/details/1')
and 列A=‘https://blog.csdn.net/qq_26222859/article/details/1'

列B还是利用B Tree索引进行查找，只不过我们是利用哈希值而不是列键本身进行索引。

实例

代码语言：javascript复制
CREATE TABLE `url_hash` (
  `url` varchar(255) DEFAULT NULL,
  `url_crc` bigint(10) DEFAULT NULL,
  KEY `HASHINDEX` (`url_crc`) USING BTREE
) ENGINE=InnoDB;

url键查询

代码语言：javascript复制
select * from url_hash where url='https://blog.csdn.net/qq_2622285'

使用mysql自带的CRC32函数对url做哈希处理，就可以使用下面的函数查询

代码语言：javascript复制
select * from url_hash where url_crc=CRC32('https://blog.csdn.net/qq_2622285' ) and  url='https://blog.csdn.net/qq_2622285'

mysql优化器会选择性能高且体积小的基于url_crc列的索引来完成查找，即使用多个相同的索引值，查找仍然很快。

但是，我们需要手动维护crc_url哈希列，可通过触发器在插入和更新时实时维护url_crc列，如下

代码语言：javascript复制
CREATE DEFINER=`root`@`localhost` TRIGGER `CRC_INS` BEFORE INSERT ON `url_hash` FOR EACH ROW begin
set NEW.url_crc=crc32(NEW.url);
end;

CREATE DEFINER=`root`@`localhost` TRIGGER `CRC_UPD` BEFORE UPDATE ON `url_hash` FOR EACH ROW begin
set NEW.url_crc=crc32(NEW.url);
end;

验证:

代码语言：javascript复制
insert into url_hash(url) values ('https://blog.csdn.net/qq_2622285')
select * from url_hash
update url_hash set url ='update'
select * from url_hash

select * from url_hash where url='https://blog.csdn.net/qq_2622285' and url_crc=CRC32('https://blog.csdn.net/qq_2622285')

注意，

1、where语句中必须包含url，避免哈希冲突。

2、mysql同时提供了SHA1()、MD5()两个加密函数，不要使用这两个函数做哈希函数，他们是强加密函数，设计目标是最大限度消除冲突，但计算的哈希值很长，浪费空间且有时更慢。哈希冲突只要在一个可接受的范围内对性能影响并不大。

代码语言：javascript复制
select SHA1('CONGZHIZHI')
select MD5('CONGZHIZHI')

空间数据索引

MyISAM存储引擎支持空间索引，可以用作地理数据存储。和B Tree索引不同，这类索引无需前缀查询。空间索引从所有维度索引数据。查询时，可以有效地使用任意维度来组合查询。必须使用Mysql的GIS相关函数如MBRCONTAINS()等来维护数据。Mysql 的GIS并不完善，大部分人不会使用到这个特性。开源关系数据库中对GIS的解决方案做得比较好的是PostgreSQL的PostGIS。

全文索引

全文索引是一种特殊类型的索引，它查找的是文本中的关键字，而不是直接比较索引中值。全文索引和其他类索引的匹配方式完全不一样。它有许多需要注意的细节，如停用词、词干、复数和布尔搜索等。全文索引更类似于搜索引擎做的事情，而不是简单的where条件匹配。

全文检索 存储 数据库 云数据库SQLServer sql

0 人点赞