SQL必知必会
陈旸
清华大学计算机博士
立即订阅
10179 人已学习
课程目录
已完结 49 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词丨SQL可能是你掌握的最有用的技能
免费
第一章:SQL语法基础篇 (19讲)
01丨了解SQL:一门半衰期很长的语言
02丨DBMS的前世今生
03丨学会用数据库的方式思考SQL是如何执行的
04丨使用DDL创建数据库&数据表时需要注意什么?
05丨检索数据:你还在SELECT * 么?
06丨数据过滤:SQL数据过滤都有哪些方法?
07丨什么是SQL函数?为什么使用SQL函数可能会带来问题?
08丨什么是SQL的聚集函数,如何利用它们汇总表的数据?
09丨子查询:子查询的种类都有哪些,如何提高子查询的性能?
10丨常用的SQL标准有哪些,在SQL92中是如何使用连接的?
11丨SQL99是如何使用连接的,与SQL92的区别是什么?
12丨视图在SQL中的作用是什么,它是怎样工作的?
13丨什么是存储过程,在实际项目中用得多么?
14丨什么是事务处理,如何使用COMMIT和ROLLBACK进行操作?
15丨初识事务隔离:隔离的级别有哪些,它们都解决了哪些异常问题?
16丨游标:当我们需要逐条处理数据时,该怎么做?
17丨如何使用Python操作MySQL?
18丨SQLAlchemy:如何使用Python ORM框架来操作MySQL?
19丨基础篇总结:如何理解查询优化、通配符以及存储过程?
第二章:SQL性能优化篇 (18讲)
20丨当我们思考数据库调优的时候,都有哪些维度可以选择?
21丨范式设计:数据表的范式有哪些,3NF指的是什么?
22丨反范式设计:3NF有什么不足,为什么有时候需要反范式设计?
23丨索引的概览:用还是不用索引,这是一个问题
24丨索引的原理:我们为什么用B+树来做索引?
25丨Hash索引的底层原理是什么?
26丨索引的使用原则:如何通过索引让SQL查询效率最大化?
27丨从数据页的角度理解B+树查询
28丨从磁盘I/O的角度理解SQL查询的成本
29丨为什么没有理想的索引?
30丨锁:悲观锁和乐观锁是什么?
31丨为什么大部分RDBMS都会支持MVCC?
32丨查询优化器是如何工作的?
33丨如何使用性能分析工具定位SQL执行慢的原因?
34丨答疑篇:关于索引以及缓冲池的一些解惑
35丨数据库主从同步的作用是什么,如何解决数据不一致问题?
36丨数据库没有备份,没有使用Binlog的情况下,如何恢复数据?
37丨SQL注入:你的SQL是如何被注入的?
第三章:认识DBMS (7讲)
38丨如何在Excel中使用SQL语言?
39丨WebSQL:如何在H5中存储一个本地数据库?
40丨SQLite:为什么微信用SQLite存储聊天记录?
41丨初识Redis:Redis为什么会这么快?
42丨如何使用Redis来实现多用户抢票问题
43丨如何使用Redis搭建玩家排行榜?
44丨DBMS篇总结和答疑:用SQLite做词云
第四章:SQL项目实战 (3讲)
45丨数据清洗:如何使用SQL对数据进行清洗?
46丨数据集成:如何对各种数据库进行集成和转换?
47丨如何利用SQL对零售数据进行分析?
结束语 (1讲)
结束语 | 互联网的下半场是数据驱动的时代
SQL必知必会
登录|注册

25丨Hash索引的底层原理是什么?

陈旸 2019-08-07
我们上节课讲解了 B+ 树的原理,今天我们来学习下 Hash 的原理和使用。Hash 本身是一个函数,又被称为散列函数,它可以帮助我们大幅提升检索数据的效率。打个比方,Hash 就好像一个智能前台,你只要告诉它想要查找的人的姓名,它就会告诉你那个人坐在哪个位置,只需要一次交互就可以完成查找,效率非常高。大名鼎鼎的 MD5 就是 Hash 函数的一种。
Hash 算法是通过某种确定性的算法(比如 MD5、SHA1、SHA2、SHA3)将输入转变为输出。相同的输入永远可以得到相同的输出,假设输入内容有微小偏差,在输出中通常会有不同的结果。如果你想要验证两个文件是否相同,那么你不需要把两份文件直接拿来比对,只需要让对方把 Hash 函数计算得到的结果告诉你即可,然后在本地同样对文件进行 Hash 函数的运算,最后通过比较这两个 Hash 函数的结果是否相同,就可以知道这两个文件是否相同。
Hash 可以高效地帮我们完成验证的工作,它在数据库中有广泛的应用。今天的课程主要包括下面几个部分:
动手写程序统计一下 Hash 检索的效率。
了解 MySQL 中的 Hash 索引,理解使用它的优点和不足。
Hash 索引和 B+ 树索引的区别以及使用场景。

