有关MySQL中的索引面试题系列

0    322    6

Tags:

👉 本文共约49915个字,系统预计阅读时间或需188分钟。

本页目录 隐藏

面试中,MySQL 索引相关的问题基本都是一系列问题,都是先从索引的基本原理,再到索引的使用场景,比如:

  • 索引底层使用了什么数据结构和算法?
  • 为什么 MySQL InnoDB 选择 B+tree 作为索引的数据结构?
  • 什么时候适用索引?
  • 什么时候不需要创建索引?
  • 什么情况下索引会失效?
  • 有什么优化索引的方法?
  • .....

MySQL 索引的知识点

今天就带大家,夯实 MySQL 索引的知识点。

有关MySQL中的索引面试题系列

什么是索引?

当你想查阅书中某个知识的内容,你会选择一页一页的找呢?还是在书的目录去找呢?

傻瓜都知道时间是宝贵的,当然是选择在书的目录去找,找到后再翻到对应的页。书中的目录,就是充当索引的角色,方便我们快速查找书中的内容,所以索引是以空间换时间的设计思想。

那换到数据库中,索引的定义就是帮助存储引擎快速获取数据的一种数据结构,形象的说就是索引是数据的目录

所谓的存储引擎,说白了就是如何存储数据、如何为存储的数据建立索引和如何更新、查询数据等技术的实现方法。MySQL 存储引擎有 MyISAM 、InnoDB、Memory,其中 InnoDB 是在 MySQL 5.5 之后成为默认的存储引擎。

下图是 MySQL 的结构图,索引和数据就是位于存储引擎中:

有关MySQL中的索引面试题系列

索引(Index)是数据库优化中最常用也是最重要的手段之一,通过索引通常可以帮助用户解决大多数的SQL性能问题。索引是帮助MySQL高效获取数据的数据结构,它用于快速找出在某个列中含有某一特定值的行。如果不使用索引,那么MySQL必须从第1条记录开始然后读完整个表直到找出相关的行。表越大,花费的时间越多。如果表中查询的列有一个索引,那么MySQL就能快速到达一个位置去搜寻数据文件的中间,而没有必要遍历所有数据。

索引是MySQL数据库中的重要对象之一,索引的目的在于提高查询效率。索引可以类比书籍中的目录,查找书籍内容时可以根据目录查找到所需内容的具体位置,然后直接获取即可。索引是表的目录,在查找内容之前可以先在索引中查找,以此快速定位查询数据。

索引列在MySQL中也叫做“键(key)”,索引是存储引擎用于快速找到记录的一种数据结构。索引的优点显而易见是可以加速查询,但创建索引也是有代价的。首先每建立一个索引都要为它建立一棵B+树,会占用额外的存储空间;其次当对表中的数据进行增加、删除、修改时,索引也需要动态的维护,降低了数据的维护速度。

总体来说,索引有如下几个优点:

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

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

③ 索引可以将随机I/O变为顺序I/O。

索引在MySQL中的结构

索引的本质是空间换时间,通过索引这个数据结构来提高数据查询的效率。在MySQL中,每一个索引在InnoDB里面对应一棵B+树。B+树是为了磁盘及其他存储辅助设备而设计的一种平衡查找树(不是二叉树)。在B+树中,所有的数据都在叶子节点,且每一个叶子节点都带有指向下一个节点的指针,形成了一个有序的链表。一般情况下,数据库的B+树的高度一般在2~4层,这就是说找到某一键值的行记录最多需要2到4次逻辑IO。
MySQL的InnoDB索引数据结构都是B+树,主键索引叶子节点存储的就是MySQL的整个数据行,普通索引的叶子节点存储的是索引列和主键列

索引的分类

你知道索引有哪些吗?大家肯定都能霹雳啪啦地说出聚簇索引、主键索引、二级索引、普通索引、唯一索引、hash索引、B+树索引等等。

然后再问你,你能将这些索引分一下类吗?可能大家就有点模糊了。其实,要对这些索引进行分类,要清楚这些索引的使用和实现方式,然后再针对有相同特点的索引归为一类。

我们可以按照四个角度来分类索引。

  • 按「数据结构」分类:B+tree索引、Hash索引、Full-text索引
  • 按「物理存储」分类:聚簇索引(主键索引)、二级索引(辅助索引)
  • 按「字段特性」分类:主键索引、唯一索引、普通索引、前缀索引
  • 按「字段个数」分类:单列索引、联合索引

接下来,按照这些角度来说说各类索引的特点。

按数据结构分类

从数据结构的角度来看,MySQL 常见索引有 B+Tree 索引、HASH 索引、Full-Text 索引。

每一种存储引擎支持的索引类型不一定相同,我在表中总结了 MySQL 常见的存储引擎 InnoDB、MyISAM 和 Memory 分别支持的索引类型。

有关MySQL中的索引面试题系列

InnoDB 是在 MySQL 5.5 之后成为默认的 MySQL 存储引擎,B+Tree 索引类型也是 MySQL 存储引擎采用最多的索引类型。

在创建表时,InnoDB 存储引擎会根据不同的场景选择不同的列作为索引:

  • 如果有主键,默认会使用主键作为聚簇索引的索引键(key);
  • 如果没有主键,就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键(key);
  • 在上面两个都没有的情况下,InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键(key);

其它索引都属于辅助索引(Secondary Index),也被称为二级索引或非聚簇索引创建的主键索引和二级索引默认使用的是 B+Tree 索引

为了让大家理解 B+Tree 索引的存储和查询的过程,接下来我通过一个简单例子,说明一下 B+Tree 索引在存储数据中的具体实现。

先创建一张商品表,id 为主键,如下:

商品表里,有这些行数据:

有关MySQL中的索引面试题系列

这些行数据,存储在 B+Tree 索引时是长什么样子的?

B+Tree 是一种多叉树,叶子节点才存放数据,非叶子节点只存放索引,而且每个节点里的数据是按主键顺序存放的。每一层父节点的索引值都会出现在下层子节点的索引值中,因此在叶子节点中,包括了所有的索引值信息,并且每一个叶子节点都指向下一个叶子节点,形成一个链表。

主键索引的 B+Tree 如图所示:

有关MySQL中的索引面试题系列

通过主键查询商品数据的过程

比如,我们执行了下面这条查询语句,这条语句使用了主键索引查询 id 号为 5 的商品。查询过程是这样的,B+Tree 会自顶向下逐层进行查找:

  • 将 5 与根节点的索引数据 (1,10,20) 比较,5 在 1 和 10 之间,所以根据 B+Tree的搜索逻辑,找到第二层的索引数据 (1,4,7);
  • 在第二层的索引数据 (1,4,7)中进行查找,因为 5 在 4 和 7 之间,所以找到第三层的索引数据(4,5,6);
  • 在叶子节点的索引数据(4,5,6)中进行查找,然后我们找到了索引值为 5 的行数据。

数据库的索引和数据都是存储在硬盘的,我们可以把读取一个节点当作一次磁盘 I/O 操作。那么上面的整个查询过程一共经历了 3 个节点,也就是进行了 3 次 I/O 操作。

B+Tree 存储千万级的数据只需要 3-4 层高度就可以满足,这意味着从千万级的表查询目标数据最多需要 3-4 次磁盘 I/O,所以B+Tree 相比于 B 树和二叉树来说,最大的优势在于查询效率很高,因为即使在数据量很大的情况,查询一个数据的磁盘 I/O 依然维持在 3-4次。

通过二级索引查询商品数据的过程

主键索引的 B+Tree 和二级索引的 B+Tree 区别如下:

  • 主键索引的 B+Tree 的叶子节点存放的是实际数据,所有完整的用户记录都存放在主键索引的 B+Tree 的叶子节点里;
  • 二级索引的 B+Tree 的叶子节点存放的是主键值,而不是实际数据。

我这里将前面的商品表中的 product_no (商品编码)字段设置为二级索引,那么二级索引的 B+Tree 如下图,其中非叶子的 key 值是 product_no(图中橙色部分),叶子节点存储的数据是主键值(图中绿色部分)。

有关MySQL中的索引面试题系列

如果我用 product_no 二级索引查询商品,如下查询语句:

会先检二级索引中的 B+Tree 的索引值(商品编码,product_no),找到对应的叶子节点,然后获取主键值,然后再通过主键索引中的 B+Tree 树查询到对应的叶子节点,然后获取整行数据。这个过程叫「回表」,也就是说要查两个 B+Tree 才能查到数据。如下图:

回表

不过,当查询的数据是能在二级索引的 B+Tree 的叶子节点里查询到,这时就不用再查主键索引查,比如下面这条查询语句:

这种在二级索引的 B+Tree 就能查询到结果的过程就叫作「覆盖索引」,也就是只需要查一个 B+Tree 就能找到数据

为什么 MySQL InnoDB 选择 B+tree 作为索引的数据结构?

前面已经讲了 B+Tree 的索引原理,现在就来回答一下 B+Tree 相比于 B 树、二叉树或 Hash 索引结构的优势在哪儿?

之前我也专门写过一篇文章,想详细了解的可以看这篇:「女朋友问我:为什么 MySQL 喜欢 B+ 树?我笑着画了 20 张图 (opens new window)」,这里就简单做个比对。

1、B+Tree vs B Tree

B+Tree 只在叶子节点存储数据,而 B 树 的非叶子节点也要存储数据,所以 B+Tree 的单个节点的数据量更小,在相同的磁盘 I/O 次数下,就能查询更多的节点。

另外,B+Tree 叶子节点采用的是双链表连接,适合 MySQL 中常见的基于范围的顺序查找,而 B 树无法做到这一点。

2、B+Tree vs 二叉树

对于有 N 个叶子节点的 B+Tree,其搜索复杂度为O(logdN),其中 d 表示节点允许的最大子节点个数为 d 个。

在实际的应用当中, d 值是大于100的,这样就保证了,即使数据达到千万级别时,B+Tree 的高度依然维持在 3~4 层左右,也就是说一次数据查询操作只需要做 3~4 次的磁盘 I/O 操作就能查询到目标数据。

而二叉树的每个父节点的儿子节点个数只能是 2 个,意味着其搜索复杂度为 O(logN),这已经比 B+Tree 高出不少,因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。

3、B+Tree vs Hash

Hash 在做等值查询的时候效率贼快,搜索复杂度为 O(1)。

但是 Hash 表不适合做范围查询,它更适合做等值的查询,这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因。

按物理存储分类:聚簇索引和非聚簇索引

从物理存储的角度来看,索引分为聚簇索引(主键索引)、二级索引(辅助索引)

这两个区别在前面也提到了:

  • 主键索引的 B+Tree 的叶子节点存放的是实际数据,所有完整的用户记录都存放在主键索引的 B+Tree 的叶子节点里;
  • 二级索引的 B+Tree 的叶子节点存放的是主键列和索引列,而不是实际数据。

所以,在查询时使用了二级索引,如果查询的数据能在二级索引里查询的到,那么就不需要回表,这个过程就是覆盖索引。如果查询的数据不在二级索引里,就会先检索二级索引,找到对应的叶子节点,获取到主键值后,然后再检索主键索引,就能查询到数据了,这个过程就是回表

在InnoDB中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表。根据叶子节点的内容,索引可以分为主键索引和非主键索引。,区别主要看叶子节点存了什么数据。
在InnoDB里,索引B+Tree的叶子节点存储了整行数据的是主键索引,主键索引也被称之为聚簇索引(clustered index)。聚簇索引是对磁盘上实际数据重新组织以按指定的一个或多个列的值排序的算法。特点是存储数据的顺序和索引顺序一致。一般情况下主键会默认创建聚簇索引,且一张表只允许存在一个聚簇索引,因为数据一旦存储,顺序只能有一种。找到了索引就找到了需要的数据,那么这个索引就是聚簇索引,所以主键就是聚簇索引,修改聚簇索引其实就是修改主键。
一张InnoDB表必须有一个聚簇索引,当有主键时,会以主键作为聚簇索引,所以,主键一定是聚簇索引,如果开发人员没有显式定义主键,那么MySQL会默认使用非空的Unique索引来代替,若没有非空的Unique索引,则MySQL自动为InnoDB表生成一个隐含字段作为主键,其它普通索引需要区分SQL场景。当SQL查询的列就是索引本身时,我们称这种场景下该普通索引也可以叫做聚簇索引,MyisAM引擎没有聚簇索引。除聚簇索引外的其他索引都可称为二级索引,例如常用到的唯一索引、普通索引、联合索引等。
在InnoDB里,索引B+Tree的叶子节点只存储了主键的值和索引列的是非主键索引,也被称之为非聚簇索引(non-clustered index)或二级索引(secondary index)或辅助索引。一个表可以有多个非聚簇索引。非聚簇索引的存储和数据的存储是分离的,也就是说可能找到了索引但没找到数据,需要根据索引上的值(主键)再次回表查询。
聚簇索引的叶子节点就是数据节点,存储了整行数据,而非聚簇索引的叶子节点仍然是索引节点,只不过有指向对应数据块的指针。聚簇索引查询相对会更快一些,因为主键索引树的叶子节点直接就是我们要查询的整行数据了,而非主键索引的叶子节点是主键的值,查到主键的值以后,还需要再通过主键的值再进行一次查询(这个过程叫做回表,也就是查了2个索引树)。
下面介绍下索引的创建、删除等操作方法。

例如,下面的SQL创建了一个学生表:

对于如下的SQL语句,直接根据主键查询获取所有字段数据,此时主键是聚簇索引,因为主键对应的索引叶子节点存储了id=1的所有字段的值:

