乐趣区

我以为我对索引非常了解直到我遇到了阿里面试官

前言

写数据库,我第一时间就想到了 MySQL、Oracle、索引、存储过程、查询优化等等。

不知道大家是不是跟我想得一样,我最想写的是索引,为啥呢?

以下这个面试场景,不知道大家熟悉不熟悉:

面试官:数据库有几千万的数据,查询又很慢我们怎么办?

面试者:加索引。

面试官:那索引有哪些数据类型?索引是怎么样的一种结构?哪些字段又适合索引呢?B+ 的优点?聚合索引和非聚合索引的区别?为什么说索引会降低插入、删除、修改等维护任务的速度?……..

面试者:面试官怎么出我们公司门来着????。

是的大家可能都知道慢了加索引,那为啥加,在什么字段上加,以及索引的数据结构特点,优点啥的都比较模糊或者甚至不知道。

那我们也不多 BB 了,直接开始这次的面试吧。

正文

我看你简历上写到了熟悉 MySQL 数据库以及索引的相关知识,我们就从索引开始,索引有哪些数据结构?

Hash、B+

大家去设计索引的时候,会发现索引类型是可以选择的。

为什么哈希表、完全平衡二叉树、B 树、B+ 树都可以优化查询,为何 Mysql 独独喜欢 B + 树?

我先聊一下 Hash:

大家可以先看一下下面的动图

注意字段值所对应的数组下标是哈希算法随机算出来的,所以可能出现 哈希冲突

那么对于这样一个索引结构,现在来执行下面的 sql 语句:

select * from sanguo where name=’ 鸡蛋 ’

可以直接对‘鸡蛋’按哈希算法算出来一个数组下标,然后可以直接从数据中取出数据并拿到所对应那一行数据的地址,进而查询那一行数据,那么如果现在执行下面的 sql 语句:

select * from sanguo where name>’ 鸡蛋 ’

则无能为力,因为哈希表的特点就是 可以快速的精确查询,但是不支持范围查询

如果做成了索引,那速度也是很慢的,要全部扫描。

问个题外话,那 Hash 表在哪些场景比较适合?

等值查询的场景,就只有 KV(Key,Value)的情况,例如 Redis、Memcached 等这些 NoSQL 的中间件。

你说的是无序的 Hash 表,那有没有有序的数据结构?

有序数组,它就比较优秀了呀,它在等值查询的和范围查询的时候都很 Nice。

那它完全没有缺点么?

不是的,有序的适合静态数据,因为如果我们新增、删除、修改数据的时候就会改变他的结构。

比如你新增一个,那在你新增的位置后面所有的节点都会后移,成本很高。

那照你这么说他根本就不优秀啊,特点也没地方放。

此言差矣,可以用来做静态存储引擎啊,用来保存静态数据,例如你 2019 年的支付宝账单,2019 年的淘宝购物记录等等都是很合适的,都是不会变动的历史数据。

有点东西啊小伙子,那二叉树呢?

二叉树的新增和结构如图:

二叉树的结构我就不在这里多 BB 了,不了解的朋友可以去看看数据结构章节。

二叉树是有序的,所以是支持范围查询的。

但是他的时间复杂度是 O(log(N)),为了维持这个时间复杂度,更新的时间复杂度也得是 O(log(N)),那就得保持这棵树是完全平衡二叉树了。

怎么听你一说,平衡二叉树用来做索引还不错呢?

此言差矣,索引也不只是在内存里面存储的,还是要落盘持久化的,可以看到图中才这么一点数据,如果数据多了,树高会很高,查询的成本就会随着树高的增加而增加。

为了节约成本很多公司的磁盘还是采用的机械硬盘,这样一次千万级别的查询差不多就要 10 秒了,这谁顶得住啊?

如果用 B 树呢?

同理来看看 B 树的结构:

可以发现同样的元素,B 树的表示要比完全平衡二叉树要“矮”,原因在于 B 树中的一个节点可以存储多个元素。

B 树其实就已经是一个不错的数据结构,用来做索引效果还是不错的。

那为啥没用 B 树,而用了 B + 树?

一样先看一下 B 加的结构:

我们可以发现同样的元素,B+ 树的表示要比 B 树要“胖”,原因在于 B + 树中的非叶子节点会冗余一份在叶子节点中,并且叶子节点之间用指针相连。

那么 B + 树到底有什么优势呢?

其实很简单,我们看一下上面的数据结构,最开始的 Hash 不支持范围查询,二叉树树高很高,只有 B 树跟 B + 有的一比。

B 树一个节点可以存储多个元素,相对于完全平衡二叉树整体的树高降低了,磁盘 IO 效率提高了。

而 B + 树是 B 树的升级版,只是把非叶子节点冗余一下,这么做的好处是 为了提高范围查找的效率

提高了的原因也无非是会有指针指向下一个节点的叶子节点。

小结:到这里可以总结出来,Mysql 选用 B + 树这种数据结构作为索引,可以提高查询索引时的磁盘 IO 效率,并且可以提高范围查询的效率,并且 B + 树里的元素也是有序的。

那么,一个 B + 树的节点中到底存多少个元素最合适你有了解过么?

额这个这个?卧 * 有点懵逼呀。

过了一会还是没想出,只能老实交代:这个不是很了解咳咳。

你可以换个角度来思考 B + 树中一个节点到底多大合适?

B+ 树中一个节点为一页或页的倍数最为合适

为啥?

因为如果一个节点的大小小于 1 页,那么读取这个节点的时候其实也会读出 1 页,造成资源的浪费。

如果一个节点的大小大于 1 页,比如 1.2 页,那么读取这个节点的时候会读出 2 页,也会造成资源的浪费。

所以为了不造成浪费,所以最后把一个节点的大小控制在 1 页、2 页、3 页、4 页等倍数页大小最为合适。

你提到了页的概念,能跟我简单说一下么?

首先 Mysql 的基本存储结构是 (记录都存在页里边):

  • 各个数据页 可以组成一个 双向链表
  • 每个数据页中的记录 又可以组成一个 单向 链表
    • 每个数据页都会为存储在它里边儿的记录生成一个 页目录 ,在通过 主键 查找某条记录的时候可以在页目录中使用 二分法快速定位 到对应的槽,然后再遍历该槽对应分组中的记录即可快速找到指定的记录
    • 其他列 (非主键) 作为搜索条件:只能从最小记录开始 依次遍历单链表中的每条记录

所以说,如果我们写 select * from user where username=’ 丙丙 ’ 这样没有进行任何优化的 sql 语句,默认会这样做:

  • 定位到记录所在的页
    • 需要遍历双向链表,找到所在的页
  • 从所在的页内中查找相应的记录
    • 由于不是根据主键查询,只能遍历所在页的单链表了

很明显,在数据量很大的情况下这样查找会 很慢!看起来跟回表有点点像。

哦?回表你聊一下。

卧槽,该死,我嘴干嘛。

回表大概就是我们有个主键为 ID 的索引,和一个普通 name 字段的索引,我们在普通字段上搜索:

select * from table where name = ‘ 丙丙 ’

执行的流程是先查询到 name 索引上的“丙丙”,然后找到他的 id 是 2,最后去主键索引,找到 id 为 2 对应的值。

回到主键索引树搜索的过程,就是 回表 。不过也有方法避免回表,那就是 覆盖索引

哦?那你再跟我聊一下覆盖索引呗?

!!!我这个嘴。。。

这个其实比较好理解,刚才我们是 select *,查询所有的,我们如果只查询 ID 那,其实在 Name 字段的索引上就已经有了,那就不需要回表了。

覆盖索引可以减少树的搜索次数,提升性能,他也是我们在实际开发过程中经常用来优化查询效率的手段。

很多联合索引的建立,就是为了支持覆盖索引,特定的业务能极大的提升效率。

索引的最左匹配原则知道么?

最左匹配原则

  • 索引可以简单如一个列 (a),也可以复杂如多个列 (a,b,c,d),即 联合索引
  • 如果是联合索引,那么 key 也由多个列组成,同时,索引只能用于查找 key 是否 存在(相等),遇到范围查询 (>、<、between、like 左匹配)等就 不能进一步匹配 了,后续退化为线性查找。
  • 因此,列的排列顺序决定了可命中索引的列数

例子:

  • 如有索引 (a,b,c,d),查询条件 a=1 and b=2 and c>3 and d=4,则会在每个节点依次命中 a、b、c,无法命中 d。(c 已经是范围查询了,d 肯定是排不了序了)

总结

索引在数据库中是一个 非常 重要的知识点!

上面谈的其实就是索引 最基本 的东西,N 叉树,跳表、LSM 我都没讲,同时要创建出好的索引要顾及到很多的方面:

  • 最左前缀匹配原则。这是非常重要、非常重要、非常重要(重要的事情说三遍)的原则,MySQL 会一直向右匹配直到遇到范围查询(>,<,BETWEEN,LIKE)就停止匹配。
  • 尽量选择 区分度高的列作为索引,区分度的公式是 COUNT(DISTINCT col)/COUNT(*)。表示字段不重复的比率,比率越大我们扫描的记录数就越少。
  • 索引列不能参与计算,尽量保持列“干净”。比如,FROM_UNIXTIME(create_time)=’2016-06-06′ 就不能使用索引,原因很简单,B+ 树中存储的都是数据表中的字段值,但是进行检索时,需要把所有元素都应用函数才能比较,显然这样的代价太大。所以语句要写成:create_time=UNIX_TIMESTAMP(‘2016-06-06’)。
  • 尽可能的 扩展索引,不要新建立索引。比如表中已经有了 a 的索引,现在要加(a,b)的索引,那么只需要修改原来的索引即可。
  • 单个多列组合索引和多个单列索引的检索查询效果不同,因为在执行 SQL 时,MySQL 只能使用一个索引 ,会从多个单列索引中选择一个限制最为严格的索引(经指正,在 MySQL5.0 以后的版本中,有“合并索引”的策略,翻看了《高性能 MySQL 第三版》,书作者认为: 还是应该建立起比较好的索引,而不应该依赖于“合并索引”这么一个策略)。
  • “合并索引”策略简单来讲,就是使用多个单列索引,然后将这些结果用“union 或者 and”来合并起来

思路文献参考:

《MySQL 实战》

《高性能 MySQL》

最后部分内容来自 ->java3y《索引和锁》

丁奇《MySQL 实战》

絮叨

之前在 B 站传了视频:

大家反馈效果还是 ok 的,我后续会多多尝试的,也希望把改进的建议留言反馈给我。

我去年拍摄了第一个超级粗糙的 vlog:

因为拍摄剪辑手法都很垃圾,我就删了,但是最近又想着放上去,在纠结哈哈,想看留个言我就传了哈哈,我们下期间。

今天丙丙也开始了来杭 16 天后的第一次上班,很开心我们公司在杭州第一批复工的名单中,我已经 16 天没和人这样说过话了,太开心了,不过不能开空调还得开窗户通风,真的是超级超级冷。

这熟悉的工位,这熟悉的显示器,我的眼角又 ……

白嫖不好,创作不易,各位的 点赞 就是丙丙创作的最大动力,我们下篇文章见!

持续更新,未完待续 ……

退出移动版