动手统计 Hash 检索效率

取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《SQL必知必会》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(19)

  • 小智e
    所以老师能在稍微解释一下“自适应 Hash 索引”吗?自己查了一些资料,不是很懂。

    作者回复: 我们先回顾下B+树索引和Hash索引:
    B+树索引是MySQL的默认索引机制,也是大部分
    因为可以使用范围搜索,可以很容易对数据进行排序操作,在联合索引中也可以利用部分索引建进行查询。这些情况下,我们都没法使用Hash索引,是因为Hash索引仅能满足=, <>, IN查询,不能使用范围查询,同时因为数据的存储是没有顺序的,所以在ORDER BY的情况下,还需要对数据重新进行排序。而对于联合索引的情况,Hash值是针对联合索引建合并后一起来计算Hash值,因此无法对单独的一个键或者几个索引键进行查询。

    好了,默认使用B+树作为索引是因为B+树存在着以上的优点,那为什么还需要自适当Hash索引呢?这里,需要了解Hash索引的特点,因为Hash索引结构的特点,导致它的检索数据效率非常高,通常只需要O(1)的复杂度,也就是一次就可以完成数据的检索。虽然Hash索引的使用场景有很多限制,但是优点也很明显,所以MySQL提供了一个自适当Hash索引的功能(Adaptive Hash index)。注意,这里的自适应指的是不需要人工来制定,而是系统根据情况来自动完成的。
    那什么情况下才会使用自适应Hash索引呢?如果某个数据经常会访问到,当满足一定条件的时候,就会将这个数据页的地址存放到Hash表中。这样下次查询的时候,就可以直接找到这个页面的所在位置。需要说明的是:
    1)自适应哈希索引只保存热数据(经常被使用到的数据),并非全表数据。因此数据量并不会很大,可以让自适应Hash放到缓冲池中,也就是InnoDB buffer pool,进一步提升查找效率。

    2)InnoDB中的自适应Hash相当于是“索引的索引”,采用Hash索引存储的是B+树索引中的页面的地址。这也就是为什么可以称自适应Hash为索引的索引。
    采用自适应Hash索引目的是可以根据SQL的查询条件加速定位到叶子节点,特别是当B+树比较深的时候,通过自适应Hash索引可以提高数据的检索效率。

    3)自适应Hash采用Hash函数映射到一个哈希表中,所以对于字典类型的数据查找非常方便
    哈希表是数组+链表的形式。通过Hash函数可以计算索引键值所对应的bucket(桶)的位置,如果产生Hash冲突,如果产生哈希冲突,就需要遍历链表来解决。

    4)是否开启了自适应Hash,可以通过innodb_adaptive_hash_index变量来查看,比如:mysql> show variables like '%adaptive_hash_index';


    所以,总结下InnoDB本身不支持Hash,但是提供自适应Hash索引,不需要用户来操作,而是存储引擎自动完成的。自适应Hash也是InnoDB三大关键特性之一,另外两个分别是插入缓冲(Insert Buffer)和二次写(Double Write)。

    2019-08-22
    1
    21
  • 用0和1改变自己
    1,Hash索引有很大的限制,如联合索引、模糊查询、范围查询,以及列里有重复值多。
    2,需要遍历链表中所有行指针,逐一进行比较,直到找到所有符合条件的

    作者回复: 对的

    2019-08-08
    7
  • Destroy、
    有个疑问,在数组中,针对下标的检索,时间复杂度是O(1)。老师的代码中用的是result.index(i),这个函数用的应该不是下标检索。因为当我把代码改成result[i],检索时间 0.0009975433349609375

    作者回复: 因为我们要找的是某个元素的值,比如我添加的元素是1,3,5,7...99 一共50个元素,如果我想要找7这个元素,你会用7作为下标进行检索,还是将7作为元素值进行查找呢?
    这里就需要检索具体的数值,对于数组来说下标是自动分配的,所以我们需要遍历数组来找到某个数值。
    而对于字典来说,我们就可以创建索引了

    2019-08-07
    5
  • 我行我素
    回复下蒙开强,如果是使用navicat创建索引的时候在后面是可以直接选择索引类型的,如果使用sql创建索引就是在穿件的使用using指定,一般默认是B+
    2019-08-07
    5
  • 蒙开强
    老师,你好,hash索引与B+树索引是在建索引的时候手动指定么

    作者回复: 在MySQL的InnoDB和如果使用的是MySQL的话,我们需要了解下MySQL的存储引擎都支持哪些索引结构,可以参考https://dev.mysql.com/doc/refman/8.0/en/create-index.html)

    针对MySQL 默认的存储引擎InnoDB,或者使用MyISAM存储引擎都会默认使用的是B+树来进行存储,无法使用Hash索引。InnoDB提供的自适应Hash是不需要手动指定的。如果是Memory/Heap,或者是NDB存储引擎,是可以进行选择的(Hash还是B+树)。

    2019-08-07
    3
  • wusiration
    mysql查询中存在着很多范围查询、order by的场景,在这些场景下,B+树的性能好于Hash索引;关键字出现相同Hash码时,会出现hash冲突。

    作者回复: 对的 所以对于一般需求来说,B+树在数据库应用的场景更多,Hash适用一些特殊的需求,比如文件校验,密码学等

    2019-08-08
    1
  • 许童童
    查找某个固定值时 Hash 索引比 B+ 树更快,为什么 MySQL 还要采用 B+ 树的存储索引呢?另外,当两个关键字的 Hash 值相同时会发生什么?
    因为B+ 树的一些特性像范围查询,联合索引的最左侧原则,支持 ORDER BY 排序等Hash索引没有。
    会发生Hash冲突,然后去按key顺序在桶中等值查找。

    作者回复: 对的

    2019-08-07
    1
  • ning先森
    1. [Hash 索引不支持 ORDER BY 排序,因为 Hash 索引指向的数据是无序的,因此无法起到排序优化的作用,而 B+ 树索引数据是有序的,可以起到对该字段 ORDER BY 排序优化的作用。同理,我们也无法用 Hash 索引进行模糊查询,而 B+ 树使用 LIKE 进行模糊查询的时候,LIKE 后面前模糊查询(比如 % 开头)的话就可以起到优化作用。] 没想明白 ?

    2.[hash索引的流程: 键值=>桶=>数据行] 没理解?

    3.[自适应Hash采用Hash函数映射到一个哈希表中,所以对于字典类型的数据查找非常方便
    哈希表是数组+链表的形式。通过Hash函数可以计算索引键值所对应的bucket(桶)的位置,如果产生Hash冲突,如果产生哈希冲突,就需要遍历链表来解决。]

    老师能不能结合图之类的解释下 ? 谢谢.
    2019-11-21
  • Berry Wang
    老师,b+树为什么可以使用最左前缀匹配原则可以解释一下吗?
    2019-11-12
  • 爱思考的仙人球
    hash函数里的桶(bucket)和hive里的桶(bucket)原理是一样的吗?
    2019-10-20
  • 峻铭
    用java代码测试下数组和map的效率呢,将元素增加到1000000,会有惊喜!!!
    2019-09-12
  • Geek_1c165d
    老师有两个问题:
    1、是不是创建的索引,不管是Hash索引还是B树索引都会存储在硬盘上的么?
    2、B树索引的内容以B树的数据结构进行存储,那Hash索引是以什么数据结构进行存储的?
    2019-08-14
  • 马哲富
    老师您好,是不同的索引结构对应不同类型的索引(比如聚集索引、非聚集索引等)吗?另外知道这些底层的索引结构对于一个普通的开发人员的价值点(或者说判断依据)在哪儿呢?
    2019-08-12
  • 渴望飞的哺乳类
    老师,B+ 树使用 LIKE 进行模糊查询的时候,like ‘xx%’ 才会使用到索引吧
    2019-08-11
  • ABC
    感觉Hash索引和Java的HashMap的Hash实现有点像,不过Java用链地址法解决了Hash冲突的问题。

    作者回复: 对 原理上是一样的

    2019-08-08
  • Ashlar
    能不能请老师分别推荐一下学习MySQL,Oracle,sql Server的一些书籍或者资料呢?

    作者回复: 可以看下关于MySQL高性能优化的书籍,如果是数据库初学者也可以先从SQL Server开始,毕竟微软的产品在操作界面上上手简单。书籍有《21天学通SQL Server》《SQL优化最佳实践》《MySQL技术内容:SQL编程》《Oracle从入门到精通》

    2019-08-08
  • 一语中的
    来自信息安全专业,看到这一节hash索引原理中提到hash算法,hash是不可逆的,有种异常熟悉的感觉,嗯,那些年学的安全算法们AES,DES,IDEA,Hash,HMAC...
    2019-08-08
  • Geek_Wison
    前模糊查询具体指啥,能举一个具体的例子吗?比如是指: 'a%' 还是指 '%a' ?

    作者回复: 前模糊查询就是类似 %a 这种,因为在字符串匹配的前面就是模糊查询了

    2019-08-07
  • 许童童
    老师你好,数组检索数据的算法复杂度为 O(n)。
    不应该也是O(1)吗?

    作者回复: 感谢提问,一个数组如果有n个元素,需要遍历完所有的元素才能找到某个元素,所以是O(n),如果是O(1)就是不需要遍历,直接找到那个元素

    2019-08-07
    3
收起评论
19
返回
顶部