对于如下的SQL语句,根据编号no查询编号和名称,编号本身是一个唯一索引,但查询的列包含了学生编号和学生名称,当命中编号索引时,该索引的节点的数据存储的是主键ID,需要根据主键ID重新查询一次,所以这种查询下no不是聚簇索引:

对于如下的SQL语句,根据编号查询编号,这种查询命中编号索引时,直接返回编号,因为所需要的数据就是该索引,不需要回表查询,这种场景下no是聚簇索引

聚簇索引的叶子节点存的是整行数据,当某条查询使用的是聚簇索引时,只需要扫描聚簇索引一颗B+树即可得到所需记录,如果想通过二级索引来查找完整的记录的话,那么需要通过回表操作,也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的记录。也就是说,基于非主键索引的查询需要多扫描一棵索引树。因此,我们在应用中应该尽量使用主键查询。

按字段特性分类

从字段特性的角度来看,索引分为主键索引、唯一索引、普通索引、前缀索引。

主键索引

主键索引就是建立在主键字段上的索引,通常在创建表的时候一起创建,一张表最多只有一个主键索引,索引列的值不允许有空值。

在创建表时,创建主键索引的方式如下:

唯一索引

唯一索引建立在 UNIQUE 字段上的索引,一张表可以有多个唯一索引,索引列的值必须唯一,但是允许有空值。

在创建表时,创建唯一索引的方式如下:

建表后,如果要创建唯一索引,可以使用这面这条命令:

普通索引

普通索引就是建立在普通字段上的索引,既不要求字段为主键,也不要求字段为 UNIQUE。

在创建表时,创建普通索引的方式如下:

建表后,如果要创建普通索引,可以使用这面这条命令:

唯一索引和普通索引在查询和更新的时候区别:

唯一索引找到满足的第一条记录会立马返回,通知检索(因为唯一性的保证)。但是这个区别并没有很大的性能区别,因为Innodb是按照页(默认16KB)读写的,读数据的时候是从B+树的根节点开始搜索,搜索的时候将整个页从硬盘加载到内存。

唯一索引在插入的时候会多做些判断,想要做这个判断就必须先把数据页读入内存。但是普通索引不需要做这个判断,就可以把需要更新的数据做判断:如果数据在内存则直接更新;如果不在也不加载内存,而是先写入change buffer,等下次查询的时候再执行change buffer。这样普通索引会相对性能好一些。但是注意:如果业务场景是写入后立马有查询,其实还是会立马需要把数据页加载到内存,这样的情况下其实并不能带来优化IO的操作。

前缀索引

前缀索引是指对字符类型字段的前几个字符建立的索引,而不是在整个字段上建立的索引,前缀索引可以建立在字段类型为 char、 varchar、binary、varbinary 的列上。

使用前缀索引的目的是为了减少索引占用的存储空间,提升查询效率。

在创建表时,创建前缀索引的方式如下:

建表后,如果要创建前缀索引,可以使用这面这条命令:

有时候需要索引很长的字符列,这会让索引变得大且慢,此时可以考虑前缀索引。MySQL目前还不支持函数索引,但是支持前缀索引,即对索引字段的前N个字符创建索引,这个特性可以大大缩小索引文件的大小,从而提高索引效率。用户在设计表结构的时候也可以对文本列根据此特性进行灵活设计。前缀索引是一种能使索引更小、更快的有效办法。

前缀索引的缺点是,在排序ORDER BY和分组GROUP BY操作的时候无法使用,也无法使用前缀索引做覆盖扫描,并且前缀索引降低了索引的选择性。索引的选择性是指不重复的索引值(也称为基数,Cardinality)和数据表的记录总数(COUNT(*))的比值,范围为(0,1]。索引的选择性越高则查询效率越高,因为选择性高的索引可以让MySQL在查找时过滤掉更多的行。唯一索引的选择性是1,这是最好的索引选择性,性能也是最好的。

一般情况下某个前缀的选择性也是足够高的,足以满足查询性能。对于BLOB,TEXT,或者很长的VARCHAR类型的列,必须使用前缀索引,因为MySQL不允许索引这些列的完整长度。

使用前缀索引的诀窍在于要选择足够长的前缀以保证较高的选择性,同时又不能太长(以便节约空间)。前缀应该足够长,以使得前缀索引的选择性接近于索引的整个列。换句话说,前缀的“基数”应该接近于完整的列的“基数”。

为了决定前缀的合适长度,需要找到最常见的值的列表,然后和最常见的前缀列表进行比较。下面给出一种方法,计算完整列的选择性,并使其前缀的选择性接近于完整列的选择性:

可以看见当索引前缀为6时的基数是0.4258,已经接近完整列选择性0.4300。在上面的示例中,已经找到了合适的前缀长度,下面创建前缀索引:

可以看见正确使用刚创建的索引。

按字段个数分类

从字段个数的角度来看,索引分为单列索引、联合索引(复合索引)。

  • 建立在单列上的索引称为单列索引,比如主键索引;
  • 建立在多列上的索引称为联合索引;

对于一个表里的多个列,比如是有些列高频查询,有些列低频查询。如果为每一个低频的列单独建立索引感觉有些浪费,如果不建立索引又只能走全表扫描。所以我们经常用联合索引来解决这个问题,联合索引如idx_key1_key2_key3(key1,key2,key3),相当于创建了(key1)、(key1,key2)和(key1,key2,key3)三个索引,那么在建立联合索引的时候,如何安排索引内的字段顺序?

如果通过调整顺序,可以少维护一个索引,那么这个顺序往往就是需要优先考虑采用

按照字段在查询条件中出现的频度建立索引

我们考虑key1 是最常用的列放最前面,key2和key3不常用。

上面这种建立一个联合索引就实际上包含了3个索引的特性就是最左匹配原则。这个最左匹配可以是联合索引的最左 N 个字段,也可以是字符串索引的最左 M 个字符。

总结起来:

  • 索引的匹配规则是左匹配的

  • 只有复合索引的第一个字段出现在查询条件中,该索引才可能被使用

  • 有了(A,B,C),就等于同时拥有了(A),(A,B)和 (A,B,C) 三个索引

  • 只要索引内,开始用范围查询,后面的索引就失效了。这里注意:IN 在 where 中,也属于准确查询,不会使后面索引失效。

联合索引

通过将多个字段组合成一个索引,该索引就被称为联合索引。比如将商品表中的 product_no 和 name 字段组合成联合索引(product_no, name),创建联合索引的方式如下:

联合索引(product_no, name) 的 B+Tree 示意图如下:

联合索引

可以看到,a 是全局有序的(1, 2, 2, 3, 4, 5, 6, 7 ,8),而 b 是全局是无序的(12,7,8,2,3,8,10,5,2)。因此,直接执行where b = 2这种查询条件没有办法利用联合索引的,利用索引的前提是索引里的 key 是有序的

只有在 a 相同的情况才,b 才是有序的,比如 a 等于 2 的时候,b 的值为(7,8),这时就是有序的,这个有序状态是局部的,因此,执行where a = 2 and b = 7是 a 和 b 字段能用到联合索引的,也就是联合索引生效了。

联合索引范围查询

联合索引有一些特殊情况,并不是查询过程使用了联合索引查询,就代表联合索引中的所有字段都用到了联合索引进行索引查询,也就是可能存在部分字段用到联合索引的 B+Tree,部分字段没有用到联合索引的 B+Tree 的情况。

这种特殊情况就发生在范围查询。联合索引的最左匹配原则会一直向右匹配直到遇到「范围查询」就会停止匹配。也就是范围查询的字段可以用到联合索引,但是在范围查询字段的后面的字段无法用到联合索引

范围查询有很多种,那到底是哪些范围查询会导致联合索引的最左匹配原则会停止匹配呢?

接下来,举例几个范围查例子。

Q1: select * from t_table where a > 1 and b = 2,联合索引(a, b)哪一个字段用到了联合索引的 B+Tree?

由于联合索引(二级索引)是先按照 a 字段的值排序的,所以符合 a > 1 条件的二级索引记录肯定是相邻,于是在进行索引扫描的时候,可以定位到符合 a > 1 条件的第一条记录,然后沿着记录所在的链表向后扫描,直到某条记录不符合 a > 1 条件位置。所以 a 字段可以在联合索引的 B+Tree 中进行索引查询。

但是在符合 a > 1 条件的二级索引记录的范围里,b 字段的值是无序的。比如前面图的联合索引的 B+ Tree 里,下面这三条记录的 a 字段的值都符合 a > 1 查询条件,而 b 字段的值是无序的:

  • a 字段值为 5 的记录,该记录的 b 字段值为 8;
  • a 字段值为 6 的记录,该记录的 b 字段值为 10;
  • a 字段值为 7 的记录,该记录的 b 字段值为 5;

因此,我们不能根据查询条件 b = 2 来进一步减少需要扫描的记录数量(b 字段无法利用联合索引进行索引查询的意思)。

所以在执行 Q1 这条查询语句的时候,对应的扫描区间是 (2, + ∞),形成该扫描区间的边界条件是 a > 1,与 b = 2 无关。

因此,Q1 这条查询语句只有 a 字段用到了联合索引进行索引查询,而 b 字段并没有使用到联合索引

我们也可以在执行计划中的 key_len 知道这一点,在使用联合索引进行查询的时候,通过 key_len 我们可以知道优化器具体使用了多少个字段的搜索条件来形成扫描区间的边界条件。

举例个例子 ,a 和 b 都是 int 类型且不为 NULL 的字段,那么 Q1 这条查询语句执行计划如下,可以看到 key_len 为 4 字节(如果字段允许为 NULL,就在字段类型占用的字节数上加 1,也就是 5 字节),说明只有 a 字段用到了联合索引进行索引查询,而且可以看到,即使 b 字段没用到联合索引,key 为 idx_a_b,说明 Q1 查询语句使用了 idx_a_b 联合索引。

img

通过 Q1 查询语句我们可以知道,a 字段使用了 > 进行范围查询,联合索引的最左匹配原则在遇到 a 字段的范围查询( >)后就停止匹配了,因此 b 字段并没有使用到联合索引。

Q2: select * from t_table where a >= 1 and b = 2,联合索引(a, b)哪一个字段用到了联合索引的 B+Tree?

Q2 和 Q1 的查询语句很像,唯一的区别就是 a 字段的查询条件「大于等于」。

由于联合索引(二级索引)是先按照 a 字段的值排序的,所以符合 >= 1 条件的二级索引记录肯定是相邻,于是在进行索引扫描的时候,可以定位到符合 >= 1 条件的第一条记录,然后沿着记录所在的链表向后扫描,直到某条记录不符合 a>= 1 条件位置。所以 a 字段可以在联合索引的 B+Tree 中进行索引查询。

虽然在符合 a>= 1 条件的二级索引记录的范围里,b 字段的值是「无序」的,但是对于符合 a = 1 的二级索引记录的范围里,b 字段的值是「有序」的(因为对于联合索引,是先按照 a 字段的值排序,然后在 a 字段的值相同的情况下,再按照 b 字段的值进行排序)。

于是,在确定需要扫描的二级索引的范围时,当二级索引记录的 a 字段值为 1 时,可以通过 b = 2 条件减少需要扫描的二级索引记录范围(b 字段可以利用联合索引进行索引查询的意思)。也就是说,从符合 a = 1 and b = 2 条件的第一条记录开始扫描,而不需要从第一个 a 字段值为 1 的记录开始扫描。

所以,Q2 这条查询语句 a 和 b 字段都用到了联合索引进行索引查询

我们也可以在执行计划中的 key_len 知道这一点。执行计划如下,可以看到 key_len 为 8 字节,说明优化器使用了 2 个字段的查询条件来形成扫描区间的边界条件,也就是 a 和 b 字段都用到了联合索引进行索引查询。

img

通过 Q2 查询语句我们可以知道,虽然 a 字段使用了 >= 进行范围查询,但是联合索引的最左匹配原则并没有在遇到 a 字段的范围查询( >=)后就停止匹配了,b 字段还是可以用到了联合索引的。

Q3: SELECT * FROM t_table WHERE a BETWEEN 2 AND 8 AND b = 2,联合索引(a, b)哪一个字段用到了联合索引的 B+Tree?

Q3 查询条件中 a BETWEEN 2 AND 8 的意思是查询 a 字段的值在 2 和 8 之间的记录。不同的数据库对 BETWEEN ... AND 处理方式是有差异的。在 MySQL 中,BETWEEN 包含了 value1 和 value2 边界值,类似于 >= and =<。而有的数据库则不包含 value1 和 value2 边界值(类似于 > and <)。

这里我们只讨论 MySQL。由于 MySQL 的 BETWEEN 包含 value1 和 value2 边界值,所以类似于 Q2 查询语句,因此 Q3 这条查询语句 a 和 b 字段都用到了联合索引进行索引查询

我们也可以在执行计划中的 key_len 知道这一点。执行计划如下,可以看到 key_len 为 8 字节,说明优化器使用了 2 个字段的查询条件来形成扫描区间的边界条件,也就是 a 和 b 字段都用到了联合索引进行索引查询。

img

通过 Q3 查询语句我们可以知道,虽然 a 字段使用了 BETWEEN 进行范围查询,但是联合索引的最左匹配原则并没有在遇到 a 字段的范围查询( BETWEEN)后就停止匹配了,b 字段还是可以用到了联合索引的。

Q4: SELECT * FROM t_user WHERE name like 'j%' and age = 22,联合索引(name, age)哪一个字段用到了联合索引的 B+Tree?

