什么是索引?

索引是用于快速查询数据的数据结构。通过索引去查找我们需要的数据,在数据量比较大时,性能会大大提升;但是错误的创建索引并不会提升查询的效率,所以我们需要正确的认识索引以及用正确的形式创建索引。

索引结构

B树和B+树是目前的数据库应用中最常用、有效的索引结构。因为数据库中的数据一般保存在磁盘中,而IO操作是一个极其消耗时间的操作,所以我们需要通过B树或B+树进行优化,减少IO次数来提高效率。

在数据库中,可以根据B类树的特点,构建一个多阶的B树或B+树,其高度一般在2到3层,这样的话,对于查找某一个节点中关键字的值时,最多只需要2到3次IO。

B树

B树的添加删除效果可以在 B树的演示网站 上查看

B树是一种平衡树数据结构,它的查找效率很高,所以通常会作为数据库的索引结构使用,它进行搜索的时间复杂度是 O(log n) 。

在一个 m 阶的B树中,它可以具有 m-1 数量的 key ,阶数表示了一个节点最多拥有的子节点数量。B树的每个内部节点包含的 key 用作分隔其子树的分离值。

下图是 key 值为 1 到 14 组成的一个3阶的B树:

上图中的数字即为节点中的 key ,每个key对应一个data,在mysql中,data就表示了这个 key 对应的数据在硬盘上的地址。

B+树

B+树的添加删除效果可以在 B+树的演示网站 上查看

B+树是B树的一个变种,在B+树中,只有叶子节点保存了数据信息,其他节点仅包含了key信息,且叶子节点中包含了指向下一个叶子节点的指针来加速顺序访问。

下图是 key 值为 1 到 14 组成的一个4阶B+树:

一般索引也是存储在磁盘上的,所以索引的查找过程也会产生磁盘的IO消耗;而索引要尽量减少查找过程中磁盘IO的存取次数。

因为B+树的数据信息只存储在叶子节点,所以同样大小的磁盘页与B树相比存储的关键字变得更多,相应的也会减少IO次数。一般而言,每个节点会设置为一页大小,也就是一次IO读取,所以使用关键字查找时,B树的IO次数会多于B+树。

并且B树的查找性能并不稳定,B树需要查找的数据可能在根节点,也可能在叶子节点;而B+树的查询必须查找到叶子节点,所以每次的查找都是稳定的,且因为叶子节点的数据有指向下一个叶子节点的指针,所以在范围查询时只需要遍历叶子节点即可。

而对于关系型数据库来讲,范围查询的使用也是比较关键的,所以MySQL采用了B+树作为索引结构,而且在B+树中,查询的性能更加稳定,因为每次查询都必须到叶子节点。

索引实现

索引的实现因存储引擎的不同,实现的方式也不同,下面只介绍B+树在最常用的 Innodb 引擎中的体现方式。

Innodb 存储引擎

在innodb的表中,有两种索引类型,聚簇索引和辅助索引,两种索引的内部实现都是B+树,在聚簇索引中,聚簇索引会以表的主键作为索引的键,且数据行信息保存在叶子节点中。

假设我们现在有主键为id的一张用户表,数据如下:

id name age
101 zhangsan 18
102 lisi 20
103 wangwu 22
104 zhaoliu 21

那么使用主键列id构建的聚簇索引如下:

除了聚簇索引之外的索引被称为辅助索引,辅助索引的键为其指定的列,在索引中的叶子节点数据为该行记录的主键值,根据此主键值再去聚簇索引中根据主键查询到对应的行。

使用 name 列构建的辅助索引如下:

辅助索引的存在并不会影响聚簇索引,一个表中虽然只能有一个聚簇索引,但对辅助索引没有限制;当通过辅助索引来查询数据时,会先通过辅助索引的叶子节点获取指向聚簇索引的主键,然后通过聚簇索引来找到一个完整的行记录。

也就是说,如果我们需要在上例数据中,通过name索引查找 “lisi” 的行记录,那么需要先对辅助索引遍历两次找到指定的主键,然后根据主键再去聚簇索引中进行2次查找,因此一共需要进行4次逻辑IO操作l来访问最终的数据页。

在字符串列中,辅助索引也可以创建仅使用列的前几个字符的索引,这样创建的索引可以使索引文件更小,在创建辅助索引时可以指定索引的前缀长度。

索引使用策略

如果我们在表中没有创建索引,MySQL就必须从数据的第一行开始进行全表的扫描以查找到相关记录。表的数据越大,查找的成本也就越高;如果表中有相关的索引,那么MySQL就可以快速的定位到需要查找的数据,而不需要进行全表的扫描。

但是索引也不是在所有的查询条件下出现的列都需要添加,对于添加索引而言,还是有几个需要注意的关键点的。

高选择性

使用索引的其中一个关键点就是,索引对于列的选择而言必须是具有高选择性的,例如对于性别字段,它的取值内容是固定的,或者说取值范围很小,即大部分是重复的数据,所以这种数据内容是低选择性的。

