腾讯云数据库负责人林晓斌说过:“我们面试 MySQL 同事时只考察两点,索引和锁”。


图片来自 Pexels

言简意赅,MySQL 索引的重要性不言而喻。MySQL 索引历经了多个版本的迭代,从语法到底层数据结构都有很多改变。

MySQL 索引,我们真的了解么?好了,今天我们一起来看看 MySQL 索引的前世今生,一起聊聊索引的那些事儿。

什么是索引?

在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

索引的作用相当于图书的目录,可以根据目录中的页码快速找到所需的内容。

当表中有大量记录时,若要对表进行查询:

  • 第一种搜索信息方式是全表搜索,是将所有记录一一取出,和查询条件进行一一对比,然后返回满足条件的记录,这样做会消耗大量数据库系统时间,并造成大量磁盘 I/O 操作。

  • 第二种就是在表中建立索引,然后在索引中找到符合查询条件的索引值,最后通过保存在索引中的 ROWID(相当于页码)快速找到表中对应的记录。

MySQL 5.5 以后 InnoDB 储引擎使用的索引数据结构主要用:B+Tree;本篇文章带大家以 B+Tree 前世今生为主线来聊一聊。

Mark:B+Tree 可以对 <,<=,=,>,>=,BETWEEN,IN,以及不以通配符开始的 LIKE 使用索引。(MySQL 5.5 后)

这些事实或许会颠覆你的一些认知,比如在你读过的其他文章或书中。以上这些都属于“范围查询”,都是不走索引的!

没错,早在 5.5 以前,优化器是不会选择通过索引搜索的,优化器认为这样取出的行多与全表扫描的行,因为还要回表查一次嘛,可能会涉及 I/O 的行数更多,被优化器放弃。

经过算法(B+Tree)优化后,支持对部分范围类型的扫描(得利与 B+Tree 数据结构的有序性)。

该做法同时也违反了最左前缀原则,导致范围查询后的条件无法用到联合索引,我们在后面详细说明。

索引的优缺点

索引的优点如下:

  • 索引大大减小了服务器需要扫描的数据量。

  • 索引可以帮助服务器避免排序和临时表。

  • 索引可以将随机 I/O 变成顺序 I/O。

索引的缺点如下:

  • 虽然索引大大提高了查询速度,同时却会降低更新表的速度,如对表进行 INSERT、UPDATE 和 DELETE。因为更新表时,MySQL 不仅要保存数据,还要保存索引文件。

  • 建立索引会占用磁盘空间的索引文件。一般情况这个问题不算严重,但如果你在一个大表上创建了多种组合索引,且伴随大量数据量插入,索引文件大小也会快速膨胀。

  • 如果某个数据列包含许多重复的内容,为它建立索引就没有太大的实际效果。

  • 对于非常小的表,大部分情况下简单的全表扫描更高效。

因此应该只为最经常查询和最经常排序的数据列建立索引。(MySQL 里同一个数据表里的索引总数限制为 16 个)

数据库存在的意义之一就是是解决数据存储和快速查找的。那么数据库的数据存在哪?没错,是磁盘,磁盘的优点是啥?便宜!缺点呢?相比内存访问速度慢。

那么你知道 MySQL 索引主要使用的数据结构么?B+树!你脱口而出。

那 B+树是什么样的数据结构?MySQL 索引又是为什么选择了 B+树呢?

其实最终选用 B+树是经历了漫长的演化:

二叉排序树 → 二叉平衡树 → B-Tree(B树) → B+Tree(B+树)

有小伙伴问我“B 树跟 B-树有什么区别”?这里普及一下,MySQL 数据结构只有B-Tree(B 树)和 B+Tree(B+树),多只是读法不同罢了,“B-Tree” 一般统称为 B 树,你叫他 B-树也行!

还有小伙伴提到的红黑树,是编程语言中的存储结构,不是 MySQL 的;如 Java 的 HashMap 就是用的链表加红黑树。

好了,今天就带着大家一起看一下演化成 B+树的过程吧。

B+Tree 索引的前世今生

①二叉排序树

理解 B+树之前,简单说一下二叉排序树,对于一个节点,它的左子树的孩子节点值都要小于它本身,它的右子树的孩子节点值都要大于它本身。

如果所有节点都满足这个条件,那么它就是二叉排序树。(此处可以串一下二分查找的知识点)

上图是一颗二叉排序树,你可以尝试利用它的特点,体验查找 9 的过程:

  • 9 比 10 小,去它的左子树(节点 3)查找。

  • 9 比 3 大,去节点 3 的右子树(节点 4)查找。

  • 9 比 4 大,去节点 4 的右子树(节点 9)查找。

  • 节点 9 与 9 相等,查找成功。

一共比较了 4 次,那你有没有想过上述结构的优化方式?

②AVL 树(自平衡二叉查找树)