由于联合索引(二级索引)是先按照 name 字段的值排序的,所以前缀为 ‘j’ 的 name 字段的二级索引记录都是相邻的, 于是在进行索引扫描的时候,可以定位到符合前缀为 ‘j’ 的 name 字段的第一条记录,然后沿着记录所在的链表向后扫描,直到某条记录的 name 前缀不为 ‘j’ 为止。

所以 a 字段可以在联合索引的 B+Tree 中进行索引查询,形成的扫描区间是['j','k')。注意, j 是闭区间。如下图:

img

虽然在符合前缀为 ‘j’ 的 name 字段的二级索引记录的范围里,age 字段的值是「无序」的,但是对于符合 name = j 的二级索引记录的范围里,age字段的值是「有序」的(因为对于联合索引,是先按照 name 字段的值排序,然后在 name 字段的值相同的情况下,再按照 age 字段的值进行排序)。

于是,在确定需要扫描的二级索引的范围时,当二级索引记录的 name 字段值为 ‘j’ 时,可以通过 age = 22 条件减少需要扫描的二级索引记录范围(age 字段可以利用联合索引进行索引查询的意思)。也就是说,从符合 name = 'j' and age = 22 条件的第一条记录时开始扫描,而不需要从第一个 name 为 j 的记录开始扫描 。如下图的右边:

img

所以,Q4 这条查询语句 a 和 b 字段都用到了联合索引进行索引查询

我们也可以在执行计划中的 key_len 知道这一点。本次例子中:

  • name 字段的类型是 varchar(30) 且不为 NULL,数据库表使用了 utf8mb4 字符集,一个字符集为 utf8mb4 的字符是 4 个字节,因此 name 字段的实际数据最多占用的存储空间长度是 120 字节(30 x 4),然后因为 name 是变长类型的字段,需要再加 2,也就是 name 的 key_len 为 122。
  • age 字段的类型是 int 且不为 NULL,key_len 为 4。

Q4 查询语句的执行计划如下,可以看到 key_len 为 126 字节,name 的 key_len 为 122,age 的 key_len 为 4,说明优化器使用了 2 个字段的查询条件来形成扫描区间的边界条件,也就是 name 和 age 字段都用到了联合索引进行索引查询。

img

通过 Q4 查询语句我们可以知道,虽然 name 字段使用了 like 前缀匹配进行范围查询,但是联合索引的最左匹配原则并没有在遇到 name 字段的范围查询( like 'j%')后就停止匹配了,age 字段还是可以用到了联合索引的。

综上所示,联合索引的最左匹配原则,在遇到范围查询(如 >、<)的时候,就会停止匹配,也就是范围查询的字段可以用到联合索引,但是在范围查询字段的后面的字段无法用到联合索引。注意,对于 >=、<=、BETWEEN、like 前缀匹配的范围查询,并不会停止匹配,前面我也用了四个例子说明了

索引下推

现在我们知道,对于联合索引(a, b),在执行 select * from table where a > 1 and b = 2 语句的时候,只有 a 字段能用到索引,那在联合索引的 B+Tree 找到第一个满足条件的主键值(ID 为 2)后,还需要判断其他条件是否满足(看 b 是否等于 2),那是在联合索引里判断?还是回主键索引去判断呢?

  • 在 MySQL 5.6 之前,只能从 ID2 (主键值)开始一个个回表,到「主键索引」上找出数据行,再对比 b 字段值。
  • 而 MySQL 5.6 引入的索引下推优化(index condition pushdown), 可以在联合索引遍历过程中,对联合索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数

当你的查询语句的执行计划里,出现了 Extra 为 Using index condition,那么说明使用了索引下推的优化。

索引区分度

另外,建立联合索引时的字段顺序,对索引效率也有很大影响。越靠前的字段被用于索引过滤的概率越高,实际开发工作中建立联合索引时,要把区分度大的字段排在前面,这样区分度大的字段越有可能被更多的 SQL 使用到

区分度就是某个字段 column 不同值的个数「除以」表的总行数,计算公式如下:

区分度计算公式

比如,性别的区分度就很小,不适合建立索引或不适合排在联合索引列的靠前的位置,而 UUID 这类字段就比较适合做索引或排在联合索引列的靠前的位置。

因为如果索引的区分度很小,假设字段的值分布均匀,那么无论搜索哪个值都可能得到一半的数据。在这些情况下,还不如不要索引,因为 MySQL 还有一个查询优化器,查询优化器发现某个值出现在表的数据行中的百分比(惯用的百分比界线是"30%")很高的时候,它一般会忽略索引,进行全表扫描。

联合索引实践

这里出一个题目,针对针对下面这条 SQL,你怎么通过索引来提高查询效率呢?

有的同学会认为,单独给 status 建立一个索引就可以了。

但是更好的方式给 status 和 create_time 列建立一个联合索引,因为这样可以避免 MySQL 数据库发生文件排序。

因为在查询时,如果只用到 status 的索引,但是这条语句还要对 create_time 排序,这时就要用文件排序 filesort,也就是在 SQL 执行计划中,Extra 列会出现 Using filesort。

所以,要利用索引的有序性,在 status 和 create_time 列建立联合索引,这样根据 status 筛选后的数据就是按照 create_time 排好序的,避免在文件排序,提高了查询效率。

MySQL中的索引可以按一定顺序引用多列,这种索引叫作联合索引。例如,User表的name和city加联合索引就是(name,city),而最左前缀原则指的是,如果查询的时候查询条件精确匹配索引的左边连续一列或几列,那么此列就可以被用到。例如:

需要注意的是,如果在查询的时候所有的索引列都用上了,但是顺序不同,例如,city= xx and name =xx,那么在查询时,存储引擎会自动优化为匹配联合索引的顺序,这样是能够命中索引的。

由于最左前缀原则,所以,在创建联合索引时,索引字段的顺序需要考虑字段值去重之后的个数,即列的唯一值较多的应该放在最前边。ORDER BY子句也遵循此规则。

需要注意避免冗余索引。如果创建了索引(A,B),再创建索引(A),那么就是冗余索引,因为这只是前一个索引的前缀索引。在大多数情况下都不需要使用冗余索引,应该尽可能拓展已有的索引而不是创建新的索引。但有时候出于性能的考虑,例如,拓展已有的索引会使得其变得太大,从而影响其他使用该索引的查询的性能。在MySQL 5.7版本后,可以通过查询sys库的schema_redundant_indexes表来查看冗余索引。

其它索引

什么是哈希索引?

哈希索引(Hash Index)建立在哈希表的基础上,它只对使用了索引中的每一列的精确查找有用。对于每一行,存储引擎计算出了被索引的哈希码(Hash Code),它是一个较小的值,并且有可能和其它行的哈希码不同。它把哈希码保存在索引中,并且保存了一个指向哈希表中的每一行的指针。如果多个值有相同的哈希码,那么索引就会把行指针以链表的方式保存在哈希表的同一条记录中。

哈希索引只有MEMORY和NDB两种引擎支持,MEMORY引擎默认支持哈希索引,如果多个HASH值相同,出现哈希碰撞,那么索引以链表方式存储。若要使InnoDB或MyISAM支持哈希索引,那么可以通过伪哈希索引来实现。主要通过增加一个字段,存储HASH值,将HASH值建立索引,在插入和更新的时候,建立触发器,自动添加计算后的HASH值到表里。在查询的时候,在WHERE子句手动指定使用哈希函数。这样做的缺陷是需要维护哈希值。

MySQL最常用存储引擎InnoDB和MyISAM都不支持HASH索引,它们默认的索引都是BTree。但是,如果在创建索引的时候定义其索引类型为HASH,那么MySQL并不会报错,而且通过SHOW CREATE TABLE查看该索引也是HASH,只不过该索引实际上还是BTree,如下所示:

HASH索引检索效率非常高,索引的检索可以一次定位,不像BTREE索引需要从根节点到枝节点,最后才能访问到叶节点这样多次的I/O访问,所以HASH索引的查询效率要远高于BTREE索引。那么,既然HASH索引的效率要比BTREE高很多,为什么大家不都用HASH索引而还要使用BTREE索引呢?其实,任何事物都是有两面性的,HASH索引也一样,虽然HASH索引效率高,但是HASH索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些:

① HASH索引仅仅能满足“=”、“IN”和“<=>”查询,不能使用范围查询。由于HASH索引比较的是进行HASH运算之后的HASH值,所以它只能用于等值的过滤,不能用于基于范围的过滤,因为经过相应的HASH算法处理之后的HASH值的大小关系,并不能保证和HASH运算前完全一样。

② 优化器不能使用HASH索引来加速ORDER BY操作,即HASH索引无法被用来避免数据的排序操作。由于HASH索引中存放的是经过HASH计算之后的HASH值,而且HASH值的大小关系并不一定和HASH运算前的键值完全一样,所以数据库无法利用索引的数据来避免任何排序运算。

③ MySQL不能确定在两个值之间大约有多少行。如果将一个MyISAM表改为HASH索引的MEMORY表,会影响一些查询的执行效率。

④ 只能使用整个关键字来搜索一行,即HASH索引不能利用部分索引键查询。对于组合索引,HASH索引在计算HASH值的时候是组合索引键合并后再一起计算HASH值,而不是单独计算HASH值,所以通过组合索引的前面一个或几个索引键进行查询的时候,HASH索引也无法被利用。

⑤ HASH索引在任何时候都不能避免表扫描。HASH索引是将索引键通过HASH运算之后,将HASH运算结果的HASH值和所对应的行指针信息存放于一个HASH表中,由于不同索引键存在相同HASH值,所以即使取满足某个HASH键值的数据的记录条数,也无法从HASH索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。

⑥ HASH索引遇到大量HASH值相等的情况后性能并不一定就会比BTREE索引高。对于选择性比较低的索引键,如果创建HASH索引,那么将会存在大量记录指针信息存于同一个HASH值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。

什么是自适应哈希索引(Adaptive Hash Index)?

InnoDB引擎有一个特殊的功能叫做自适应哈希索引(Adaptive Hash Index)。当InnoDB注意到某些索引值被使用的非常频繁时,它会在内存中基于BTree索引之上再创建一个哈希索引,这样就让BTree索引也具有哈希索引的一些优点,例如:快速的哈希查找,这是一个全自动的,内部的行为,用户无法控制或者配置,不过如果有必要,可以选择关闭这个功能(innodb_adaptive_hash_index=OFF,默认为ON)。

通过“SHOW ENGINE INNODB STATUS;”可以看到当前自适应哈希索引的使用情况:

可以看到自适应哈希索引的使用信息,包括自适应哈希索引的大小、使用情况,每秒使用自适应哈希索引搜索的情况。

索引下推

参考:https://www.xmmup.com/mysqlzhongdesuoyinxiatui.html

什么时候需要 / 不需要创建索引?

索引最大的好处是提高查询速度,但是索引也是有缺点的,比如:

  • 需要占用物理空间,数量越大,占用空间越大;
  • 创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增大;
  • 会降低表的增删改的效率,因为每次增删改索引,B+ 树为了维护索引有序性,都需要进行动态维护

所以,索引不是万能钥匙,它也是根据场景来使用的。

什么时候适用索引?

  • 字段有唯一性限制的,比如商品编码;
  • 经常用于 WHERE 查询条件的字段,这样能够提高整个表的查询速度,如果查询条件不是一个字段,可以建立联合索引。
  • 经常用于 GROUP BYORDER BY 的字段,这样在查询的时候就不需要再去做一次排序了,因为我们都已经知道了建立索引之后在 B+Tree 中的记录都是排序好的。

什么时候不需要创建索引?

  • WHERE 条件,GROUP BYORDER BY 里用不到的字段,索引的价值是快速定位,如果起不到定位的字段通常是不需要创建索引的,因为索引是会占用物理空间的。
  • 字段中存在大量重复数据,不需要创建索引,比如性别字段,只有男女,如果数据库表中,男女的记录分布均匀,那么无论搜索哪个值都可能得到一半的数据。在这些情况下,还不如不要索引,因为 MySQL 还有一个查询优化器,查询优化器发现某个值出现在表的数据行中的百分比很高的时候,它一般会忽略索引,进行全表扫描。
  • 表数据太少的时候,不需要创建索引;
  • 经常更新的字段不用创建索引,比如不要对电商项目的用户余额建立索引,因为索引字段频繁修改,由于要维护 B+Tree的有序性,那么就需要频繁的重建索引,这个过程是会影响数据库性能的。

MySQL中索引的使用原则

