MySql索引

摘要

索引相关

B+Tree(B-Tree变种)

  • 非叶子节点不存储data,只存储索引(冗余),目的是为了放更多的索引,减少树的高度,提高查询效率,非叶子结点由主键值和一个指向下一层的地址的指针组成。

  • 叶子节点包含所有索引字段,聚集索引包含全部字段,非聚集索引包含索引中的字段,叶子结点中由一组键值对和一个指向该层下一页的指针组成,键值对存储的主键值和数据

  • 叶节点之间通过双向链表链接,提高区间访问的性能

  • 在B+树中,一个结点就是一页,MySQL中InnoDB页的大小默认是16k,Innodb的所有数据文件(后缀为 ibd 的文件),其大小始终都是 16384(16k)的整数倍。

1
2
3
4
5
6
mysql> SHOW VARIABLES LIKE 'innodb_page_size';
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+

计算机在存储数据的时候,最小存储单元是扇区,一个扇区的大小是 512 字节,而文件系统(例如 XFS/EXT4)最小单元是块,一个块的大小是 4KB。InnoDB 引擎存储数据的时候,是以页为单位的,每个数据页的大小默认是 16KB,即四个块。

B+Tree可以存放多少条数据,为什么是2000万?

  • 指针在InnoDB中为6字节,设主键的类型是bigint,占8字节。一组就是14字节。
  • 计算出一个非叶子结点可以存储16 * 1024 / 14 = 1170个索引指针。
  • 假设一条数据的大小是1KB,那么一个叶子结点可以存储16条数据。
  • 两层B+树可以存储1170 x 16 = 18720条数据。
  • 三层B+树可以存储1170 x 1170 x 16 = 21902400条数据,约为2000万。
  • 四层B+树可以存储1170 x 1170 x 1170 x 16 = 25625808000条数据,约为256亿。
  • 如不考虑磁盘IO,B+树的查找与其层数(树的高度)和阶数(节点的最大分支数)有关,因为数据都在叶子节点,所以查找数据必须从树的根节点开始,通过2分法定位其所在的分支,一层一层的查找(每层都是2分法定位其所在的分支),直到最后一层的叶子节点定位数据。
  • 在查找不超过3层的B+Tree中的数据时,一次页的查找代表一次IO,所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。
  • 一般不建议单表的数据量超过2000万,因为每查找一个页,都要进行一次IO,而磁盘的速度相比内存而言是非常的慢的,比如常见的7200RPM的硬盘,摇臂转一圈需要60/7200≈8.33ms,换句话说,让磁盘完整的旋转一圈找到所需要的数据需要8.33ms,这比内存常见的100ns慢100000倍左右,这还不包括移动摇臂的时间。所以在这里制约查找速度的不是比较次数,而是IO操作的次数。

B+Tree查找的时间复杂度(比较次数)计算方法

  • B+Tree的查找时间复杂度的计算方法是每层通过2分法查找的次数M * 树的高度H

  • 假设B+Tree中总的数据量为N,阶数为R,则 M = log2R,H = logRN,则M * H = log2R * logRN = log2N

  • 举例,比如有一课B+Tree的总的数据量是65536,最大分支为16,则N=65536,R=16,M = log2R = log216 = 4,H = logRN = log1665536 = 4,则 M * H = log2N = log265536 = 16,即最多查找16次就可以找到对应的数据

  • 注意这里仅是计算内存中查找的比较次数,而没有考虑每次加载数据页到内存的IO成本,而实际上IO成本才是制约mysql查找快慢的关键因素,所以mysql每次IO都会将查询页附近的几个页一并加载到内存,以此减少IO次数