对于索引而言,如果需要查询的值在数据中能匹配大量的行数据,那么使用索引的效率是比较低下的;只有在索引匹配少量的数据时,索引才能高效的查询数据。

相反,如果某个列的数据大部分不会重复,例如姓名字段,则使用B+树索引比较合适,因此,在对一个列建立索引时,需要考虑该列的选择性。

索引选择性的计算公式是基数除以数据总行数,例如对于性别字段,假如表中有一万行数据,其中五千是男,五千是女,则基数为男和女,也就是 2/10000 ,最终计算出的选择性为 0.0002 ;而对于姓名字段,可能一万行数据中没有重复的,那基数就为 10000 /10000 ,选择性为 1,则从选择性方面而言,非常适合建立索引。

当选择性越大,则建立的索引价值也就越大。

条件匹配

当在列上建立了索引后,在 where 条件中与索引中的列进行匹配,就可以加速查询,例如前面提到的用户表,如果建立了 name 列及 age 列的两个辅助索引,那么我们在条件查询中可以对添加了索引的列进行全值匹配、前缀匹配或者范围匹配。

以下是 sql 查询语句的示例

1
2
3
select * from user where name = 'zhangsan' 
select * from user where name LIKE 'zha%'
select * from user where age > 18 and age < 22

联合索引

联合索引是指在多个列上建立索引,辅助索引中,不仅仅只能用一列创建索引,还可以创建多列的联合索引,联合索引中最多可以包含16列。

对于多列的索引,我们在条件查询中可以用到第一列,前两列及前三列等等,只要我们在条件查询中正确的指定联合索引中的列,则联合索引就可以加速查询。

例如对于用户表,我们建立了一个index(name,age)的联合索引,那么就可以查询 name 列和 age 列的组合条件,也可以仅指定 name 列的查询。

联合索引的内部结构其实还是B+树,但是其关键字并不是单独的一列的值了,而是多个列组合的值,例如对于上例中的用户表新建一个联合索引 index(name,age),那么其内部结构如下:

因此,index(name,age)这个联合索引适用于如下 sql 查询:

1
2
3
select * from user where name = 'zhangsan'
select * from user where name = 'zhangsan' and age = 18
select * from user where name = 'zhangsan' and age > 18 and age < 22

但是,这个联合索引并不能用于以下的 sql 查询

1
2
select * from user where age = 18
select * from user where name = 'zhangsan' or age = 18

所以,在一个查询中如果想要使用一个联合索引来加速查询,在条件匹配中必须符合这个联合索引的最左前缀,例如我们创建了一个 index(column1,column2,column3) 的3列联合索引,只要我们在查询中单独用到了第一列column1,或者column1和column2以及column1,column2,column3都能让查询使用这个联合索引来加速查询。

例如以下的 sql 查询,只有前两个 sql 查询会使用到 index(column1,column2,column3) 的联合索引,虽然第三和第四个 sql 查询中用到了索引中包含的列,但是不是索引中的最左前缀,所以无法使用该索引来完成查找。

1
2
3
4
5
select * from table_name where column1 = 'value'
select * from table_name where column1 = 'value' and column2 = 'value'

select * from table_name where column2 = 'value'
select * from table_name where column2 = 'value' and column3 = 'value'

并且在联合索引中,对于第二列或之后的列,可以进行排序,例如对于index(name,age) 这个联合索引,我们可以获取重名的用户,并且按照年龄排序,这时使用联合索引就可以直接获取到已经排序过的数据,因为其本身在叶子节点中就已经排序了,例如下面这个 sql 查询:

1
select * from user where name = 'zhangsan' order by age

覆盖索引

如果查询中仅需要获得在索引中的列,那么可以直接从索引中获得数据,而不用再去查找数据行。

例如以下 sql 查询:

1
select name from user where name LIKE 'zha%'

在这个 sql 查询语句返回的结果中,可以不用去获取数据行的内容,因为在 name 列的辅助索引中已经包含了该列的值,则可以从该辅助索引中直接返回所匹配的关键字即可,不需要在根据主键去聚簇索引中获取数据行,对于联合索引来讲,也是一样的效果。

查询执行计划

MySQL中的 explain命令可以查看sql语句的执行计划,而通过执行计划我们可以了解到这条sql的查询方式、索引的使用情况、需要扫描的数据量、是否需要临时表及排序等操作信息。

我们需要分析执行计划,来进行有必要的优化,在sql语句前加上explain即可查看该sql语句的执行计划。

输出格式

explain select * from db where user = 'test'查询为例,结果如下:

各列含义如下:

列名 含义
id 查询标识符
select_type 查询类型
table 输出行的表
partitions 匹配的分区
type 连接类型
possible_keys 可以选择的索引,但实际选择的索引由key字段决定
key 实际选择的索引
key_len 索引使用的字节数
ref 索引使用的列或常量
rows 预计需要检查的行数
filtered 按条件过滤的数据百分比
Extra 额外信息

查询类型

下表显示了所有查询类型:

查询类型 含义
SIMPLE 简单的select查询,查询中不包含union或子查询
PRIMARY 查询中包含子查询,表示这是最外层查询
UNION union的第二个或之后的查询被标记为UNION
DEPENDENT UNION 依赖外部查询的union
UNION RESULT union的结果。
SUBQUERY 子查询
DEPENDENT SUBQUERY 依赖外部查询的子查询
DERIVED 用于from的子查询
DEPENDENT DERIVED 依赖外部查询的用于from的子查询

连接类型

连接类型type介绍了如何连接表,以下列表从最佳类型到最差类型列出了所有的连接类型:

  • system

    表中只有一条数据,这是连接类型 const 的一个特例。

  • const

    表示通过主键或唯一索引查询,最多只返回一行数据。因为只有一行数据,如果在where列表中,mysql能将该查询转换为一个常量,const 查询速度非常快, 因为它只需要读取一次。

  • eq_ref

    对于每个来自于前面的表的结果,都只能从该表中匹配一行数据,连接的字段为主键或唯一索引。

    在以下官方文档的示例中,可以使用eq_ref连接来处理ref_table表 :

    1
    2
    3
    4
    5
    6
    select * from ref_table,other_table 
    where ref_table.key_column=other_table.column;

    select * from ref_table,other_table
    where ref_table.key_column_part1=other_table.column
    and ref_table.key_column_part2=1;

    ref_table表中的key_column列添加了唯一索引。

  • ref

    对于每个来自于前面的表的结果,可以从该表中根据索引匹配几行数据,连接的字段具有非唯一索引或者使用了最左前缀规则的查询。

    在以下官方文档的示例中,可以使用ref连接来处理ref_table表 :

    1
    2
    3
    4
    5
    6
    7
    8
    select * from ref_table where key_column=expr;

    select * from ref_table,other_table
    where ref_table.key_column=other_table.column;

    select * from ref_table,other_table
    where ref_table.key_column_part1=other_table.column
    AND ref_table.key_column_part2=1;

    ref_table表中的key_column列添加了非唯一索引或使用了最左前缀的规则进行查询。

  • ref_or_null

    该连接类型与ref类型相同,但是对包含NULL值的行进行额外搜索。

    在以下官方文档的示例中,可以使用ref_or_null连接来处理ref_table表 :

    1
    2
    select * from ref_table
    where key_column=expr or key_column is null;
  • index_merge

    该连接类型表示使用了索引合并优化方法。在这种情况下,key输出行中的列包含使用的索引列表,并且key_len包含所用索引的最长关键部分的列表。

  • unique_subquery

    在以下官方文档的示例中,该类型替换了子查询的eq_ref类型

    1
    value in (select primary_key from single_table where some_expr)

    primary_key列必须是主键或唯一索引。

  • index_subquery

    该连接类型与unique_subquery类型相似,但它适用于子查询的查询结果列为非唯一索引的时候。

  • range

    只检索给定范围的行,使用一个索引来选择行。

    在以下官方文档的示例中,可以使用range连接:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    select * from tbl_name
    where key_column = 10;

    select * from tbl_name
    where key_column between 10 and 20;

    select * from tbl_name
    where key_column IN (10,20,30);

    select * from tbl_name
    where key_part1 = 10 and key_part2 in (10,20,30);
  • index

    该联接类型与ALL相同,只是索引树被扫描。这通常比ALL快,因为索引文件通常比数据文件小。

  • ALL

    对于每个表进行全表扫描,可以添加索引来避免这个连接类型。

额外信息

Extra 字段中会显示执行计划中的额外信息。以下列表说明了此列中可能出现的值:

  • Distinct

    MySQL正在寻找不重复的匹配值,因此它在找到第一个匹配行后停止搜索更多的匹配行。

  • Not exists

    MySQL对left join查询进行优化,发现1个匹配left join条件的行后,不再检查更多的行。

  • Range checked for each record (index map: N)

    MySQL没有发现较好的可以使用的索引,但发现如果来自前面的表的列值已知,可能部分索引可以使用。对于上表中的每个行组合,检查是否可以使用range或 index_merge连接类型来检索行。

    这虽然不是很快,但比执行没有索引的连接更快。、

    索引从1开始编号,顺序与表中show index显示的顺序相同。索引映射值 N指示哪些索引是候选。例如,值0x19(二进制11001)表示将考虑索引1,4和5。

  • Using filesort

    表示 MySQL 需额外的排序操作, 不能通过索引顺序达到排序效果。

  • Using index

    表示查询在索引树中就可查找所需数据, 不用扫描表数据文件, 使用覆盖索引。

  • Using index condition

    表示此查询用到了索引,但是需要查询表数据。

  • Using index for group-by

    类似于访问表的Using index方式,Using index for group-by表示MySQL发现了一个索引,可以用来查询GROUP BY或DISTINCT查询的所有列,而不要额外搜索硬盘访问实际的表。

  • Using temporary

    MySQL需要创建一个临时表来容纳结果。