索引的设计可以遵循一些已有的原则,创建索引的时候请尽量考虑符合这些原则,便于提高索引的使用效率,更高效地使用索引。
① 最适合索引的列是出现在WHERE子句中的列,或连接子句中指定的列,而不是出现在SELECT关键字后的选择列表中的列。
② 使用唯一索引。考虑某列中值的分布。索引的列的基数越大,索引的效果越好。唯一性索引的值是唯一的,可以更快速的通过该索引来确定某条记录。例如,学生表中学号是具有唯一性的字段。为该字段建立唯一性索引可以很快的确定某个学生的信息。如果使用姓名的话,可能存在同名现象,从而降低查询速度。
③ 使用短索引。如果对字符串列进行索引,那么应该尽量指定一个前缀长度。例如,有一个CHAR(200)列,如果在前10个字符内,大多数值是唯一的,那么就不要对整个列使用索引。对前10个字符进行索引能够节省大量索引空间,也会使查询更快,因为较小的索引涉及的磁盘I/O更少。更为重要的是,对于较短的键值,索引高速缓存中的块能容纳更多的键值,因此,MySQL也可以在内存中容纳更多的值。
④ 利用最左前缀。在创建一个n列的索引时,实际是创建了MySQL可利用的n个索引。多列索引可起几个索引的作用,因为可利用索引中最左边的列集来匹配行。这样的列集称为最左前缀(Leftmost Prefixing)。
⑤ 不要过度索引。不要以为索引“越多越好”,什么东西都用索引是错误的。每个额外的索引都要占用额外的磁盘空间,并降低写操作的性能。在修改表的内容时,索引必须进行更新,有时可能需要重构,因此,索引越多,所花的时间越长。如果有一个索引很少利用或从不使用,那么会不必要地减缓表的修改速度。此外,MySQL在生成一个执行计划时,要考虑各个索引,这也要花费时间。创建多余的索引给查询优化带来了更多的工作。索引太多,也可能会使MySQL选择不到所要使用的最好索引。只保持所需的索引有利于查询优化。
⑥ 对于InnoDB存储引擎的表,记录默认会按照一定的顺序保存,如果有明确定义的主键,那么按照主键顺序保存。如果没有主键,但是有唯一索引,那么就是按照唯一索引的顺序保存。如果既没有主键又没有唯一索引,那么表中会自动生成一个内部列,按照这个列的顺序保存。按照主键或者内部列进行的访问是最快的,所以InnoDB表尽量自己指定主键,当表中同时有几个列都是唯一的,都可以作为主键的时候,要选择最常作为访问条件的列作为主键,提高查询的效率。另外,还需要注意,InnoDB表的普通索引都会保存主键的键值,所以主键要尽可能选择较短的数据类型,可以有效地减少索引的磁盘占用,提高索引的缓存效果。
⑦ 为经常需要排序、分组和联合操作的字段建立索引。经常需要ORDER BY、GROUP BY、DISTINCT和UNION等操作的字段,排序操作会浪费很多时间。如果为其建立索引,可以有效地避免排序操作。
⑧ 限制索引的数目。索引的数目不是越多越好。每个索引都需要占用磁盘空间,索引越多,需要的磁盘空间就越大。修改表时,对索引的重构和更新很麻烦。越多的索引,会使更新表变得很浪费时间。
⑨ 尽量使用数据量少的索引。如果索引的值很长,那么查询的速度会受到影响。例如,对一个CHAR(100)类型的字段进行全文检索需要的时间肯定要比对CHAR(10)类型的字段需要的时间要多。
⑩ 尽量使用前缀来索。引如果索引字段的值很长,最好使用值的前缀来索引。例如,TEXT和BLOG类型的字段,进行全文检索会很浪费时间。如果只检索字段的前面的若干个字符,这样可以提高检索速度。
⑪ 删除不再使用或者很少使用的索引。表中的数据被大量更新,或者数据的使用方式被改变后,原有的一些索引可能不再需要。数据库管理员应当定期找出这些索引,将它们删除,从而减少索引对更新操作的影响。
注意:选择索引的最终目的是为了使查询的速度变快。上面给出的原则是最基本的准则,但不能拘泥于上面的准则。读者要在以后的学习和工作中进行不断的实践。根据应用的实际情况进行分析和判断,选择最合适的索引方式。

有什么优化索引的方法?

这里说一下几种常见优化索引的方法:

  • 前缀索引优化;
  • 覆盖索引优化;
  • 主键索引最好是自增的;
  • 防止索引失效;

前缀索引优化

前缀索引顾名思义就是使用某个字段中字符串的前几个字符建立索引,那我们为什么需要使用前缀来建立索引呢?

使用前缀索引是为了减小索引字段大小,可以增加一个索引页中存储的索引值,有效提高索引的查询速度。在一些大字符串的字段作为索引时,使用前缀索引可以帮助我们减小索引项的大小。

不过,前缀索引有一定的局限性,例如:

  • order by 就无法使用前缀索引;
  • 无法把前缀索引用作覆盖索引;

覆盖索引优化

覆盖索引是指 SQL 中 query 的所有字段,在索引 B+Tree 的叶子节点上都能找得到的那些索引,从二级索引中查询得到记录,而不需要通过聚簇索引查询获得,可以避免回表的操作。

假设我们只需要查询商品的名称、价格,有什么方式可以避免回表呢?

我们可以建立一个联合索引,即「商品ID、名称、价格」作为一个联合索引。如果索引中存在这些数据,查询将不会再次检索主键索引,从而避免回表。

所以,使用覆盖索引的好处就是,不需要查询出包含整行记录的所有信息,也就减少了大量的 I/O 操作。

如果一个索引包含(或者说覆盖了)所有满足查询所需要的数据,那么就称这类索引为覆盖索引(Covering Index)。索引覆盖查询不需要回表操作。当一条查询语句符合覆盖索引条件时,MySQL只需要通过索引就可以返回查询所需要的数据,这样避免了查到索引后再返回表操作,减少I/O提高效率。

在MySQL中,可以通过使用explain命令输出的Extra列来判断是否使用了索引覆盖查询。若使用了索引覆盖查询,则Extra列包含“Using index”字符串。MySQL查询优化器在执行查询前会判断是否有一个索引能执行覆盖查询。

覆盖索引能有效地提高查询性能,因为覆盖索引只需要读取索引而不用回表再读取数据。覆盖索引有以下一些优点:

1、索引项通常比记录要小,所以MySQL会访问更少的数据。

2、索引都按值的大小顺序存储,相对于随机访问记录,需要更少的I/O。

3、大多数据引擎能更好的缓存索引,比如MyISAM只缓存索引。

4、覆盖索引对于InnoDB表尤其有用,因为InnoDB使用聚集索引组织数据,如果二级索引中包含查询所需的数据,那么就不再需要在聚集索引中查找了。

下面的SQL语句就使用到了覆盖索引:

主键索引最好是自增的

我们在建表的时候,都会默认将主键索引设置为自增的,具体为什么要这样做呢?又什么好处?

InnoDB 创建主键索引默认为聚簇索引,数据被存放在了 B+Tree 的叶子节点上。也就是说,同一个叶子节点内的各个数据是按主键顺序存放的,因此,每当有一条新的数据插入时,数据库会根据主键将其插入到对应的叶子节点中。

如果我们使用自增主键,那么每次插入的新数据就会按顺序添加到当前索引节点的位置,不需要移动已有的数据,当页面写满,就会自动开辟一个新页面。因为每次插入一条新记录,都是追加操作,不需要重新移动数据,因此这种插入数据的方法效率非常高。

如果我们使用非自增主键,由于每次插入主键的索引值都是随机的,因此每次插入新的数据时,就可能会插入到现有数据页中间的某个位置,这将不得不移动其它数据来满足新数据的插入,甚至需要从一个页面复制数据到另外一个页面,我们通常将这种情况称为页分裂页分裂还有可能会造成大量的内存碎片,导致索引结构不紧凑,从而影响查询效率

举个例子,假设某个数据页中的数据是1、3、5、9,且数据页满了,现在准备插入一个数据7,则需要把数据页分割为两个数据页:

img

出现页分裂时,需要将一个页的记录移动到另外一个页,性能会受到影响,同时页空间的利用率下降,造成存储空间的浪费。

而如果记录是顺序插入的,例如插入数据11,则只需开辟新的数据页,也就不会发生页分裂:

img

因此,在使用 InnoDB 存储引擎时,如果没有特别的业务需求,建议使用自增字段作为主键。

另外,主键字段的长度不要太大,因为主键字段长度越小,意味着二级索引的叶子节点越小(二级索引的叶子节点存放的数据是主键值),这样二级索引占用的空间也就越小

索引最好设置为 NOT NULL

为了更好的利用索引,索引列要设置为 NOT NULL 约束。有两个原因:

  • 第一原因:索引列存在 NULL 就会导致优化器在做索引选择的时候更加复杂,更加难以优化,因为可为 NULL 的列会使索引、索引统计和值比较都更复杂,比如进行索引统计时,count 会省略值为NULL 的行。

  • 第二个原因:NULL 值是一个没意义的值,但是它会占用物理空间,所以会带来的存储空间的问题,会导致更多的存储空间占用,因为 InnoDB 默认行存储格式COMPACT,会用 1 字节空间存储 NULL 值列表,如下图的黄色部分:

    有关MySQL中的索引面试题系列

防止索引失效

用上了索引并不意味着查询的时候会使用到索引,所以我们心里要清楚有哪些情况会导致索引失效,从而避免写出索引失效的查询语句,否则这样的查询效率是很低的。

我之前写过索引失效的文章,想详细了解的可以去看这篇文章:谁还没碰过索引失效呢?(opens new window)

这里简单说一下,发生索引失效的情况:

  • 当我们使用左或者左右模糊匹配的时候,也就是 like %xx 或者 like %xx%这两种方式都会造成索引失效;
  • 当我们在查询条件中对索引列做了计算、函数、类型转换操作,这些情况下都会造成索引失效;
  • 联合索引要能正确使用需要遵循最左匹配原则,也就是按照最左优先的方式进行索引的匹配,否则就会导致索引失效。
  • 在 WHERE 子句中,如果在 OR 前的条件列是索引列,而在 OR 后的条件列不是索引列,那么索引会失效。

我上面说的是常见的索引失效场景,实际过程中,可能会出现其他的索引失效场景,这时我们就需要查看执行计划,通过执行计划显示的数据判断查询语句是否使用了索引。

如下图,就是一个没有使用索引,并且是一个全表扫描的查询语句。

有关MySQL中的索引面试题系列

对于执行计划,参数有:

  • possible_keys 字段表示可能用到的索引;
  • key 字段表示实际用的索引,如果这一项为 NULL,说明没有使用索引;
  • key_len 表示索引的长度;
  • rows 表示扫描的数据行数。
  • type 表示数据扫描类型,我们需要重点看这个。

type 字段就是描述了找到所需数据时使用的扫描方式是什么,常见扫描类型的执行效率从低到高的顺序为

  • All(全表扫描);
  • index(全索引扫描);
  • range(索引范围扫描);
  • ref(非唯一索引扫描);
  • eq_ref(唯一索引扫描);
  • const(结果只有一条的主键或唯一索引扫描)。

在这些情况里,all 是最坏的情况,因为采用了全表扫描的方式。index 和 all 差不多,只不过 index 对索引表进行全扫描,这样做的好处是不再需要对数据进行排序,但是开销依然很大。所以,要尽量避免全表扫描和全索引扫描。

range 表示采用了索引范围扫描,一般在 where 子句中使用 < 、>、in、between 等关键词,只检索给定范围的行,属于范围查找。从这一级别开始,索引的作用会越来越明显,因此我们需要尽量让 SQL 查询可以使用到 range 这一级别及以上的 type 访问方式

ref 类型表示采用了非唯一索引,或者是唯一索引的非唯一性前缀,返回数据返回可能是多条。因为虽然使用了索引,但该索引列的值并不唯一,有重复。这样即使使用索引快速查找到了第一条数据,仍然不能停止,要进行目标值附近的小范围扫描。但它的好处是它并不需要扫全表,因为索引是有序的,即便有重复值,也是在一个非常小的范围内扫描。

eq_ref 类型是使用主键或唯一索引时产生的访问方式,通常使用在多表联查中。比如,对两张表进行联查,关联条件是两张表的 user_id 相等,且 user_id 是唯一索引,那么使用 EXPLAIN 进行执行计划查看的时候,type 就会显示 eq_ref。

const 类型表示使用了主键或者唯一索引与常量值进行比较,比如 select name from product where id=1。

需要说明的是 const 类型和 eq_ref 都使用了主键或唯一索引,不过这两个类型有所区别,const 是与常量进行比较,查询效率会更快,而 eq_ref 通常用于多表联查中

除了关注 type,我们也要关注 extra 显示的结果。

这里说几个重要的参考指标:

  • Using filesort :当查询语句中包含 group by 操作,而且无法利用索引完成排序操作的时候, 这时不得不选择相应的排序算法进行,甚至可能会通过文件排序,效率是很低的,所以要避免这种问题的出现。
  • Using temporary:使了用临时表保存中间结果,MySQL 在对查询结果排序时使用临时表,常见于排序 order by 和分组查询 group by。效率低,要避免这种问题的出现。
  • Using index:所需数据只需在索引即可全部获得,不须要再到表中取数据,也就是使用了覆盖索引,避免了回表操作,效率不错。

总结

这次主要介绍了索引的原理、分类和使用。我把重点总结在了下面这个表格

有关MySQL中的索引面试题系列

从数据页的角度看 B+ 树

大家背八股文的时候,都知道 MySQL 里 InnoDB 存储引擎是采用 B+ 树来组织数据的。

这点没错,但是大家知道 B+ 树里的节点里存放的是什么呢?查询数据的过程又是怎样的?

这次,我们从数据页的角度看 B+ 树,看看每个节点长啥样。

有关MySQL中的索引面试题系列

InnoDB 是如何存储数据的?

MySQL 支持多种存储引擎,不同的存储引擎,存储数据的方式也是不同的,我们最常使用的是 InnoDB 存储引擎,所以就跟大家图解下InnoDB 是如何存储数据的。

记录是按照行来存储的,但是数据库的读取并不以「行」为单位,否则一次读取(也就是一次 I/O 操作)只能处理一行数据,效率会非常低。

因此,InnoDB 的数据是按「数据页」为单位来读写的,也就是说,当需要读一条记录的时候,并不是将这个记录本身从磁盘读出来,而是以页为单位,将其整体读入内存。

数据库的 I/O 操作的最小单位是页,InnoDB 数据页的默认大小是 16KB,意味着数据库每次读写都是以 16KB 为单位的,一次最少从磁盘中读取 16K 的内容到内存中,一次最少把内存中的 16K 内容刷新到磁盘中。

数据页包括七个部分,结构如下图:

图片

这 7 个部分的作用如下图:

图片

在 File Header 中有两个指针,分别指向上一个数据页和下一个数据页,连接起来的页相当于一个双向的链表,如下图所示:

图片

采用链表的结构是让数据页之间不需要是物理上的连续的,而是逻辑上的连续。

数据页的主要作用是存储记录,也就是数据库的数据,所以重点说一下数据页中的 User Records 是怎么组织数据的。

数据页中的记录按照「主键」顺序组成单向链表,单向链表的特点就是插入、删除非常方便,但是检索效率不高,最差的情况下需要遍历链表上的所有节点才能完成检索。

因此,数据页中有一个页目录,起到记录的索引作用,就像我们书那样,针对书中内容的每个章节设立了一个目录,想看某个章节的时候,可以查看目录,快速找到对应的章节的页数,而数据页中的页目录就是为了能快速找到记录。

那 InnoDB 是如何给记录创建页目录的呢?页目录与记录的关系如下图:

图片

页目录创建的过程如下:

  1. 将所有的记录划分成几个组,这些记录包括最小记录和最大记录,但不包括标记为“已删除”的记录;
  2. 每个记录组的最后一条记录就是组内最大的那条记录,并且最后一条记录的头信息中会存储该组一共有多少条记录,作为 n_owned 字段(上图中粉红色字段)
  3. 页目录用来存储每组最后一条记录的地址偏移量,这些地址偏移量会按照先后顺序存储起来,每组的地址偏移量也被称之为槽(slot),每个槽相当于指针指向了不同组的最后一个记录

从图可以看到,页目录就是由多个槽组成的,槽相当于分组记录的索引。然后,因为记录是按照「主键值」从小到大排序的,所以我们通过槽查找记录时,可以使用二分法快速定位要查询的记录在哪个槽(哪个记录分组),定位到槽后,再遍历槽内的所有记录,找到对应的记录,无需从最小记录开始遍历整个页中的记录链表。

以上面那张图举个例子,5 个槽的编号分别为 0,1,2,3,4,我想查找主键为 11 的用户记录:

  • 先二分得出槽中间位是 (0+4)/2=2 ,2号槽里最大的记录为 8。因为 11 > 8,所以需要从 2 号槽后继续搜索记录;
  • 再使用二分搜索出 2 号和 4 槽的中间位是 (2+4)/2= 3,3 号槽里最大的记录为 12。因为 11 < 12,所以主键为 11 的记录在 3 号槽里;
  • 这里有个问题,「槽对应的值都是这个组的主键最大的记录,如何找到组里最小的记录」?比如槽 3 对应最大主键是 12 的记录,那如何找到最小记录 9。解决办法是:通过槽 3 找到 槽 2 对应的记录,也就是主键为 8 的记录。主键为 8 的记录的下一条记录就是槽 3 当中主键最小的 9 记录,然后开始向下搜索 2 次,定位到主键为 11 的记录,取出该条记录的信息即为我们想要查找的内容。

看到第三步的时候,可能有的同学会疑问,如果某个槽内的记录很多,然后因为记录都是单向链表串起来的,那这样在槽内查找某个记录的时间复杂度不就是 O(n) 了吗?

这点不用担心,InnoDB 对每个分组中的记录条数都是有规定的,槽内的记录就只有几条:

  • 第一个分组中的记录只能有 1 条记录;
  • 最后一个分组中的记录条数范围只能在 1-8 条之间;
  • 剩下的分组中记录条数范围只能在 4-8 条之间。

B+ 树是如何进行查询的?

上面我们都是在说一个数据页中的记录检索,因为一个数据页中的记录是有限的,且主键值是有序的,所以通过对所有记录进行分组,然后将组号(槽号)存储到页目录,使其起到索引作用,通过二分查找的方法快速检索到记录在哪个分组,来降低检索的时间复杂度。

但是,当我们需要存储大量的记录时,就需要多个数据页,这时我们就需要考虑如何建立合适的索引,才能方便定位记录所在的页。

为了解决这个问题,InnoDB 采用了 B+ 树作为索引。磁盘的 I/O 操作次数对索引的使用效率至关重要,因此在构造索引的时候,我们更倾向于采用“矮胖”的 B+ 树数据结构,这样所需要进行的磁盘 I/O 次数更少,而且 B+ 树 更适合进行关键字的范围查询。

InnoDB 里的 B+ 树中的每个节点都是一个数据页,结构示意图如下:

图片

通过上图,我们看出 B+ 树的特点:

  • 只有叶子节点(最底层的节点)才存放了数据,非叶子节点(其他上层节)仅用来存放目录项作为索引。
  • 非叶子节点分为不同层次,通过分层来降低每一层的搜索量;
  • 所有节点按照索引键大小排序,构成一个双向链表,便于范围查询;

我们再看看 B+ 树如何实现快速查找主键为 6 的记录,以上图为例子:

  • 从根节点开始,通过二分法快速定位到符合页内范围包含查询值的页,因为查询的主键值为 6,在[1, 7)范围之间,所以到页 30 中查找更详细的目录项;
  • 在非叶子节点(页30)中,继续通过二分法快速定位到符合页内范围包含查询值的页,主键值大于 5,所以就到叶子节点(页16)查找记录;
  • 接着,在叶子节点(页16)中,通过槽查找记录时,使用二分法快速定位要查询的记录在哪个槽(哪个记录分组),定位到槽后,再遍历槽内的所有记录,找到主键为 6 的记录。

可以看到,在定位记录所在哪一个页时,也是通过二分法快速定位到包含该记录的页。定位到该页后,又会在该页内进行二分法快速定位记录所在的分组(槽号),最后在分组内进行遍历查找。

聚簇索引和二级索引

另外,索引又可以分成聚簇索引和非聚簇索引(二级索引),它们区别就在于叶子节点存放的是什么数据:

  • 聚簇索引的叶子节点存放的是实际数据,所有完整的用户记录都存放在聚簇索引的叶子节点;
  • 二级索引的叶子节点存放的是主键值,而不是实际数据。

因为表的数据都是存放在聚簇索引的叶子节点里,所以 InnoDB 存储引擎一定会为表创建一个聚簇索引,且由于数据在物理上只会保存一份,所以聚簇索引只能有一个。

InnoDB 在创建聚簇索引时,会根据不同的场景选择不同的列作为索引:

  • 如果有主键,默认会使用主键作为聚簇索引的索引键;
  • 如果没有主键,就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键;
  • 在上面两个都没有的情况下,InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键;

一张表只能有一个聚簇索引,那为了实现非主键字段的快速搜索,就引出了二级索引(非聚簇索引/辅助索引),它也是利用了 B+ 树的数据结构,但是二级索引的叶子节点存放的是主键值,不是实际数据。

二级索引的 B+ 树如下图,数据部分为主键值:

图片

因此,如果某个查询语句使用了二级索引,但是查询的数据不是主键值,这时在二级索引找到主键值后,需要去聚簇索引中获得数据行,这个过程就叫作「回表」,也就是说要查两个 B+ 树才能查到数据。不过,当查询的数据是主键值时,因为只在二级索引就能查询到,不用再去聚簇索引查,这个过程就叫作「索引覆盖」,也就是只需要查一个 B+ 树就能找到数据。

总结

InnoDB 的数据是按「数据页」为单位来读写的,默认数据页大小为 16 KB(Oracle和PG默认为8KB)。每个数据页之间通过双向链表的形式组织起来,物理上不连续,但是逻辑上连续。

数据页内包含用户记录,每个记录之间用单向链表的方式组织起来,为了加快在数据页内高效查询记录,设计了一个页目录,页目录存储各个槽(分组),且主键值是有序的,于是可以通过二分查找法的方式进行检索从而提高效率。

为了高效查询记录所在的数据页,InnoDB 采用 b+ 树作为索引,每个节点都是一个数据页。

如果叶子节点存储的是实际数据的就是聚簇索引,一个表只能有一个聚簇索引;如果叶子节点存储的不是实际数据,而是主键值则就是二级索引,一个表中可以有多个二级索引。

在使用二级索引进行查找数据时,如果查询的数据能在二级索引找到,那么就是「索引覆盖」操作,如果查询的数据不在二级索引里,就需要先在二级索引找到主键值,需要去聚簇索引中获得数据行,这个过程就叫作「回表」。

为什么 MySQL 采用 B+ 树作为索引?

「为什么 MySQL 采用 B+ 树作为索引?」这句话,是不是在面试时经常出现。

要解释这个问题,其实不单单要从数据结构的角度出发,还要考虑磁盘 I/O 操作次数,因为 MySQL 的数据是存储在磁盘中的嘛。

这次,就跟大家一层一层的分析这个问题,图中包含大量的动图来帮助大家理解,相信看完你就拿捏这道题目了!

图片

怎样的索引的数据结构是好的?

MySQL 的数据是持久化的,意味着数据(索引+记录)是保存到磁盘上的,因为这样即使设备断电了,数据也不会丢失。

磁盘是一个慢的离谱的存储设备,有多离谱呢?

人家内存的访问速度是纳秒级别的,而磁盘访问的速度是毫秒级别的,也就是说读取同样大小的数据,磁盘中读取的速度比从内存中读取的速度要慢上万倍,甚至几十万倍。

磁盘读写的最小单位是扇区,扇区的大小只有 512B 大小,操作系统一次会读写多个扇区,所以操作系统的最小读写单位是块(Block)。Linux 中的块大小为 4KB,也就是一次磁盘 I/O 操作会直接读写 8 个扇区。

由于数据库的索引是保存到磁盘上的,因此当我们通过索引查找某行数据的时候,就需要先从磁盘读取索引到内存,再通过索引从磁盘中找到某行数据,然后读入到内存,也就是说查询过程中会发生多次磁盘 I/O,而磁盘 I/O 次数越多,所消耗的时间也就越大。

所以,我们希望索引的数据结构能在尽可能少的磁盘的 I/O 操作中完成查询工作,因为磁盘 I/O 操作越少,所消耗的时间也就越小。

另外,MySQL 是支持范围查找的,所以索引的数据结构不仅要能高效地查询某一个记录,而且也要能高效地执行范围查找。

所以,要设计一个适合 MySQL 索引的数据结构,至少满足以下要求:

  • 能在尽可能少的磁盘的 I/O 操作中完成查询工作;
  • 要能高效地查询某一个记录,也要能高效地执行范围查找;

分析完要求后,我们针对每一个数据结构分析一下。

什么是二分查找?

索引数据最好能按顺序排列,这样可以使用「二分查找法」高效定位数据。

假设我们现在用数组来存储索引,比如下面有一个排序的数组,如果要从中找出数字 3,最简单办法就是从头依次遍历查询,这种方法的时间复杂度是 O(n),查询效率并不高。因为该数组是有序的,所以我们可以采用二分查找法,比如下面这张采用二分法的查询过程图:

有关MySQL中的索引面试题系列

可以看到,二分查找法每次都把查询的范围减半,这样时间复杂度就降到了 O(logn),但是每次查找都需要不断计算中间位置。

什么是二分查找树?

用数组来实现线性排序的数据虽然简单好用,但是插入新元素的时候性能太低。

因为插入一个元素,需要将这个元素之后的所有元素后移一位,如果这个操作发生在磁盘中呢?这必然是灾难性的。因为磁盘的速度比内存慢几十万倍,所以我们不能用一种线性结构将磁盘排序。

其次,有序的数组在使用二分查找的时候,每次查找都要不断计算中间的位置。

那我们能不能设计一个非线形且天然适合二分查找的数据结构呢?

有的,请看下图这个神奇的操作,找到所有二分查找中用到的所有中间节点,把他们用指针连起来,并将最中间的节点作为根节点。

请添加图片描述

怎么样?是不是变成了二叉树,不过它不是普通的二叉树,它是一个二叉查找树

二叉查找树的特点是一个节点的左子树的所有节点都小于这个节点,右子树的所有节点都大于这个节点,这样我们在查询数据时,不需要计算中间节点的位置了,只需将查找的数据与节点的数据进行比较。

假设,我们查找索引值为 key 的节点:

  1. 如果 key 大于根节点,则在右子树中进行查找;
  2. 如果 key 小于根节点,则在左子树中进行查找;
  3. 如果 key 等于根节点,也就是找到了这个节点,返回根节点即可。

二叉查找树查找某个节点的动图演示如下,比如要查找节点 3 :

图片

另外,二叉查找树解决了插入新节点的问题,因为二叉查找树是一个跳跃结构,不必连续排列。这样在插入的时候,新节点可以放在任何位置,不会像线性结构那样插入一个元素,所有元素都需要向后排列。

下面是二叉查找树插入某个节点的动图演示:

请添加图片描述

因此,二叉查找树解决了连续结构插入新元素开销很大的问题,同时又保持着天然的二分结构。

那是不是二叉查找树就可以作为索引的数据结构了呢?

不行不行,二叉查找树存在一个极端情况,会导致它变成一个瘸子!

当每次插入的元素都是二叉查找树中最大的元素,二叉查找树就会退化成了一条链表,查找数据的时间复杂度变成了 O(n),如下动图演示:

请添加图片描述

由于树是存储在磁盘中的,访问每个节点,都对应一次磁盘 I/O 操作(假设一个节点的大小「小于」操作系统的最小读写单位块的大小),也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数,所以树的高度越高,就会影响查询性能。

二叉查找树由于存在退化成链表的可能性,会使得查询操作的时间复杂度从 O(logn) 升为 O(n)。

而且会随着插入的元素越多,树的高度也变高,意味着需要磁盘 IO 操作的次数就越多,这样导致查询性能严重下降,再加上不能范围查询,所以不适合作为数据库的索引结构。