上图是 AVL 树,节点个数和值均和二叉排序树一摸一样。

再来看一下查找 9 的过程:

  • 9 比 4 大,去它的右子树查找。

  • 9 比 10 小,去它的左子树查找。

  • 节点 9 与 9 相等,查找成功。

一共比较了 3 次,同样的数据量比二叉排序树少了一次,为什么呢?因为 AVL 树高度要比二叉排序树小,高度越高意味着比较的次数越多;不要小看优化的这一次,假如是 200w 条数据,比较次数会明显地不同。

你可以想象一下一棵 100 万节点的平衡二叉树,树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。

也就是说,对于一个 100 万行的表,如果使用二叉树来存储,单独访问一个行可能需要 20 个 10 ms 的时间,这个查询可真够慢的!

③B 树(Balanced Tree)多路平衡查找树,多叉的

B 树是一种多路自平衡搜索树,它类似普通的二叉树,但是 B 树允许每个节点有更多的子节点。

B 树示意图如下:

B 树的特点如下:

  • 所有键值分布在整个树中。

  • 任何关键字出现且只出现在一个节点中。

  • 搜索有可能在非叶子节点结束。

  • 在关键字全集内做一次查找,性能逼近二分查找算法。

为了提升效率,要尽量减少磁盘 I/O 的次数。实际过程中,磁盘并不是每次严格按需读取,而是每次都会预读。