索引分类

  • 聚集索引/聚簇索引/密集索引
    InnoDB中使用了聚集索引,就是将表的主键用来构造一棵B+树,并且将整张表的行记录数据存放在该B+树的叶子节点中。也就是所谓的索引即数据,数据即索引。
    由于聚集索引是利用表的主键构建的,所以每张表只能拥有一个聚集索引。
    聚集索引的叶子节点就是数据页。换句话说,数据页上存放的是完整的每行记录。
    因此聚集索引的一个优点就是:通过聚集索引能获取完整的整行数据。
    另一个优点是:对于主键的排序查找和范围查找速度非常快。
    如果我们没有定义主键呢?MySQL会使用唯一性索引,没有唯一性索引,MySQL也会创建一个隐含列RowID来做主键,然后用这个主键来建立聚集索引。

  • 辅助索引/二级索引/非聚集索引/稀疏索引
    上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用,因为B+树中的数据都是按照主键进行排序的,那如果我们想以别的列作为搜索条件怎么办?
    我们一般会建立多个索引,这些索引被称为辅助索引/二级索引,辅助索引也是一颗B+树。
    对于辅助索引(Secondary Index,也称二级索引、非聚集索引),叶子节点并不包含行记录的全部数据。
    叶子节点除了包含键值以外,每个叶子节点中的索引行中还包含了相应行数据的聚集索引主键,用于回表查询。
    辅助索引的存在并不影响数据在聚集索引中的组织,因此每张表上可以有多个辅助索引,有几个辅助索引就会创建几颗B+树。
    MyISAM存储引擎,不管是主键索引,唯一键索引还是普通索引都是非聚集索引。

当通过辅助索引来寻找数据时,InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键,然后再通过主键索引(聚集索引)来找到一个完整的行记录。这个过程也被称为回表。
也就是根据辅助索引的值查询一条完整的用户记录需要使用到2棵B+树–一次辅助索引,一次聚集索引。

  • 联合索引/复合索引
    前面我们对索引的描述,隐含了一个条件,那就是构建索引的字段只有一个,但实践工作中构建索引的完全可以是多个字段。
    所以,将表上的多个列组合起来进行索引我们称之为联合索引或者复合索引,比如index(a,b)就是将a,b两个列组合起来构成一个索引。
    联合索引只会建立1棵B+树。

  • 自适应哈希索引(Adaptive Hash Index,AHI)
    由mysql自己维护,对于经常被访问的索引,mysql会创建一个hash索引,下次查询这个索引时直接定位到记录的地址,而不需要去B+树中查询。
    AHI默认开启,由innodb_adaptive_hash_index变量控制,默认8个分区,最大设置为512。

1
2
3
4
5
6
7
8
9
10
11
12
mysql> show variables like 'innodb_adaptive_hash_index';
+----------------------------+-------+
| Variable_name | Value |
+----------------------------+-------+
| innodb_adaptive_hash_index | ON |
+----------------------------+-------+
mysql> show variables like 'innodb_adaptive_hash_index_parts';
+----------------------------------+-------+
| Variable_name | Value |
+----------------------------------+-------+
| innodb_adaptive_hash_index_parts | 8 |
+----------------------------------+-------+

通过show engine innodb status\G命令可以查看AHI的使用情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
mysql> show engine innodb status\G

-------------------------------------
INSERT BUFFER AND ADAPTIVE HASH INDEX
-------------------------------------
Ibuf: size 1, free list len 0, seg size 2, 0 merges
merged operations:
insert 0, delete mark 0, delete 0
discarded operations:
insert 0, delete mark 0, delete 0
Hash table size 276707, node heap has 0 buffer(s)
Hash table size 276707, node heap has 0 buffer(s)
Hash table size 276707, node heap has 4 buffer(s)
Hash table size 276707, node heap has 0 buffer(s)
Hash table size 276707, node heap has 0 buffer(s)
Hash table size 276707, node heap has 0 buffer(s)
Hash table size 276707, node heap has 1 buffer(s)
Hash table size 276707, node heap has 1 buffer(s)
0.00 hash searches/s, 0.00 non-hash searches/s
  • 全文检索之倒排索引(FULLTEXT)
    数据类型为 char、varchar、text 及其系列才可以建全文索引。
    每张表只能有一个全文检索的索引
    不支持没有单词界定符(delimiter)的语言,如中文、日语、韩语等。
    由于mysql的全文索引功能很弱,这里不做详细介绍,推荐使用ES等专业的搜索引擎。