什么是自平衡二叉树?

为了解决二叉查找树会在极端情况下退化成链表的问题,后面就有人提出平衡二叉查找树(AVL 树)

主要是在二叉查找树的基础上增加了一些条件约束:每个节点的左子树和右子树的高度差不能超过 1。也就是说节点的左子树和右子树仍然为平衡二叉树,这样查询操作的时间复杂度就会一直维持在 O(logn) 。

下图是每次插入的元素都是平衡二叉查找树中最大的元素,可以看到,它会维持自平衡:

图片

除了平衡二叉查找树,还有很多自平衡的二叉树,比如红黑树,它也是通过一些约束条件来达到自平衡,不过红黑树的约束条件比较复杂,不是本篇的重点重点,大家可以看《数据结构》相关的书籍来了解红黑树的约束条件。

下面是红黑树插入节点的过程,这左旋右旋的操作,就是为了自平衡。

图片

不管平衡二叉查找树还是红黑树,都会随着插入的元素增多,而导致树的高度变高,这就意味着磁盘 I/O 操作次数多,会影响整体数据查询的效率

比如,下面这个平衡二叉查找树的高度为 5,那么在访问最底部的节点时,就需要磁盘 5 次 I/O 操作。

图片

根本原因是因为它们都是二叉树,也就是每个节点只能保存 2 个子节点 ,如果我们把二叉树改成 M 叉树(M>2)呢?

比如,当 M=3 时,在同样的节点个数情况下,三叉树比二叉树的树高要矮。

图片

因此,当树的节点越多的时候,并且树的分叉数 M 越大的时候,M 叉树的高度会远小于二叉树的高度

什么是 B 树

自平衡二叉树虽然能保持查询操作的时间复杂度在O(logn),但是因为它本质上是一个二叉树,每个节点只能有 2 个子节点,那么当节点个数越多的时候,树的高度也会相应变高,这样就会增加磁盘的 I/O 次数,从而影响数据查询的效率。

为了解决降低树的高度的问题,后面就出来了 B 树,它不再限制一个节点就只能有 2 个子节点,而是允许 M 个子节点 (M>2),从而降低树的高度。

B 树的每一个节点最多可以包括 M 个子节点,M 称为 B 树的阶,所以 B 树就是一个多叉树。

假设 M = 3,那么就是一棵 3 阶的 B 树,特点就是每个节点最多有 2 个(M-1个)数据和最多有 3 个(M个)子节点,超过这些要求的话,就会分裂节点,比如下面的的动图:

图片

我们来看看一棵 3 阶的 B 树的查询过程是怎样的?

图片

假设我们在上图一棵 3 阶的 B 树中要查找的索引值是 9 的记录那么步骤可以分为以下几步:

  1. 与根节点的索引(4,8)进行比较,9 大于 8,那么往右边的子节点走;
  2. 然后该子节点的索引为(10,12),因为 9 小于 10,所以会往该节点的左边子节点走;
  3. 走到索引为9的节点,然后我们找到了索引值 9 的节点。

可以看到,一棵 3 阶的 B 树在查询叶子节点中的数据时,由于树的高度是 3 ,所以在查询过程中会发生 3 次磁盘 I/O 操作。

而如果同样的节点数量在平衡二叉树的场景下,树的高度就会很高,意味着磁盘 I/O 操作会更多。所以,B 树在数据查询中比平衡二叉树效率要高。

但是 B 树的每个节点都包含数据(索引+记录),而用户的记录数据的大小很有可能远远超过了索引数据,这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。

而且,在我们查询位于底层的某个节点(比如 A 记录)过程中,「非 A 记录节点」里的记录数据会从磁盘加载到内存,但是这些记录数据是没用的,我们只是想读取这些节点的索引数据来做比较查询,而「非 A 记录节点」里的记录数据对我们是没用的,这样不仅增多磁盘 I/O 操作次数,也占用内存资源。

另外,如果使用 B 树来做范围查询的话,需要使用中序遍历,这会涉及多个节点的磁盘 I/O 问题,从而导致整体速度下降。

什么是 B+ 树?

B+ 树就是对 B 树做了一个升级,MySQL 中索引的数据结构就是采用了 B+ 树,B+ 树结构如下图:

图片

B+ 树与 B 树差异的点,主要是以下这几点:

  • 叶子节点(最底部的节点)才会存放实际数据(索引+记录),非叶子节点只会存放索引;
  • 所有索引都会在叶子节点出现,叶子节点之间构成一个有序链表;
  • 非叶子节点的索引也会同时存在在子节点中,并且是在子节点中所有索引的最大(或最小)。
  • 非叶子节点中有多少个子节点,就有多少个索引;

下面通过三个方面,比较下 B+ 和 B 树的性能区别。

1、单点查询

B 树进行单个索引查询时,最快可以在 O(1) 的时间代价内就查到,而从平均时间代价来看,会比 B+ 树稍快一些。

但是 B 树的查询波动会比较大,因为每个节点即存索引又存记录,所以有时候访问到了非叶子节点就可以找到索引,而有时需要访问到叶子节点才能找到索引。

B+ 树的非叶子节点不存放实际的记录数据,仅存放索引,因此数据量相同的情况下,相比存储即存索引又存记录的 B 树,B+树的非叶子节点可以存放更多的索引,因此 B+ 树可以比 B 树更「矮胖」,查询底层节点的磁盘 I/O次数会更少

2、插入和删除效率

B+ 树有大量的冗余节点,这样使得删除一个节点的时候,可以直接从叶子节点中删除,甚至可以不动非叶子节点,这样删除非常快,

比如下面这个动图是删除 B+ 树 0004 节点的过程,因为非叶子节点有 0004 的冗余节点,所以在删除的时候,树形结构变化很小:

请添加图片描述

注意,:B+ 树对于非叶子节点的子节点和索引的个数,定义方式可能会有不同,有的是说非叶子节点的子节点的个数为 M 阶,而索引的个数为 M-1(这个是维基百科里的定义),因此我本文关于 B+ 树的动图都是基于这个。但是我在前面介绍 B+ 树与 B+ 树的差异时,说的是「非叶子节点中有多少个子节点,就有多少个索引」,主要是 MySQL 用到的 B+ 树就是这个特性。

下面这个动图是删除 B 树 0008 节点的过程,可能会导致树的复杂变化:

请添加图片描述

甚至,B+ 树在删除根节点的时候,由于存在冗余的节点,所以不会发生复杂的树的变形,比如下面这个动图是删除 B+ 树根节点的过程:

请添加图片描述

B 树则不同,B 树没有冗余节点,删除节点的时候非常复杂,比如删除根节点中的数据,可能涉及复杂的树的变形,比如下面这个动图是删除 B 树根节点的过程:

图片

B+ 树的插入也是一样,有冗余节点,插入可能存在节点的分裂(如果节点饱和),但是最多只涉及树的一条路径。而且 B+ 树会自动平衡,不需要像更多复杂的算法,类似红黑树的旋转操作等。

因此,B+ 树的插入和删除效率更高

3、范围查询

B 树和 B+ 树等值查询原理基本一致,先从根节点查找,然后对比目标数据的范围,最后递归的进入子节点查找。

因为 B+ 树所有叶子节点间还有一个链表进行连接,这种设计对范围查找非常有帮助,比如说我们想知道 12 月 1 日和 12 月 12 日之间的订单,这个时候可以先查找到 12 月 1 日所在的叶子节点,然后利用链表向右遍历,直到找到 12 月12 日的节点,这样就不需要从根节点查询了,进一步节省查询需要的时间。

而 B 树没有将所有叶子节点用链表串联起来的结构,因此只能通过树的遍历来完成范围查询,这会涉及多个节点的磁盘 I/O 操作,范围查询效率不如 B+ 树。

因此,存在大量范围检索的场景,适合使用 B+树,比如数据库。而对于大量的单个索引查询的场景,可以考虑 B 树,比如 nosql 的MongoDB。

MySQL 中的 B+ 树

MySQL 的存储方式根据存储引擎的不同而不同,我们最常用的就是 Innodb 存储引擎,它就是采用了 B+ 树作为了索引的数据结构。

下图就是 Innodb 里的 B+ 树:

图片

但是 Innodb 使用的 B+ 树有一些特别的点,比如:

  • B+ 树的叶子节点之间是用「双向链表」进行连接,这样的好处是既能向右遍历,也能向左遍历。
  • B+ 树点节点内容是数据页,数据页里存放了用户的记录以及各种信息,每个数据页默认大小是 16 KB。

Innodb 根据索引类型不同,分为聚集和二级索引。他们区别在于,聚集索引的叶子节点存放的是实际数据,所有完整的用户记录都存放在聚集索引的叶子节点,而二级索引的叶子节点存放的是主键值,而不是实际数据。

因为表的数据都是存放在聚集索引的叶子节点里,所以 InnoDB 存储引擎一定会为表创建一个聚集索引,且由于数据在物理上只会保存一份,所以聚簇索引只能有一个,而二级索引可以创建多个。

更多关于 Innodb 的 B+ 树,可以看我之前写的这篇:从数据页的角度看 B+ 树 (opens new window)

总结

MySQL 是会将数据持久化在硬盘,而存储功能是由 MySQL 存储引擎实现的,所以讨论 MySQL 使用哪种数据结构作为索引,实际上是在讨论存储引使用哪种数据结构作为索引,InnoDB 是 MySQL 默认的存储引擎,它就是采用了 B+ 树作为索引的数据结构。

要设计一个 MySQL 的索引数据结构,不仅仅考虑数据结构增删改的时间复杂度,更重要的是要考虑磁盘 I/0 的操作次数。因为索引和记录都是存放在硬盘,硬盘是一个非常慢的存储设备,我们在查询数据的时候,最好能在尽可能少的磁盘 I/0 的操作次数内完成。

二分查找树虽然是一个天然的二分结构,能很好的利用二分查找快速定位数据,但是它存在一种极端的情况,每当插入的元素都是树内最大的元素,就会导致二分查找树退化成一个链表,此时查询复杂度就会从 O(logn)降低为 O(n)。

为了解决二分查找树退化成链表的问题,就出现了自平衡二叉树,保证了查询操作的时间复杂度就会一直维持在 O(logn) 。但是它本质上还是一个二叉树,每个节点只能有 2 个子节点,随着元素的增多,树的高度会越来越高。

而树的高度决定于磁盘 I/O 操作的次数,因为树是存储在磁盘中的,访问每个节点,都对应一次磁盘 I/O 操作,也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数,所以树的高度越高,就会影响查询性能。

B 树和 B+ 都是通过多叉树的方式,会将树的高度变矮,所以这两个数据结构非常适合检索存于磁盘中的数据。

但是 MySQL 默认的存储引擎 InnoDB 采用的是 B+ 作为索引的数据结构,原因有:

  • B+ 树的非叶子节点不存放实际的记录数据,仅存放索引,因此数据量相同的情况下,相比存储即存索引又存记录的 B 树,B+树的非叶子节点可以存放更多的索引,因此 B+ 树可以比 B 树更「矮胖」,查询底层节点的磁盘 I/O次数会更少。
  • B+ 树有大量的冗余节点(所有非叶子节点都是冗余索引),这些冗余索引让 B+ 树在插入、删除的效率都更高,比如删除根节点的时候,不会像 B 树那样会发生复杂的树的变化;
  • B+ 树叶子节点之间用链表连接了起来,有利于范围查询,而 B 树要实现范围查询,因此只能通过树的遍历来完成范围查询,这会涉及多个节点的磁盘 I/O 操作,范围查询效率不如 B+ 树。

MySQL索引失效有哪些情况?

在工作中,如果我们想提高一条语句查询速度,通常都会想对字段建立索引。

但是索引并不是万能的。建立了索引,并不意味着任何查询语句都能走索引扫描。

稍不注意,可能你写的查询语句是会导致索引失效,从而走了全表扫描,虽然查询的结果没问题,但是查询的性能大大降低。

不仅会用实验案例给大家说明,也会清楚每个索引失效的原因

发车!

图片

索引存储结构长什么样?

我们先来看看索引存储结构长什么样?因为只有知道索引的存储结构,才能更好的理解索引失效的问题。

索引的存储结构跟 MySQL 使用哪种存储引擎有关,因为存储引擎就是负责将数据持久化在磁盘中,而不同的存储引擎采用的索引数据结构也会不相同。

MySQL 默认的存储引擎是 InnoDB,它采用 B+Tree 作为索引的数据结构,至于为什么选择 B+ 树作为索引的数据结构 ,详细的分析可以看我这篇文章:为什么 MySQL 喜欢 B+ 树?(opens new window)

在创建表时,InnoDB 存储引擎默认会创建一个主键索引,也就是聚簇索引,其它索引都属于二级索引。

MySQL 的 MyISAM 存储引擎支持多种索引数据结构,比如 B+ 树索引、R 树索引、Full-Text 索引。MyISAM 存储引擎在创建表时,创建的主键索引默认使用的是 B+ 树索引。

虽然,InnoDB 和 MyISAM 都支持 B+ 树索引,但是它们数据的存储结构实现方式不同。不同之处在于:

  • InnoDB 存储引擎:B+ 树索引的叶子节点保存数据本身;
  • MyISAM 存储引擎:B+ 树索引的叶子节点保存数据的物理地址;

接下来,我举个例子,给大家展示下这两种存储引擎的索引存储结构的区别。

这里有一张 t_user 表,其中 id 字段为主键索引,其他都是普通字段。

图片

如果使用的是 MyISAM 存储引擎,B+ 树索引的叶子节点保存数据的物理地址,即用户数据的指针,如下图:

图片

如果使用的是 InnoDB 存储引擎, B+ 树索引的叶子节点保存数据本身,如下图所示:

图片

InnoDB 存储引擎根据索引类型不同,分为聚簇索引(上图就是聚簇索引)和二级索引。它们区别在于,聚簇索引的叶子节点存放的是实际数据,所有完整的用户数据都存放在聚簇索引的叶子节点,而二级索引的叶子节点存放的是主键值,而不是实际数据。

如果将 name 字段设置为普通索引,那么这个二级索引长下图这样,叶子节点仅存放主键值。

图片

知道了 InnoDB 存储引擎的聚簇索引和二级索引的存储结构后,接下来举几个查询语句,说下查询过程是怎么选择用哪个索引类型的。

在我们使用「主键索引」字段作为条件查询的时候,如果要查询的数据都在「聚簇索引」的叶子节点里,那么就会在「聚簇索引」中的 B+ 树检索到对应的叶子节点,然后直接读取要查询的数据。如下面这条语句:

在我们使用「二级索引」字段作为条件查询的时候,如果要查询的数据都在「聚簇索引」的叶子节点里,那么需要检索两颗B+树:

  • 先在「二级索引」的 B+ 树找到对应的叶子节点,获取主键值;
  • 然后用上一步获取的主键值,在「聚簇索引」中的 B+ 树检索到对应的叶子节点,然后获取要查询的数据。

上面这个过程叫做回表,如下面这条语句:

在我们使用「二级索引」字段作为条件查询的时候,如果要查询的数据在「二级索引」的叶子节点,那么只需要在「二级索引」的 B+ 树找到对应的叶子节点,然后读取要查询的数据,这个过程叫做覆盖索引。如下面这条语句:

上面这些查询语句的条件都用到了索引列,所以在查询过程都用上了索引。

但是并不意味着,查询条件用上了索引列,就查询过程就一定都用上索引,接下来我们再一起看看哪些情况会导致索引失效,而发生全表扫描。

首先说明下,下面的实验案例,我使用的 MySQL 版本为 8.0.26

对索引使用左或者左右模糊匹配

当我们使用左或者左右模糊匹配的时候,也就是 like %xx 或者 like %xx% 这两种方式都会造成索引失效。

比如下面的 like 语句,查询 name 后缀为「林」的用户,执行计划中的 type=ALL 就代表了全表扫描,而没有走索引。

图片

如果是查询 name 前缀为林的用户,那么就会走索引扫描,执行计划中的 type=range 表示走索引扫描,key=index_name 看到实际走了 index_name 索引:

图片

为什么 like 关键字左或者左右模糊匹配无法走索引呢?

因为索引 B+ 树是按照「索引值」有序排列存储的,只能根据前缀进行比较。

举个例子,下面这张二级索引图,是以 name 字段有序排列存储的。

图片

假设我们要查询 name 字段前缀为「林」的数据,也就是 name like '林%',扫描索引的过程:

  • 首节点查询比较:林这个字的拼音大小比首节点的第一个索引值中的陈字大,但是比首节点的第二个索引值中的周字小,所以选择去节点2继续查询;
  • 节点 2 查询比较:节点2的第一个索引值中的陈字的拼音大小比林字小,所以继续看下一个索引值,发现节点2有与林字前缀匹配的索引值,于是就往叶子节点查询,即叶子节点4;
  • 节点 4 查询比较:节点4的第一个索引值的前缀符合林字,于是就读取该行数据,接着继续往右匹配,直到匹配不到前缀为林的索引值。

如果使用 name like '%林' 方式来查询,因为查询的结果可能是「陈林、张林、周林」等之类的,所以不知道从哪个索引值开始比较,于是就只能通过全表扫描的方式来查询。

想要更详细了解 InnoDB 的 B+ 树查询过程,可以看我写的这篇:B+ 树里的节点里存放的是什么呢?查询数据的过程又是怎样的?(opens new window)

对索引使用函数

有时候我们会用一些 MySQL 自带的函数来得到我们想要的结果,这时候要注意了,如果查询条件中对索引字段使用函数,就会导致索引失效。

比如下面这条语句查询条件中对 name 字段使用了 LENGTH 函数,执行计划中的 type=ALL,代表了全表扫描:

图片

为什么对索引使用函数,就无法走索引了呢?

因为索引保存的是索引字段的原始值,而不是经过函数计算后的值,自然就没办法走索引了。

不过,从 MySQL 8.0 开始,索引特性增加了函数索引,即可以针对函数计算后的值建立一个索引,也就是说该索引的值是函数计算后的值,所以就可以通过扫描索引来查询数据。

举个例子,我通过下面这条语句,对 length(name) 的计算结果建立一个名为 idx_name_length 的索引。

然后我再用下面这条查询语句,这时候就会走索引了。

图片

对索引进行表达式计算

在查询条件中对索引进行表达式计算,也是无法走索引的。

比如,下面这条查询语句,执行计划中 type = ALL,说明是通过全表扫描的方式查询数据的:

图片

但是,如果把查询语句的条件改成 where id = 10 - 1,这样就不是在索引字段进行表达式计算了,于是就可以走索引查询了。

图片

为什么对索引进行表达式计算,就无法走索引了呢?

原因跟对索引使用函数差不多。

因为索引保存的是索引字段的原始值,而不是 id + 1 表达式计算后的值,所以无法走索引,只能通过把索引字段的取值都取出来,然后依次进行表达式的计算来进行条件判断,因此采用的就是全表扫描的方式。

有的同学可能会说,这种对索引进行简单的表达式计算,在代码特殊处理下,应该是可以做到索引扫描的,比方将 id + 1 = 10 变成 id = 10 - 1。

是的,是能够实现,但是 MySQL 还是偷了这个懒,没有实现。

我的想法是,可能也是因为,表达式计算的情况多种多样,每种都要考虑的话,代码可能会很臃肿,所以干脆将这种索引失效的场景告诉程序员,让程序员自己保证在查询条件中不要对索引进行表达式计算。

对索引隐式类型转换(Implicit Type Conversion)

如果索引字段是字符串类型,但是在条件查询中,输入的参数是整型的话,你会在执行计划的结果发现这条语句会走全表扫描。

我在原本的 t_user 表增加了 phone 字段,是二级索引且类型是 varchar。

图片

然后我在条件查询中,用整型作为输入参数,此时执行计划中 type = ALL,所以是通过全表扫描来查询数据的。

图片

但是如果索引字段是整型类型,查询条件中的输入参数即使字符串,是不会导致索引失效,还是可以走索引扫描。

我们再看第二个例子,id 是整型,但是下面这条语句还是走了索引扫描的。

图片

为什么第一个例子会导致索引失效,而第二例子不会呢?

要明白这个原因,首先我们要知道 MySQL 的数据类型转换规则是什么?就是看 MySQL 是会将字符串转成数字处理,还是将数字转换成字符串处理。

我在看《mysql45讲的时候》看到一个简单的测试方式,就是通过 select “10” > 9 的结果来知道MySQL 的数据类型转换规则是什么:

  • 如果规则是 MySQL 会将自动「字符串」转换成「数字」,就相当于 select 10 > 9,这个就是数字比较,所以结果应该是 1;
  • 如果规则是 MySQL 会将自动「数字」转换成「字符串」,就相当于 select "10" > "9",这个是字符串比较,字符串比较大小是逐位从高位到低位逐个比较(按ascii码) ,那么"10"字符串相当于 “1”和“0”字符的组合,所以先是拿 “1” 字符和 “9” 字符比较,因为 “1” 字符比 “9” 字符小,所以结果应该是 0。

在 MySQL 中,执行的结果如下图:

有关MySQL中的索引面试题系列

上面的结果为 1,说明 MySQL 在遇到字符串和数字比较的时候,会自动把字符串转为数字,然后再进行比较

前面的例子一中的查询语句,我也跟大家说了是会走全表扫描:

这是因为 phone 字段为字符串,所以 MySQL 要会自动把字符串转为数字,所以这条语句相当于:

可以看到,CAST 函数是作用在了 phone 字段,而 phone 字段是索引,也就是对索引使用了函数!而前面我们也说了,对索引使用函数是会导致索引失效的

例子二中的查询语句,我跟大家说了是会走索引扫描:

这时因为字符串部分是输入参数,也就需要将字符串转为数字,所以这条语句相当于:

可以看到,索引字段并没有用任何函数,CAST 函数是用在了输入参数,因此是可以走索引扫描的。

联合索引非最左匹配

对主键字段建立的索引叫做聚簇索引,对普通字段建立的索引叫做二级索引。

那么多个普通字段组合在一起创建的索引就叫做联合索引,也叫组合索引。

创建联合索引时,我们需要注意创建时的顺序问题,因为联合索引 (a, b, c) 和 (c, b, a) 在使用的时候会存在差别。

联合索引要能正确使用需要遵循最左匹配原则,也就是按照最左优先的方式进行索引的匹配。

比如,如果创建了一个 (a, b, c) 联合索引,如果查询条件是以下这几种,就可以匹配上联合索引:

  • where a=1;
  • where a=1 and b=2 and c=3;
  • where a=1 and b=2;

需要注意的是,因为有查询优化器,所以 a 字段在 where 子句的顺序并不重要。

但是,如果查询条件是以下这几种,因为不符合最左匹配原则,所以就无法匹配上联合索引,联合索引就会失效:

  • where b=2;
  • where c=3;
  • where b=2 and c=3;

有一个比较特殊的查询条件:where a = 1 and c = 3 ,符合最左匹配吗?

这种其实严格意义上来说是属于索引截断,不同版本处理方式也不一样。

MySQL 5.5 的话,前面 a 会走索引,在联合索引找到主键值后,开始回表,到主键索引读取数据行,然后再比对 c 字段的值。

从 MySQL 5.6 之后,有一个索引下推功能,可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。

大概原理是:截断的字段会被下推到存储引擎层进行条件判断(因为 c 字段的值是在 (a, b, c) 联合索引里的),然后过滤出符合条件的数据后再返回给 Server 层。由于在引擎层就过滤掉大量的数据,无需再回表读取数据来进行判断,减少回表次数,从而提升了性能。

比如下面这条 where a = 1 and c = 0 语句,我们可以从执行计划中的 Extra=Using index condition 使用了索引下推功能。

图片

为什么联合索引不遵循最左匹配原则就会失效?

原因是,在联合索引的情况下,数据是按照索引第一列排序,第一列数据相同时才会按照第二列排序。

也就是说,如果我们想使用联合索引中尽可能多的列,查询条件中的各个列必须是联合索引中从最左边开始连续的列。如果我们仅仅按照第二列搜索,肯定无法走索引。

WHERE 子句中的 OR

在 WHERE 子句中,如果在 OR 前的条件列是索引列,而在 OR 后的条件列不是索引列,那么索引会失效。

举个例子,比如下面的查询语句,id 是主键,age 是普通列,从执行计划的结果看,是走了全表扫描。

图片

这是因为 OR 的含义就是两个只要满足一个即可,因此只有一个条件列是索引列是没有意义的,只要有条件列不是索引列,就会进行全表扫描。

要解决办法很简单,将 age 字段设置为索引即可。

图片

可以看到 type=index merge, index merge 的意思就是对 id 和 age 分别进行了扫描,然后将这两个结果集进行了合并,这样做的好处就是避免了全表扫描。

MySQL 使用 like “%x“,索引一定会失效吗?

一个有点意思的思考题:

图片

这个思考题其实是出自于,我之前这篇文章「一条 SQL 语句引发的思考 (opens new window)」中留言区一位读者朋友出的问题。

很多读者都在留言区说了自己的想法,也有不少读者私聊我答案到底是什么?

所以,我今晚就跟大家聊聊这个思考题。

题目一

题目一很简单,相信大家都能分析出答案,我昨天分享的索引失效文章里也提及过。

「题目 1 」的数据库表如下,id 是主键索引,name 是二级索引,其他字段都是非索引字段。

图片

这四条模糊匹配的查询语句,第一条和第二条都会走索引扫描,而且都是选择扫描二级索引(index_name),我贴个第二条查询语句的执行计划结果图:

图片

而第三和第四条会发生索引失效,执行计划的结果 type= ALL,代表了全表扫描。

图片

题目二

题目 2 的数据库表特别之处在于,只有两个字段,一个是主键索引 id,另外一个是二级索引 name。

图片

针对题目 2 的数据表,第一条和第二条模糊查询语句也是一样可以走索引扫描,第二条查询语句的执行计划如下,Extra 里的 Using index 说明用上了覆盖索引:

图片

我们来看一下第三条查询语句的执行计划(第四条也是一样的结果):

图片

从执行计划的结果中,可以看到 key=index_name,也就是说用上了二级索引,而且从 Extra 里的 Using index 说明用上了覆盖索引。

这是为什么呢?

首先,这张表的字段没有「非索引」字段,所以 select * 相当于 select id,name,然后这个查询的数据都在二级索引的 B+ 树,因为二级索引的 B+ 树的叶子节点包含「索引值+主键值」,所以查二级索引的 B+ 树就能查到全部结果了,这个就是覆盖索引。

但是执行计划里的 type 是 index,这代表着是通过全扫描二级索引的 B+ 树的方式查询到数据的,也就是遍历了整颗索引树。

而第一和第二条查询语句的执行计划中 type 是 range,表示对索引列进行范围查询,也就是利用了索引树的有序性的特点,通过查询比较的方式,快速定位到了数据行。

所以,type=range 的查询效率会比 type=index 的高一些。

为什么选择全扫描二级索引树,而不扫描聚簇索引树呢?