磁盘读取完需要的数据后,会按顺序再多读一部分数据到内存中,这样做的理论依据是计算机科学中注明的局部性原理:

  • 由于磁盘顺序读取的效率很高(不需要寻址时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高 I/O 效率。预读的长度一般为页(page)的整倍数。

  • MySQL(默认使用 InnoDB 引擎),将记录按照页的方式进行管理,每页大小默认为 16K(可以修改)。

B-Tree 借助计算机磁盘预读机制:每次新建节点的时候,都是申请一个页的空间,所以每查找一个节点只需要一次 I/O;因为实际应用当中,节点深度会很少,所以查找效率很高。

那么最终版的 B+树是如何做的呢?

④B+Tree (B+树是 B 树的变体,也是一种多路搜索树)

从图中也可以看到,B+树与 B 树的不同在于:

  • 所有关键字存储在叶子节点,非叶子节点不存储真正的 data,从而可以快速定位到叶子结点。

  • 为所有叶子节点增加了一个链指针,意味着所有的值都是按顺序存储的,并且每一个叶子页到根的距离相同,很适合查找范围数据。

因此,B+Tree 可以对 <,<=,=,>,>=,BETWEEN,IN,以及不以通配符开始的 LIKE 使用索引。

B+ 树的优点,比较的次数均衡,减少了 I/O 次数,提高了查找速度,查找也更稳定:

  • B+树的磁盘读写代价更低。

  • B+树的查询效率更加稳定。

要知道的是,你每次创建表,系统会为你自动创建一个基于 ID 的聚集索引(上述 B+树),存储全部数据。

你每次增加索引,数据库就会为你创建一个附加索引(上述 B+树),索引选取的字段个数就是每个节点存储数据索引的个数,注意该索引并不存储全部数据。

为什么 MySQL 索引选择了 B+树而不是 B 树?

原因有如下两点:

  • B+树更适合外部存储(一般指磁盘存储),由于内节点(非叶子节点)不存储 data,所以一个节点可以存储更多的内节点,每个节点能索引的范围更大更精确。也就是说使用 B+树单次磁盘 I/O 的信息量相比较 B 树更大,I/O 效率更高。

  • MySQL 是关系型数据库,经常会按照区间来访问某个索引列,B+树的叶子节点间按顺序建立了链指针,加强了区间访问性,所以 B+树对索引列上的区间范围查询很友好。而 B 树每个节点的 key 和 data 在一起,无法进行区间查找。

程序员,你应该知道的索引知识点

①回表查询

比如你创建了 name, age 索引 name_age_index,查询数据时使用了:

select * from table where name ='陈哈哈' and age = 26;

由于附加索引中只有 name 和 age,因此命中索引后,数据库还必须回去聚集索引中查找其他数据,这就是回表,这也是你背的那条:少用 select * 的原因。

②索引覆盖

结合回表会更好理解,比如上述 name_age_index 索引,有查询:

select name, age from table where name ='陈哈哈' and age = 26;

此时 select 的字段 name,age 在索引 name_age_index 中都能获取到,所以不需要回表,满足索引覆盖,直接返回索引中的数据,效率高。是 DBA 同学优化时的首选优化方式。

③最左前缀原则

B+树的节点存储索引顺序是从左向右存储,在匹配的时候自然也要满足从左向右匹配。

通常我们在建立联合索引的时候,也就是对多个字段建立索引,相信建立过索引的同学们会发现,无论是 Oracle 还是 MySQL 都会让我们选择索引的顺序。

比如我们想在 a,b,c 三个字段上建立一个联合索引,我们可以选择自己想要的优先级,a、b、c,或者是 b、a、c 或者是 c、a、b 等顺序。

为什么数据库会让我们选择字段的顺序呢?不都是三个字段的联合索引么?这里就引出了数据库索引的最左前缀原理。

在我们开发中经常会遇到明明这个字段建了联合索引,但是 SQL 查询该字段时却不会使用索引的问题。

比如索引 abc_index:(a,b,c)是 a,b,c 三个字段的联合索引,下列 sql 执行时都无法命中索引 abc_index 的。

select * from table where c = '1'; select * from table where b ='1' and c ='2';

以下三种情况却会走索引:

select * from table where a = '1'; select * from table where a = '1' and b = '2'; select * from table where a = '1' and b = '2'  and c='3';

从上面两个例子大家是否阔以看出点眉目?

是的,索引 abc_index:(a,b,c),只会在(a)、(a,b)、(a,b,c)三种类型的查询中使用。

其实这里说的有一点歧义,其实(a,c)也会走,但是只走 a 字段索引,不会走 c 字段。

另外还有一个特殊情况说明下,下面这种类型的也只会有 a 与 b 走索引,c 不会走。

select * from table where a = '1' and b > '2'  and c='3';

像上面这种类型的 sql 语句,在 a、b 走完索引后,c 已经是无序了,所以 c 就没法走索引,优化器会认为还不如全表扫描 c 字段来的快。

最左前缀:顾名思义,就是最左优先,上例中我们创建了 a_b_c 多列索引,相当于创建了(a)单列索引,(a,b)组合索引以及(a,b,c)组合索引。

因此,在创建多列索引时,要根据业务需求,where 子句中使用最频繁的一列放在最左边。

④索引下推优化

还是索引 name_age_index,有如下 sql:

select * from table where name like '陈%' and age > 26;

该语句有两种执行可能:

  • 命中 name_age_index 联合索引,查询所有满足 name 以"陈"开头的数据, 然后回表查询所有满足的行。

  • 命中 name_age_index 联合索引,查询所有满足 name 以"陈"开头的数据,然后顺便筛出 age>20 的索引,再回表查询全行数据。

显然第 2 种方式回表查询的行数较少,I/O 次数也会减少,这就是索引下推。所以不是所有 like 都不会命中索引。

使用索引时的注意事项

①索引不会包含有 null 值的列

只要列中包含有 null 值都将不会被包含在索引中,复合索引中只要有一列含有 null 值,那么这一列对于此复合索引就是无效的。所以我们在数据库设计时建议不要让字段的默认值为 null。

②使用短索引

对串列进行索引,如果可能应该指定一个前缀长度。

例如,如果有一个 char(255)的列,如果在前 10 个或 20 个字符内,多数值是惟一的,那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和 I/O 操作。

③索引列排序

查询只使用一个索引,因此如果 where 子句中已经使用了索引的话,那么 order by 中的列是不会使用索引的。

因此数据库默认排序可以符合要求的情况下不要使用排序操作;尽量不要包含多个列的排序,如果需要最好给这些列创建复合索引。

④like 语句操作

一般情况下不推荐使用 like 操作,如果非使用不可,如何使用也是一个问题。like “%陈%” 不会使用索引而 like “陈%”可以使用索引。

⑤不要在列上进行运算

这将导致索引失效而进行全表扫描,例如:

SELECT * FROM table_name WHERE YEAR(column_name)<2017;

⑥不使用 not in 和 <> 操作

这不属于支持的范围查询条件,不会使用索引。

我的体会

曾经,我一度以为我很懂 MySQL。

刚入职那年,我还是个孩子,记得第一个需求是做个统计接口,查询近两小时每隔 5 分钟为一时间段的网站访问量,JSONArray 中一共返回 24 个值,当时菜啊,写了个接口循环二十四遍,发送 24 条 SQL 去查(捂脸)。

由于那个接口,被技术经理嘲讽表示他写的 SQL 比我吃的米都多。虽然我们山东人基本不吃米饭,但我还是羞愧不已。

然后经理通过调用一个 dateTime 函数分组查询处理一下,就 OK 了,效率是我的几十倍吧。

从那时起,我就定下目标,深入 MySQL 学习,万一日后有机会嘲讽回去?

筒子们,MySQL 路漫漫,其修远兮。永远不要眼高手低,一起加油,希望本文能对你有所帮助。

作者:陈哈哈

简介:MySQL 社区的非著名贡献者,善于白嫖知识;陪伴 MySQL 五年,致力于高性能 SQL、事务锁优化方面的研究;长路漫漫,希望通过自己的分享让大家少踩一些坑。我是陈哈哈,一个爱笑的程序员。

编辑:陶家龙