MySQL有哪些索引类型?

  • 从数据结构角度可分为B+树索引、哈希索引、以及FULLTEXT索引(现在MyISAM和InnoDB 引擎都支持了)和R-Tree索引(用于对GIS数据类型创建SPATIAL索引);
  • 从物理存储角度可分为聚集索引(clustered index)、非聚集索引(non-clustered index);
  • 从逻辑角度可分为主键索引、普通索引,或者单列索引、多列索引、唯一索引、非唯一索引等等。

覆盖索引/索引覆盖

  • InnoDB存储引擎支持覆盖索引(covering index,或称索引覆盖),即从辅助索引中就可以得到查询的记录,而不需要查询聚集索引中的记录。

  • 使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息,故其大小要远小于聚集索引,因此可以减少大量的IO操作。

  • 覆盖索引可以视为索引优化的一种方式,而并不是索引类型的一种。

  • 除了覆盖索引这个概念外,在索引优化的范围内,还有前缀索引、三星索引等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
> show create table employees\G
***************************[ 1. row ]***************************
Table | employees
Create Table | CREATE TABLE `employees` (
`id` int NOT NULL AUTO_INCREMENT,
`name` varchar(24) NOT NULL DEFAULT '' COMMENT '姓名',
`age` int NOT NULL DEFAULT '0' COMMENT '年龄',
`position` varchar(20) NOT NULL DEFAULT '' COMMENT '职位',
`hire_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '入职时间',
PRIMARY KEY (`id`),
KEY `idx_name_age_position` (`name`,`age`,`position`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8mb3 COMMENT='员工记录表'

> EXPLAIN SELECT * FROM employees WHERE name > 'LiLei' AND age = 22 AND position ='manager';
+----+-------------+-----------+------------+------+-----------------------+--------+---------+--------+-------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-----------+------------+------+-----------------------+--------+---------+--------+-------+----------+-------------+
| 1 | SIMPLE | employees | <null> | ALL | idx_name_age_position | <null> | <null> | <null> | 92796 | 0.5 | Using where |
+----+-------------+-----------+------------+------+-----------------------+--------+---------+--------+-------+----------+-------------+

> EXPLAIN SELECT name,age,position FROM employees WHERE name > 'LiLei' AND age = 22 AND position ='manager';
+----+-------------+-----------+------------+-------+-----------------------+-----------------------+---------+--------+-------+----------+--------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-----------+------------+-------+-----------------------+-----------------------+---------+--------+-------+----------+--------------------------+
| 1 | SIMPLE | employees | <null> | range | idx_name_age_position | idx_name_age_position | 74 | <null> | 46398 | 1.0 | Using where; Using index |
+----+-------------+-----------+------------+-------+-----------------------+-----------------------+---------+--------+-------+----------+--------------------------+

前缀索引

如果索引的字段类型很长,如varchar(255),此时创建的索引就会非常大,而且维护起来也非常慢,此时建议使用前缀索引,就是只对该字段的前面一些字符进行索引。
阿里的Java编程规范中也提到,在varchar上建立索引时,必须指定索引长度,没必要对全字段建立索引,建议索引的长度不超过20。
可以使用select count(distinct left(列名, 索引长度))/count(*) from tableName的区分度来确定,一般大于90%即可。

三星索引

  • 一星(缩小查询范围): 索引将相关的记录放到一起则获得一星,即索引的扫描范围越小越好;

  • 二星(排序): 如果索引中的数据顺序和查找中的排列顺序一致则获得二星,即当查询需要排序,group by、 order by,查询所需的顺序与索引是一致的(索引本身是有序的);

  • 三星(覆盖索引): 如果索引中的列包含了查询中需要的全部列则获得三星,即索引中所包含了这个查询所需的所有列(包括 where 子句 和 select 子句中所需的列,也就是覆盖索引)。

注意

  • 一个索引就是一个B+树,索引让我们的查询可以快速定位和扫描到我们需要的数据记录上,加快查询的速度。

  • 一个select查询语句在执行过程中一般最多能使用一个二级索引来加快查询,即使在where条件中用了多个二级索引。

索引的代价

  • 空间上的代价
    这个是显而易见的,每建立一个索引都要为它建立一棵B+树,每一棵B+树的每一个节点都是一个数据页,一个页默认会占用16KB的存储空间,一棵很大的B+树由许多数据页组成会占据很多的存储空间。

  • 时间上的代价
    每次对表中的数据进行增、删、改操作时,都需要去修改各个B+树索引。B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。
    不论是叶子节点中的记录,还是非叶子内节点中的记录都是按照索引列的值从小到大的顺序而形成了一个单向链表。
    而增、删、改操作可能会对节点和记录的排序造成破坏,所以存储引擎需要额外的时间进行一些记录移位,页面分裂、页面回收的操作来维护好节点和记录的排序。
    如果我们建了许多索引,每个索引对应的B+树都要进行相关的维护操作,这必然会对性能造成影响。

所以,索引虽然可以加快我们的查询效率,但也不是创建的越多越好,一般来说,一张表不要超过7个索引为宜。

索引的创建与删除

  • 查看索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
mysql> desc actor;
+-------------+-------------+------+-----+---------+-------+
| Field | Type | Null | Key | Default | Extra |
+-------------+-------------+------+-----+---------+-------+
| id | int | NO | PRI | NULL | |
| name | varchar(45) | YES | | NULL | |
| update_time | datetime | YES | MUL | NULL | |
+-------------+-------------+------+-----+---------+-------+

mysql> show index from actor;
+-------+------------+------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-------+------------+------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| actor | 0 | PRIMARY | 1 | id | A | 2 | <null> | <null> | | BTREE | | | YES | <null> |
| actor | 0 | unique_name_time_order | 1 | name | D | 3 | 15 | <null> | YES | BTREE | | | YES | <null> |
| actor | 0 | unique_name_time_order | 2 | update_time | A | 3 | <null> | <null> | YES | BTREE | | | YES | <null> |
| actor | 1 | index_update_time | 1 | update_time | A | 1 | <null> | <null> | YES | BTREE | | | YES | <null> |
| actor | 1 | index_name | 1 | name | A | 3 | 15 | <null> | YES | BTREE | | | YES | <null> |
| actor | 1 | index_name_desc | 1 | name | D | 3 | 15 | <null> | YES | BTREE | | | YES | <null> |
+-------+------------+------------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
参数说明:
Table: 表名称
Non_unique: 是否为唯一索引,0表示唯一索引,1表示非唯一索引
Key_name: 索引名称
Seq_in_index: 联合索引中的字段顺序,从1开始计算
Column_name: 字段名称
Collation: 表示索引是升序还是降序,默认创建索引是升序A,降序为D
  • 已有表索引维护

创建索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 方式1
create index index_name on actor (name(15));
# 创建降序索引,默认升序
create index index_name_desc on actor (name(15) desc);
create unique index unique_name on actor (name(15));
create unique index unique_name_time on actor (name(15),update_time);
create unique index unique_name_time_order on actor (name(15) desc,update_time asc);

# 方式2
alter table actor add index index_name(name(15));
alter table actor add index index_name(name(15) desc);
alter table actor add unique index unique_name(name(15));
alter table actor add unique index unique_name_time(name(15),update_time);
alter table actor add unique index unique_name_time_order(name(15) desc,update_time asc);

删除索引

1
2
3
4
5
6
7
8
9
10
11
# 方式1
drop index index_name on actor;
drop index unique_name on actor;
drop index unique_name_time on actor;

# 方式2
alter table actor drop index index_name;
alter table actor drop index unique_name;
alter table actor drop index unique_name_time;
# 同时删除多个索引
alter table actor drop index index1,drop index index2,drop index index3;

函数索引

  • mysql8.0.13及以后的版本开始支持函数式索引,即创建索引的时候可以使用mysql提供的函数(不支持自定义函数)

1
2
3
4
5
6
7
8
9
10
# 注意,创建函数索引时,要在外层有一对括号,表示表达式
alter table actor add index index1((upper(name)));
# 前缀
alter table actor add index index1((upper(left(name,15))));
# 排序
alter table actor add index index2((upper(name)) desc);
# 联合索引,函数索引+普通索引
alter table actor add index index3((upper(name)) desc,update_time asc);
# 联合索引,函数索引+函数索引
alter table actor add index index4((upper(name)) desc,(year(update_time)) asc);

注意查询时也要使用函数才能使用索引

1
2
3
4
5
6
explain select * from actor where upper(name) = 'A';
+----+-------------+-------+------------+------+---------------+--------+---------+-------+------+----------+--------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+--------+---------+-------+------+----------+--------+
| 1 | SIMPLE | actor | <null> | ref | index3 | index3 | 138 | const | 1 | 100.0 | <null> |
+----+-------------+-------+------------+------+---------------+--------+---------+-------+------+----------+--------+

函数索引的限制条件

  • 函数索引实际上是作为一个隐藏的虚拟列实现的,因此其很多限制与虚拟列相同,如下:
  • 函数索引的字段数量受到表的字段总数限制
  • 函数索引能够使用的函数与虚拟列上能够使用的函数相同
  • 子查询,参数,变量,存储过程,用户定义的函数不允许在函数索引上使用
  • 虚拟列本身不需要存储,函数索引和其他索引一样需要占用存储空间
  • 函数索引可以使用 UNIQUE 标识,但是主键不能使用函数索引,主键要求被存储,但是函数索引由于其使用的虚拟列不能被存储,因此主键不能使用函数索引
  • 如果表中没有主键,那么 InnoDB 将会使其非空的唯一索引作为主键,因此该唯一索引不能定义为函数索引
  • 函数索引不允许在外键中使用
  • 空间索引和全文索引不能定义为函数索引
  • 对于非函数的索引,如果创建相同的索引,将会有一个告警信息,而函数索引则不会
  • 如果一个字段被用于函数索引,那么删除该字段前,需要先删除该函数索引,否则删除该字段会报错
  • 函数索引实际上就是mysql帮我们在表上创建了一个隐藏的虚拟列,我们也可以通过自建虚拟列,然后在该虚拟列上创建普通索引来实现相同的效果

1
2
3
4
5
6
7
8
9
10
11
12
ALTER TABLE actor ADD COLUMN upper_name varchar(15) GENERATED ALWAYS AS ((upper(left(name,15)))) VIRTUAL;
alter table actor add index virtual_upper(upper_name desc);
explain select * from actor where upper_name = 'A';
+----+-------------+-------+------------+------+---------------+---------------+---------+-------+------+----------+--------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+---------------+---------+-------+------+----------+--------+
| 1 | SIMPLE | actor | <null> | ref | virtual_upper | virtual_upper | 48 | const | 1 | 100.0 | <null> |
+----+-------------+-------+------------+------+---------------+---------------+---------+-------+------+----------+--------+

# 删除虚拟列前要先删除其对应的索引
ALTER TABLE actor DROP INDEX virtual_upper;
ALTER TABLE actor DROP COLUMN upper_name;

索引条件下推

什么是索引条件下推,这里举例说明:
SELECT * FROM s1 WHERE order_no > 'z' AND order_no LIKE '%a';
其中的order_no > 'z'可以使用到索引,但是 order_no LIKE '%a'却无法使用到索引

  • 在MySQL5.6之前的版本中,是按照下边步骤来执行这个查询的:
    1、先根据 order_no> 'z'这个条件,从二级索引 idx_order_no 中获取到对应的二级索引记录。
    2、根据上一步骤得到的二级索引记录中的主键值进行回表(因为是 select *),找到完整的用户记录再检测该记录是否符合 key1 LIKE '%a'这个条件,将符合条件的记录加入到最后的结果集。

  • MySQL5.6之后的版本开始支持索引下推,其执行步骤如下:
    1、先根据 order_no> 'z'这个条件,定位到二级索引 idx_order_no 中对应的二级索引记录。
    2、对于指定的二级索引记录,先不着急回表,而是先检测一下该记录是否满足 order_no LIKE '%a'这个条件,如果这个条件不满足,则该二级索引记录压根儿就没必要回表。
    3、对于满足 order_no LIKE '%a'这个条件的二级索引记录执行回表操作。

  • 回表操作其实是一个随机 IO,比较耗时,所以上述修改可以省去很多回表操作的成本。这个改进称之为索引条件下推(英文名:ICP ,Index Condition Pushdown)。

  • 如果在查询语句的执行过程中将要使用索引条件下推这个特性,在执行计划的 Extra 列中将会显示Using index condition

索引合并

过MySQL在一般情况下执行一个查询时最多只会用到单个二级索引,但存在有特殊情况下也可能在一个查询中使用到多个二级索引,MySQL中这种使用到多个索引来完成一次查询的执行方法称之为:索引合并/index merge。

  • 索引合并算法有如下三种:

    • 1.Intersection合并: 将从多个二级索引中查询到的结果取交集,某些特定的情况下才可能会使用到Intersection索引合并

      • 情况一:等值匹配
      • 情况二:主键列可以是范围匹配
    • 2.Union合并: 使用不同索引的搜索条件之间使用OR连接起来的情况,某些特定的情况下才可能会使用到Union索引合并

      • 情况一:等值匹配
      • 情况二:主键列可以是范围匹配
      • 情况三:使用Intersection索引合并的搜索条件

      就是搜索条件的某些部分使用Intersection索引合并的方式得到的主键集合和其他方式得到的主键集合取交集,比方说这个查询: SELECT * FROM order_exp WHERE insert_time = ‘a’ AND order_status = ‘b’ AND expire_time = ‘c’ OR (order_no = ‘a’ AND expire_time = ‘b’);

    • 3.Sort-Union合并: 先按照二级索引记录的主键值进行排序,之后按照Union索引合并方式执行的方式称之为Sort-Union索引合并,很显然,这种Sort-Union索引合并比单纯的Union索引合并多了一步对二级索引记录的主键值排序的过程

索引设计原则

  • 代码先行,索引后上

    • 一般应该等到主体业务功能开发完毕,把涉及到该表相关sql都要拿出来分析之后再建立索引
  • 联合索引尽量覆盖条件

    • 比如可以设计一个或者两三个联合索引(尽量少建单值索引),让每一个联合索引都尽量去包含sql语句里的 where、order by、group by的字段,还要确保这些联合索引的字段顺序尽量满足sql查询的最左前缀原则
  • 不要在小基数字段上建立索引

    • 比如性别字段,其值不是男就是女,那么该字段的基数就是2,对这种小基数字段建立索引的话,还不如全表扫描
  • 长字符串可以采用前缀索引

    • 但是要注意,order bygroup by时没办法使用前缀索引
  • whereorder by冲突时优先where

    • where可以缩小查询范围,会使排序的成本会小很多
  • 基于慢sql查询做优化

    • 线上系统一定要开启慢sql,然后定期对慢sql就行索引优化