因为二级索引树的记录东西很少,就只有「索引列+主键值」,而聚簇索引记录的东西会更多,比如聚簇索引中的叶子节点则记录了主键值、事务 id、用于事务和 MVCC 的回滚指针以及所有的剩余列。

再加上,这个 select * 不用执行回表操作。

所以, MySQL 优化器认为直接遍历二级索引树要比遍历聚簇索引树的成本要小的多,因此 MySQL 选择了「全扫描二级索引树」的方式查询数据。

为什么这个数据表加了非索引字段,执行同样的查询语句后,怎么变成走的是全表扫描呢?

加了其他字段后,select * from t_user where name like "%xx"; 要查询的数据就不能只在二级索引树里找了,得需要回表操作才能完成查询的工作,再加上是左模糊匹配,无法利用索引树的有序性来快速定位数据,所以得在二级索引树逐一遍历,获取主键值后,再到聚簇索引树检索到对应的数据行,这样实在太累了。

所以,优化器认为上面这样的查询过程的成本实在太高了,所以直接选择全表扫描的方式来查询数据。


从这个思考题我们知道了,使用左模糊匹配(like "%xx")并不一定会走全表扫描,关键还是看数据表中的字段。

如果数据库表中的字段只有主键+二级索引,那么即使使用了左模糊匹配,也不会走全表扫描(type=all),而是走全扫描二级索引树(type=index)。

再说一个相似,我们都知道联合索引要遵循最左匹配才能走索引,但是如果数据库表中的字段都是索引的话,即使查询过程中,没有遵循最左匹配原则,也是走全扫描二级索引树(type=index),比如下图:

图片

总结:为什么索引没有被使用?

会发生索引失效的情况:

  • 当我们使用左或者左右模糊匹配的时候,也就是 like %xx 或者 like %xx%这两种方式都会造成索引失效;

  • 当我们在查询条件中对索引列使用函数、表达式计算等,就会导致索引失效。如果对索引字段进行函数、算术运算或其他表达式等操作,那么MySQL不使用索引。

  • 如果MySQL估计使用全表扫描要比使用索引快,那么MySQL不使用索引。

  • MySQL 在遇到字符串和数字比较的时候,会自动把字符串转为数字,然后再进行比较。如果字符串是索引列,而条件语句中的输入参数是数字的话,那么索引列会发生隐式类型转换,由于隐式类型转换是通过 CAST 函数实现的,等同于对索引列使用了函数,所以就会导致索引失效。因此,若索引列是字符串,那么给出的值需要加上引号

    若索引列出现了隐式类型转换(Implicit Type Conversion),则MySQL不会使用索引。常见的情况是,如果在SQL的WHERE条件中,字段类型为字符串,而其值为数值,那么MySQL不会使用索引,这个规则和Oracle是一致的,所以,字符类型的字段值应该加上引号。例如,表t_base_user的telephone列是一个字符类型的索引列,则:

    这个语句在执行的时候不会选择索引,应该修改为:

  • 联合索引要能正确使用需要遵循最左匹配原则,也就是按照最左优先的方式进行索引的匹配,否则就会导致索引失效。对于多列索引,若没有使用前导列,则MySQL不会使用索引。

  • 在 WHERE 子句中,如果在 OR 前的条件列是索引列,而在 OR 后的条件列不是索引列,那么索引会失效。如果WHERE条件中含有OR,除非OR条件中的所有列都是索引列,否则MySQL不会选择索引。

  • 采用is null条件时,因为索引上根本没Null值,不能利用到索引,只能全表扫描

    更准确的说,单列索引不存储null值,复合索引不存储全为null的值。索引不能存储Null,所以对这列采用is null条件时,因为索引上根本

    没Null值,不能利用到索引,只能全表扫描。

    为什么索引列不能存Null值?

    将索引列值进行建树,其中必然涉及到诸多的比较操作。Null值的特殊性就在于参与的运算大多取值为null。

    这样的话,null值实际上是不能参与进建索引的过程。也就是说,null值不会像其他取值一样出现在索引树的叶子节点上。

  • 不适合键值较少的列(重复数据较多的列)

    假如索引列TYPE有5个键值,如果有1万条数据,那么 WHERE TYPE = 1将访问表中的2000个数据块。

    再加上访问索引块,一共要访问大于200个的数据块。

    如果全表扫描,假设10条数据一个数据块,那么只需访问1000个数据块,既然全表扫描访问的数据块

    少一些,肯定就不会利用索引了。

  • 在使用cast函数时,需要保证字符集一样,否则MySQL不会使用索引。例如,表t_base_user的telephone列的字符集为latin1,则在使用cast函数时需要指定字符集:

MySQL中的count(*) 和 count(1) 有什么区别?哪个性能最好?

当我们对一张数据表中的记录进行统计的时候,习惯都会使用 count 函数来统计,但是 count 函数传入的参数有很多种,比如 count(1)、count(*)、count(字段) 等。

到底哪种效率是最好的呢?是不是 count(*) 效率最差?

我曾经以为 count(*) 是效率最差的,因为认知上 selete * from t 会读取所有表中的字段,所以凡事带有 * 字符的就觉得会读取表中所有的字段,当时网上有很多博客也这么说。

但是,当我深入 count 函数的原理后,被啪啪啪的打脸了!

不多说, 发车!

图片

哪种 count 性能最好?

哪种 count 性能最好?

我先直接说结论:

图片

要弄明白这个,我们得要深入 count 的原理,以下内容基于常用的 innodb 存储引擎来说明。

count() 是什么?

count() 是一个聚合函数,函数的参数不仅可以是字段名,也可以是其他任意表达式,该函数作用是统计符合查询条件的记录中,函数指定的参数不为 NULL 的记录有多少个

假设 count() 函数的参数是字段名,如下:

这条语句是统计「 t_order 表中,name 字段不为 NULL 的记录」有多少个。也就是说,如果某一条记录中的 name 字段的值为 NULL,则就不会被统计进去。

再来假设 count() 函数的参数是数字 1 这个表达式,如下:

这条语句是统计「 t_order 表中,1 这个表达式不为 NULL 的记录」有多少个。

1 这个表达式就是单纯数字,它永远都不是 NULL,所以上面这条语句,其实是在统计 t_order 表中有多少个记录。

count(主键字段) 执行过程是怎样的?

在通过 count 函数统计有多少个记录时,MySQL 的 server 层会维护一个名叫 count 的变量。

server 层会循环向 InnoDB 读取一条记录,如果 count 函数指定的参数不为 NULL,那么就会将变量 count 加 1,直到符合查询的全部记录被读完,就退出循环。最后将 count 变量的值发送给客户端。

InnoDB 是通过 B+ 树来保持记录的,根据索引的类型又分为聚簇索引和二级索引,它们区别在于,聚簇索引的叶子节点存放的是实际数据,而二级索引的叶子节点存放的是主键值,而不是实际数据。

用下面这条语句作为例子:

如果表里只有主键索引,没有二级索引时,那么,InnoDB 循环遍历聚簇索引,将读取到的记录返回给 server 层,然后读取记录中的 id 值,就会 id 值判断是否为 NULL,如果不为 NULL,就将 count 变量加 1。

图片

但是,如果表里有二级索引时,InnoDB 循环遍历的对象就不是聚簇索引,而是二级索引。

图片

这是因为相同数量的二级索引记录可以比聚簇索引记录占用更少的存储空间,所以二级索引树比聚簇索引树小,这样遍历二级索引的 I/O 成本比遍历聚簇索引的 I/O 成本小,因此「优化器」优先选择的是二级索引。

count(1) 执行过程是怎样的?

用下面这条语句作为例子:

本人提供Oracle、MySQL、PG等数据库的培训和考证业务,私聊QQ646634621或微信db_bao,谢谢!

如果表里只有主键索引,没有二级索引时。

图片

那么,InnoDB 循环遍历聚簇索引(主键索引),将读取到的记录返回给 server 层,但是不会读取记录中的任何字段的值,因为 count 函数的参数是 1,不是字段,所以不需要读取记录中的字段值。参数 1 很明显并不是 NULL,因此 server 层每从 InnoDB 读取到一条记录,就将 count 变量加 1。

可以看到,count(1) 相比 count(主键字段) 少一个步骤,就是不需要读取记录中的字段值,所以通常会说 count(1) 执行效率会比 count(主键字段) 高一点。

但是,如果表里有二级索引时,InnoDB 循环遍历的对象就二级索引了。

图片

count(*) 执行过程是怎样的?

看到 * 这个字符的时候,是不是大家觉得是读取记录中的所有字段值?

对于 selete * 这条语句来说是这个意思,但是在 count(*) 中并不是这个意思。

count(*) 其实等于 count(0),也就是说,当你使用 count(*) 时,MySQL 会将 * 参数转化为参数 0 来处理。

图片

所以,count(*) 执行过程跟 count(1) 执行过程基本一样的,性能没有什么差异。

在 MySQL 5.7 的官方手册中有这么一句话:

InnoDB handles SELECT COUNT(*) and SELECT COUNT(1) operations in the same way. There is no performance difference.

翻译:InnoDB以相同的方式处理SELECT COUNT(*)SELECT COUNT(1)操作,没有性能差异。

而且 *MySQL 会对 count() 和 count(1) 有个优化,如果有多个二级索引的时候,优化器会使用key_len 最小的二级索引进行扫描。只有当没有二级索引的时候,才会采用主键索引来进行统计。**

count(字段) 执行过程是怎样的?

count(字段) 的执行效率相比前面的 count(1)、 count(*)、 count(主键字段) 执行效率是最差的。

用下面这条语句作为例子:

对于这个查询来说,会采用全表扫描的方式来计数,所以它的执行效率是比较差的。

图片

为什么要通过遍历的方式来计数?

你可以会好奇,为什么 count 函数需要通过遍历的方式来统计记录个数?

我前面将的案例都是基于 Innodb 存储引擎来说明的,但是在 MyISAM 存储引擎里,执行 count 函数的方式是不一样的,通常在没有任何查询条件下的 count(*),MyISAM 的查询速度要明显快于 InnoDB。

使用 MyISAM 引擎时,执行 count 函数只需要 O(1 )复杂度,这是因为每张 MyISAM 的数据表都有一个 meta 信息有存储了row_count值,由表级锁保证一致性,所以直接读取 row_count 值就是 count 函数的执行结果。

而 InnoDB 存储引擎是支持事务的,同一个时刻的多个查询,由于多版本并发控制(MVCC)的原因,InnoDB 表“应该返回多少行”也是不确定的,所以无法像 MyISAM一样,只维护一个 row_count 变量。

举个例子,假设表 t_order 有 100 条记录,现在有两个会话并行以下语句:

有关MySQL中的索引面试题系列

在会话 A 和会话 B的最后一个时刻,同时查表 t_order 的记录总个数,可以发现,显示的结果是不一样的。所以,在使用 InnoDB 存储引擎时,就需要扫描表来统计具体的记录。

而当带上 where 条件语句之后,MyISAM 跟 InnoDB 就没有区别了,它们都需要扫描表来进行记录个数的统计。

如何优化 count(*)?

如果对一张大表经常用 count(*) 来做统计,其实是很不好的。

比如下面我这个案例,表 t_order 共有 1200+ 万条记录,我也创建了二级索引,但是执行一次 select count(*) from t_order 要花费差不多 5 秒!

图片

面对大表的记录统计,我们有没有什么其他更好的办法呢?

第一种,近似值

如果你的业务对于统计个数不需要很精确,比如搜索引擎在搜索关键词的时候,给出的搜索结果条数是一个大概值。

有关MySQL中的索引面试题系列

这时,我们就可以使用 show table status 或者 explain 命令来表进行估算。

执行 explain 命令效率是很高的,因为它并不会真正的去查询,下图中的 rows 字段值就是 explain 命令对表 t_order 记录的估算值。

有关MySQL中的索引面试题系列

第二种,额外表保存计数值

如果是想精确的获取表的记录总数,我们可以将这个计数值保存到单独的一张计数表中。

当我们在数据表插入一条记录的同时,将计数表中的计数字段 + 1。也就是说,在新增和删除操作时,我们需要额外维护这个计数表。

小结

在执行count(1)、 count(*)、 count(主键字段)的时候,MySQL 会对 count(*) 和 count(1) 有个优化,如果有多个二级索引的时候,优化器会使用key_len 最小的二级索引进行扫描。只有当没有二级索引的时候,才会采用主键索引来进行统计。

所以,如果要执行 count(1)、 count(*)、 count(主键字段) 时,尽量在数据表上建立二级索引,这样优化器会自动采用 key_len 最小的二级索引进行扫描,相比于扫描主键索引效率会高一些。

另外,不要使用 count(字段) 来统计记录个数,因为它的效率是最差的,会采用全表扫描的方式来统计。如果你非要统计表中该字段不为 NULL 的记录个数,建议给这个字段建立一个二级索引。

有关count(*)的优化也可以参考:https://www.xmmup.com/mysqlzhiselect-countyouhuaanli.html

参考

https://xiaolincoding.com/mysql/index/index_interview.html

https://xiaolincoding.com/mysql/index/page.html

https://xiaolincoding.com/mysql/index/why_index_chose_bpuls_tree.html

https://xiaolincoding.com/mysql/index/index_lose.html

标签:

头像

小麦苗

学习或考证,均可联系麦老师,请加微信db_bao或QQ646634621

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

2 + 15 =

 

嘿,我是小麦,需要帮助随时找我哦
  • 18509239930
  • 个人微信

  • 麦老师QQ聊天
  • 个人邮箱
  • 点击加入QQ群
  • 个人微店

  • 回到顶部
返回顶部