SQL性能优化系列——Hash索引的原理[六]

2019年8月19日01:04:17 发表评论 45

上一篇说了B+树的原理,这篇说一下Hash的原理和使用。Hash本身是一个函数,又被称为散列函数,它可以帮助提升检索数据的效率。打个比方,Hash就好像一个智能前台,你只要告诉它想要查找的人的姓名,它就会告诉你这个人的位置,只需要一次交互就可以完成查询,效率非常高。MD5就是Hash函数的一种。

Hash算法是通过某种确定性的算法(如MD5、SHA1、SHA2、SHA3)将输入变为输出。相同的输入永远得到相同的输出。如果想验证两个文件是否相同,只需要对两个文件进行Hash函数运算比较结果是否相同即可。

代码统计Hash检索效率

Python的数据结构中有数组和字典两种,其中数组检索类似于全表扫描,需要对整个数组进行检索。字典是Hash表实现的,存储的是key-value值,数据检索效率很高。

没有对比就没有伤害,例如:

实验1:在数组中添加10000个元素,然后分别对这10000个元素进行检索,最后统计检索时间。

import time
# 插入数据
result = []
for i in range(10000):
       result.append(i)
# 检索数据
time_start=time.time()
for i in range(10000):
       temp = result.index(i)
time_end=time.time()
print('检索时间', time_end-time_start)

运行结果:

检索时间为 1.2436728477478027 秒。

实验2:采用Hash表的形式存储数据,即在Python中采用字典方式添加10000个元素,然后检索这10000个数据,最后统计时间。

import time
# 插入数据
result = {}
for i in range(1000000):
       result[i] = i
# 检索数据
time_start=time.time()
for i in range(10000):
       temp = result[i]
time_end=time.time()
print('检索时间:',time_end-time_start)

运行结果:

检索时间为 0.0019941329956054688 秒。

通过对比,检索效率差别很大。因为Hash算法复杂度为O(1),数组检索数据的算法复杂度为O(n)。

MySQL中的Hash索引

采用Hash进行检索效率非常高,基本上一次检索就可以找到数据,而B+树需要自顶向下依次查找,多次访问节点才能找到数据,中间需要多次I/O操作,从效率上来说Hash比B+树更高。

Hash索引示意图如下:

SQL性能优化系列——Hash索引的原理[六]

键值key通过Hash映射找到bucket。在这里bucket指的是一个能存储一条或多条记录的存储单位。一个桶的结构包含了一个内存指针数组,其中的每一行数据都会指向下一条,形成链表结构,当遇到Hash冲突时,会在桶中进行键值的查找。

什么是Hash冲突?

如果桶的空间小于输入的空间,不同的输入可能会映射到同一个桶中,这时就会产生Hash冲突,如果冲突的量很大,就会影响读取的性能。

Hash索引与B+树索引的区别

1.Hash索引不能进行范围查询,而B+树可以。因为Hash索引指向的数据是无序的,B+树的叶子节点是个有序链表。

2.Hash索引不支持联合索引的最左侧原则(即联合索引的部分索引无法使用),而B+树可以。因为Hash索引在计算Hash值时,是将索引键合并后再一起计算Hash值,所以不会对每个索引单独计算Hash值,因此如果用到联合索引的一个或几个索引时,联合索引无法被利用。

3.Hash索引不支持 ORDER BY 排序,因为 Hash 索引指向的数据是无序的,因此无法起到排序优化的作用,而B+树可以。同理,也无法使用Hash索引进行模糊查询,而B+树使用 LIKE 进行模糊查询的时候,LIKE 后面前模糊查询(%开头)的话可以起到优化作用。

对于等值查询来说,通常Hash索引的效率更高,不过当索引列的重复值很多效率就会很低。因为遇到 Hash 冲突时,需要对桶中的行指针进行比较,找到查询的关键字,非常耗时。所以,Hash 索引通常不会用到重复值多的列上,比如列为性别、年龄的情况等。

总结

Hash 索引存在很多限制,相比之下数据库中B+树索引的使用面更广。不过键值型数据库 Redis 存储的核心就是 Hash 表。

(本文完)

  • 我的微信
  • 微信扫一扫
  • weinxin
  • 微信公众号
  • 微信公众号扫一扫
  • weinxin
  • A+
所属分类:SQL

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: