查看原文
其他

图解MySQL索引(上)—聊聊索引的分类

李强 Java填坑笔记 2022-07-13

关于MySQL索引相关的内容,一直是一个让人头疼的问题,尤其是对于初学者来说。笔者曾在很长一段时间内深陷其中,无法分清“覆盖索引,辅助索引,唯一索引,Hash索引,B-Tree索引……”到底是些什么东西,导致在面试过程中进入比较尴尬的局面。

很多人可能会抱怨”面试造火箭,工作拧螺丝,很多知识都是为了面试学的,工作中根本用不到!“。庆幸的是,MySQL中索引不仅是面试必考知识,还是工作中用到最为频繁的必备技能,在笔者看来,索引是MySQL中性价比最高的一部分内容

由于MySQL中支持多种存储引擎,在不同的存储引擎中实现略微有所差距,索引下文中如果没有特殊声明,默认指的都是InnoDB存储引擎。

一、底层数据结构

首先,索引是高效获取数据的数据结构。就像书中的目录一样,我们可以通过它快速定位到数据所在的位置,从而提高数据查询的效率。

在MySQL中有许多关于索引的名词和概念,对于初学者来说很容易被迷惑。为了方便理解,我建立了一张表,从具体的案例中尝试说清楚这些概念到底是什么。

Hash索引

正如上文中说到,索引是提高查询效率的数据结构,而能够提高查询效率的数据结构有很多,如二叉搜索树,红黑树,跳表,哈希表(散列表)等,而MySQL中用到了B+Tree和散列表(Hash表)作为索引的底层数据结构。

需要注意的是,MySQL并没有显式支持Hash索引,而是作为内部的一种优化,对于热点的数据会自动生成Hash索引,也叫自适应Hash索引

Hash索引在等值查询中,可以O(1)时间复杂度定位到数据,效率非常高,但是不支持范围查询。在许多编程语言以及数据库中都会用到这个数据结构,如Redis支持的Hash数据结构。具体结构如下:

B+Tree索引

提到B+Tree首先不得不提B-Tree,B-Tree(多路搜索树,并不是二叉的)是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。

B+ 树是基于B-Tree升级后的一种树数据结构,通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入,这与二叉树恰好相反。

MySQL索引的实现也是基于这种高效的数据结构。具体数据结构如下:

笔者首先要声明一下,不要将B树,B-Tree以及B+Tree弄混淆。首先,B-Tree就是B树,中间的“-”是一个中划线,而不是减号,并不存在"B减树"这种数据结构。其次,就是B+Tree和B-Tree实现索引时有两个区别,具体可见下图

①B+Tree只在叶子节点存储数据,而B-Tree的数据存储在各个节点中

②B+Tree的叶子节点间通过指针链接,可以通过遍历叶子节点即可获取所有数据。

B+Tree是一种神奇的数据结构,如果用语言来讲可能会有点费劲,感兴趣的同学可以点击文末数据结构可视化工具,操作一番后想必会有所收获,下图是笔者演示B+Tree的数据插入方式(自下而上)。

二,数据组织方式

根据数据的组织方式,可以分为聚簇索引和非聚簇索引(也叫聚集索引和非聚集索引)。聚簇索引就是按照每张表的主键构造一棵B+Tree,同时叶子节点存放了整张表的行记录数据

在InnoDB中聚簇索引和主键索引概念等价,MySQL中规定所以每张表都必须有主键索引,主键索引只能有一个,不能为null同时必须保证唯一性。建表时如果没有指定主键索引,则会自动生成一个隐藏的字段作为主键索引。

与之对应的则是非聚集索引,非聚集索引又可以称之为为非主键索引,辅助索引,二级索引。主键索引的叶子节点存储了完整的数据行,而非主键索引的叶子节点存储的则是主键索引值,通过非主键索引查询数据时,会先查找到主键索引,然后再到主键索引上去查找对应的数据,这个过程叫做回表(下文中会再次提到)。

需要补充的是MyISAM中索引和数据文件分开存储,所有的索引都是非聚簇索引。B+Tree的叶子节点存储的是数据存放的地址,而不是具体的数据 。

三,包含字段个数

为了能应对不同的数据检索需求,索引即可以仅包含一个字段,也可以同时包含多个字段。单个字段组成的索引可以称为单值索引,否则称之为复合索引(或者称为组合索引或多值索引)。上文中演示的都是单值索引,所以接下来展示一下复合索引作为对比。

复合索引的索引的数据顺序跟字段的顺序相关,包含多个值的索引中,如果当前面字段的值重复时,将会按照其后面的值进行排序。

四,其他分类

唯一索引

唯一索引,不允许具有索引值相同的行,从而禁止重复的索引或键值。系统在创建该索引时检查是否有重复的键值,并在每次使用 INSERT 或 UPDATE 语句添加数据时进行检查, 如果有重复的值,则会操作失败,抛出异常。

需要注意的是,主键索引一定是唯一索引,而唯一索引不一定是主键索引。唯一索引可以理解为仅仅是将索引设置一个唯一性的属性

覆盖索引

上文提到了一个回表的概念,既如果通过非主键索引查询数据时,会先查询到主键索引的值,然后再去主键索引中查询具体的数据,整个查询流程需要扫描两次索引,显然回表是一个耗时的操作。

为了减少回表次数,在设计索引时我们可以让索引中包含要查询的结果,在辅助索引中检索到数据后直接返回,而不需要进行回表操作。

但是需要注意的是,使用覆盖索引的前提是字段长度比较短,对于值长度较长的字段则不适合使用覆盖索引,原因有很多,比如索引一般存储在内存中,如果占用空间较大,则可能会从磁盘中加载,影响性能。当然还有其他原因,具体情况将会在下一篇文章中介绍。

六,总结

本文从不同维度介绍了MySQL中的索引,索引从不同维度划分可以有很多种名称,但是需要明确一个问题就是,索引的本质是一种数据结构,其他索引的划分则是针对实际应用而言。具体分类如下图所示:

目的是让大家对于索引有个初步且清晰的认识,解决What的问题。后续将会针对Why以及How,进行深入探讨,当然,首先应当能区分本章文章中讲述的概念性问题。

数据结构可视化工具:
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

七、Q&A

1. 为什么MySQL索引使用B+Tree实现,而不是搜索二叉树,红黑树或者跳表?

这是一个综合性问题,远不止看起来那么简单,小伙伴们可以把答案写在留言区我们一起探讨,同样笔者将会在下一篇文章中重点介绍为什么,以及如何正确使用索引。


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存