MySQL中的索引 - Sanarous的博客

MySQL中的索引

索引概述

MySQL 官方对索引的定义为:索引(Index)是帮助 MySQL 高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

索引用于快速找出在某个列中有一特定值的行,不使用索引,MySQL 必须从第一条记录开始读完整个表,直到找出相关的行,表越大,查询数据所花费的时间就越多,如果表中查询的列有一个索引,MySQL 能够快速到达一个位置去搜索数据文件,而不必查看所有数据,那么将会节省很大一部分时间。

我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为 O(n) 的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

索引是在存储引擎层实现的,而不是在服务器层实现的,所以不同存储引擎具有不同的索引类型和实现。由于 MySQL 默认存储引擎为 InnoDB,因此下文只讨论 InnoDB 存储引擎下索引的实现。索引是应用程序设计和开发中的一个重要方面,若索引太多,应用程序的性能可能会受到影响,而索引太少,对查询性能又会产生影响。要找到一个合适的平衡点,这对应用程序性能至关重要。

InnoDB存储引擎索引概述

InnoDB 存储引擎支持以下几种常见的索引:

  • B+ 树索引
  • 全文索引
  • 哈希索引

其中,InnoDB 存储引擎支持的哈希索引是自适应的, InnoDB 存储引擎会根据表的使用情况自动生成哈希索引,不能人为干预是否在一张表中生成哈希索引。
而 B+ 树索引就是传统意义上的索引,这是目前关系型数据库系统中查找最为常用和最为有效的索引,B+ 树索引的构造类似于二叉树,根据键值(key value)快速找到数据。

数据结构与算法

在介绍 B+ 树原理之前,有必要先介绍与其相近的二叉树相关知识,以便于更好的理解为什么数据库要选择 B+ 树作为索引的数据结构的原理。

二叉查找树

二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质:

  1. 任意节点左子树不为空,则左子树的值均小于根节点的值;
  2. 任意节点右子树不为空,则右子树的值均大于于根节点的值;
  3. 任意节点的左右子树也分别是二叉查找树;
  4. 没有键值相等的节点;

上图为一个普通的二叉查找树,按照中序遍历的方式可以从小到大的顺序排序输出:2、3、5、6、7、8。

对上述二叉树进行查找,如查键值为 5 的记录,先找到根,其键值是 6,6 大于 5,因此查找 6 的左子树,找到 3;而 5 大于 3,再找其右子树;一共找了 3 次。如果按 2、3、5、6、7、8 的顺序来找同样需求 3 次。用同样的方法在查找键值为 8 的这个记录,这次用了 3 次查找,而顺序查找需要 6次。计算平均查找次数得:顺序查找的平均查找次数为(1+2+3+4+5+6)/ 6 = 3.3次,二叉查找树的平均查找次数为(3+3+3+2+2+1)/ 6= 2.3次。二叉查找树的平均查找速度比顺序查找来得更快。

二叉查找树可以任意构造,同样是上述数字,也可以构造为如下:

而上图的平均查找次数为(1+2+3+4+5+5) / 6 = 3.16次,和顺序查找差不多,显然这样构造的查询效率就比较低了。因此若想最大性能的构造一颗二叉查找树,需要这个二叉树是平衡的,也就是必须是平衡二叉树(AVL 树)。

AVL树

AVL 树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过 1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过 1)。不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道 AVL 树适合用于插入删除次数比较少,但查找多的情况。

如下是插入新值 9 后平衡二叉树的变化:

如下是需要多次旋转的 AVL 树:

由上可知,由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么 AVL 还是较优于红黑树。

红黑树

一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是 red 或 black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是若平衡,可以推出,相同的节点情况下,AVL 树的高度低于红黑树),相对于要求严格的 AVL 树来说,它的旋转次数变少,所以对于搜索、插入、删除操作多的情况下,我们就用红黑树。

红黑树具有以下性质:

  • 每个节点非红即黑;
  • 根节点是黑的;
  • 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的;
  • 如果一个节点是红的,那么它的两儿子都是黑的;
  • 对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;
  • 每条路径都包含相同的黑节点;

红黑树构造如下:

其应用较为广泛:

  1. 广泛用于 C++ 的 STL 中,Map 和 Set 都是用红黑树实现的;
  2. 著名的 Linux 进程调度 Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间;
  3. IO 多路复用 epoll 的实现采用红黑树组织管理 sockfd,以支持快速的增删改查;
  4. Nginx 中用红黑树管理 timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器;
  5. Java 中 TreeMap、HashMap、ConcurrentHashMap 的实现;

B/B+ 树

说了上述的三种树:二叉查找树、AVL和红黑树,似乎我们还没有摸到 MySQL 为什么要使用 B+ 树作为索引的实现,不要急,接下来我们就先探讨一下什么是 B 树。

我们在 MySQL 中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过 B 树进行优化,提高磁盘读取时定位的效率。

为什么 B 类树可以进行优化呢?我们可以根据 B 类树的特点,构造一个多阶的 B 类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的 I/O 操作也少一些,而且 B 类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

总的来说,B/B+ 树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B 树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,一颗 B/B+ 树的高度远远小于红黑树的高度(在下面 B/B+ 树的性能分析中会提到)。B/B+ 树上操作的时间通常由存取磁盘的时间和 CPU 计算时间这两部分构成,而 CPU 的速度非常快,所以 B 树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下 B 树的高度越小,磁盘 I/O 所花的时间越少。

B树

B 树的性质:

  1. 定义任意非叶子结点最多只有M个儿子,且M>2;
  2. 根结点的儿子数为[2, M];
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M];
  4. 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1;
  6. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
  7. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
  8. 所有叶子结点位于同一层;

这里只是一个简单的 B 树,在实际中 B 树节点中关键字很多的,上面的图中比如 35 节点,35 代表一个 key (索引),而小黑块代表的是这个 key 所指向的内容在内存中实际的存储位置,是一个指针。

B+树

B+ 树是应文件系统所需而产生的一种 B 树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保存数据)非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中,这不就是文件系统文件的查找吗?

我们就举个文件查找的例子:有 3 个文件夹a、b、c, a包含b,b包含c,一个文件 yang.c,a、b、c就是索引(存储在非叶子节点), a、b、c只是要找到的 yang.c 的key,而实际的数据 yang.c 存储在叶子节点上。

所有的非叶子节点都可以看成索引部分!

B+ 树有以下性质:

  1. 非叶子节点的子树指针与关键字个数相同;
  2. 非叶子节点的子树指针 p[i] ,指向关键字值属于 [k[i],k[i+1]] 的子树。(B 树是开区间,也就是说B树不允许关键字重复,B+ 树允许重复);
  3. 为所有叶子节点增加一个链指针;
  4. 所有关键字都在叶子节点出现(稠密索引)。 (且链表中的关键字恰好是有序的);
  5. 非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层;
  6. 更适合于文件系统;

非叶子节点(比如5,28,65)只是一个key(索引),实际的数据存在叶子节点上(5,8,9)才是真正的数据或指向真实数据的指针。

为什么说B+树比B树更适合数据库索引?

  1. B+ 树的磁盘读写代价更低:B+ 树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对 I/O 读写次数就降低了。

  2. B+ 树的查询效率更加稳定:由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

  3. 由于 B+ 树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是 B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以 B+ 树更加适合在区间查询的情况,所以通常 B+ 树用于数据库索引。

简而言之,数据库索引采用 B+ 树的主要原因是:B树在提高了 I/O 性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+ 树应用而生。B+ 树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而 B 树不支持这样的操作或者说效率太低。

索引操作

创建索引

以下使用的 MySQL 数据库为 5.7.26 版本,不同版本显示结果略有不同。

创建表的时候创建索引

格式:

1
CREATE TABLE 表名[字段名 数据类型]  [UNIQUE|FULLTEXT|SPATIAL|...] [INDEX|KEY] [索引名字] (字段名[length])   [ASC|DESC]

对应意思如下:

1
普通创建表语句  设置什么样的索引(唯一、全文等)  索引关键字  索引名字 对哪个字段设置索引  对索引进行排序
创建普通索引
1
2
3
4
5
6
7
8
9
10
11
CREATE TABLE book
(
bookid INT NOT NULL,
bookname VARCHAR(255) NOT NULL,
authors VARCHAR(255) NULL,
info VARCHAR(255) NULL,
comment VARCHAR(255) NULL,
year_publication YEAR NOT NULL,

INDEX(year_publication)
);

或者使用如下命令:

1
2
3
4
5
6
7
8
9
10
11
CREATE TABLE book
(
bookid INT NOT NULL,
bookname VARCHAR(255) NOT NULL,
authors VARCHAR(255) NULL,
info VARCHAR(255) NULL,
comment VARCHAR(255) NULL,
year_publication YEAR NOT NULL,

KEY(year_publication)
);

创建之后,我们使用Explain查看创建的索引:

1
EXPLAIN SELECT * FROM book WHERE year_publication = 2019\G;

其输出结果为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mysql> EXPLAIN SELECT * FROM book where year_publication = 2019\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: book
partitions: NULL
type: ref
possible_keys: year_publication
key: year_publication
key_len: 1
ref: const
rows: 1
filtered: 100.00
Extra: Using index condition
1 row in set, 1 warning (0.01 sec)

其中每个符号代表的意义如下:

  1. id:SELECT 识别符。这是 SELECT 的查询序列号,也就是一条语句中,该 select 是第几次出现。在次语句中,select 就只有一个,所以是 1。
  2. select_type:所使用的 SELECT 查询类型,SIMPLE 表示为简单的 SELECT,不实用 UNION 或子查询,就为简单的 SELECT。也就是说在该 SELECT 查询时会使用索引。其他取值,PRIMARY:最外面的 SELECT。拥有子查询时,就会出现两个以上的 SELECT。UNION:union (两张表连接)中的第二个或后面的 select 语句 SUBQUERY:在子查询中,第二 SELECT。

  3. table:数据表的名字。他们按被读取的先后顺序排列,这里因为只查询一张表,所以只显示 book。

  4. type:指定本数据表和其他数据表之间的关联关系,该表中所有符合检索值的记录都会被取出来和从上一个表中取出来的记录作联合。ref 用于连接程序使用键的最左前缀或者是该键不是 primary key 或 unique索引(换句话说,就是连接程序无法根据键值只取得一条记录)的情况。当根据键值只查询到少数几条匹配的记录时,这就是一个不错的连接类型。(注意,个人这里不是很理解,百度了很多资料,全是大白话,等以后用到了这类信息时,在回过头来补充,这里不懂对后面的影响不大。)可能的取值有 system、const、eq_ref、index和All。
  5. possible_keys:MySQL 在搜索数据记录时可以选用的各个索引,该表中就只有一个索引 year_publication。
  6. key:实际选用的索引
  7. key_len:显示了 MySQL 使用索引的长度(也就是使用的索引个数),当 key 字段的值为 null 时,索引的长度就是 null。注意,key_len 的值可以告诉你在联合索引中 mysql 会真正使用了哪些索引。这里就使用了 1 个索引,所以为 1。
  8. ref:给出关联关系中另一个数据表中数据列的名字。常量(const),这里使用的是 1990,就是常量。
  9. rows:MySQL 在执行这个查询时预计会从这个数据表里读出的数据行的个数。
  10. extra:提供了与关联操作有关的信息,没有则什么都不写。   

上面的一大堆东西能看懂多少看多少,我们最主要的是看 possible_keys 和 key 这两个属性,上面显示了 key 为year_publication。说明使用了索引。

创建唯一索引
1
2
3
4
5
6
CREATE TABLE t1
(
id NOT NULL,
name CHAR(30) NOT NULL,
UNIQUE INDEX UniqIdx(id)
);

解释:对 id 字段使用了索引,并且索引名字为 UniqIdx。

我们使用命令SHOW CREATE TABLE t1\G查看建表语句:

1
2
3
4
5
6
7
8
9
10
mysql> SHOW CREATE TABLE t1\G
*************************** 1. row ***************************
Table: t1
Create Table: CREATE TABLE `t1` (
`id` int(11) NOT NULL,
`name` char(30) NOT NULL,
UNIQUE KEY `UniqIdx` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1

1 row in set (0.00 sec)

要查看其中查询时使用的索引,必须先往表中插入数据,然后在查询数据,不然查找一个没有的id值,是不会使用索引的。

1
2
INSERT INTO t1 VALUES(1,'xxx');
EXPLAIN SELECT * FROM t1 WHERE id = 1\G;

上述 EXPLAIN 结果为:

可以看到,通过id查询时,会使用唯一索引。

创建主键索引
1
2
3
4
5
6
7
8
9
CREATE TABLE t2
(
id INT NOT NULL,
name CHAR(10),
PRIMARY KEY(id)
);  

INSERT INTO t2 VALUES(1,'xxx');
EXPLAIN SELECT * FROM t2 WHERE id = 1\G;

分析后结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mysql> EXPLAIN SELECT * FROM t2 where id=1\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: t2
partitions: NULL
type: const
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: const
rows: 1
filtered: 100.00
Extra: NULL
1 row in set, 1 warning (0.00 sec)

通过这个主键索引,我们就应该反应过来,其实我们以前声明的主键约束,就是一个主键索引,只是之前我们没学过,不知道而已。

创建单列索引

这个其实就不用在说了,前面几个就是单列索引。

创建组合索引

组合索引就是在多个字段上创建一个索引。

创建一个表 t3,在表中的 id、name 和 age 字段上建立组合索引:

1
2
3
4
5
6
7
8
9
10
CREATE TABLE t3
(
id INT NOT NULL,
name CHAR(30) NOT NULL,
age INT NOT NULL,
info VARCHAR(255),
INDEX MultiIdx(id,name,age)
);

SHOW CREATE TABLE t3\G;

结果如下:

1
2
3
4
5
6
7
8
9
10
11
mysql> show create table t3\G
*************************** 1. row ***************************
Table: t3
Create Table: CREATE TABLE `t3` (
`id` int(11) NOT NULL,
`name` char(30) NOT NULL,
`age` int(11) NOT NULL,
`info` varchar(255) DEFAULT NULL,
KEY `MultiIdx` (`id`,`name`,`age`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

解释最左前缀:组合索引就是遵从了最左前缀,利用索引中最左边的列集来匹配行,这样的列集称为最左前缀,不明白没关系,举几个例子就明白了,例如,这里由id、name 和 age 3 个字段构成的索引,索引行中就按id/name/age 的顺序存放,索引可以索引下面字段组合(id,name,age)、(id,name)或者(id)。如果要查询的字段不构成索引最左面的前缀,那么就不会是用索引,比如,age 或者(name,age)组合就不会使用索引查询。

在 t3 表中,查询 id 和 name 字段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mysql> EXPLAIN SELECT * FROM t3 where id = 1 AND name = "zuoxiang"\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: t3
partitions: NULL
type: ref
possible_keys: MultiIdx //使用了组合索引
key: MultiIdx //使用了组合索引
key_len: 34
ref: const,const
rows: 1
filtered: 100.00
Extra: NULL
1 row in set, 1 warning (0.00 sec)

而 在t3表中,查询(age,name)字段,这样就不会使用索引查询。来看看结果 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mysql> EXPLAIN SELECT * FROM t3 where age = 22 AND name = "zuoxiang"\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: t3
partitions: NULL
type: ALL
possible_keys: NULL //没有找到索引
key: NULL //没有使用索引
key_len: NULL
ref: NULL
rows: 1
filtered: 100.00
Extra: Using where
1 row in set, 1 warning (0.00 sec)
创建全文索引

全文索引可以用于全文搜索,但只有 MyISAM 存储引擎支持 FULLTEXT 索引,并且只为 CHAR、VARCHAR 和TEXT 列服务。索引总是对整个列进行,不支持前缀索引。

1
2
3
4
5
6
7
8
9
10
CREATE TABLE t4
(
id INT NOT NULL,
name CHAR(30) NOT NULL,
age INT NOT NULL,
info VARCHAR(255),
FULLTEXT INDEX FullTxtIdx(info)
)ENGINE=MyISAM;

SHOW CREATE TABLE t4\G;

结果如下:

1
2
3
4
5
6
7
8
9
10
11
mysql> SHOW CREATE TABLE t4\G;
*************************** 1. row ***************************
Table: t4
Create Table: CREATE TABLE `t4` (
`id` int(11) NOT NULL,
`name` char(30) NOT NULL,
`age` int(11) NOT NULL,
`info` varchar(255) DEFAULT NULL,
FULLTEXT KEY `FullTxtidx` (`info`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

使用一下什么叫做全文搜索。就是在很多文字中,通过关键字就能够找到该记录。

1
INSERT INTO t4 VALUES(8,'AAA',3,'text is so good,hei,my name is bob'),(9,'BBB',4,'my name is gorlr');

分析一下:

注意:在使用全文搜索时,需要借助 MATCH 函数,并且其全文搜索的限制比较多,比如只能通过 MyISAM 引擎,比如只能在 CHAR , VARCHAR , TEXT 上设置全文索引。比如搜索的关键字默认至少要 4 个字符,比如搜索的关键字太短就会被忽略掉。

创建空间索引

空间索引也必须使用 MyISAM 引擎, 并且空间类型的字段必须为非空。 这个空间索引具体能干嘛我也不知道,可能跟游戏开发有关,可能跟别的东西有关,等遇到了自然就知道了,现在只要求能够创建出来。

1
2
3
4
5
CREATE TABLE t5
(
  g GEOMETRY NOT NULL,
  SPATIAL INDEX spatIdx(g)
) ENGINE = MyISAM;
在已经存在的表上创建索引

格式:

1
格式:ALTER TABLE 表名 ADD[UNIQUE|FULLTEXT|SPATIAL] [INDEX|KEY] [索引名] (索引字段名)[ASC|DESC]

有了上面的基础,这里就不用过多陈述了。

为表添加索引

就拿上面的book表来说。本来已经有了一个year_publication,现在我们为该表在加一个普通索引

1
ALTER TABLE book ADD INDEX BkNameIdx(bookname(30));

看一下 book 表的索引:

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
28
29
30
mysql> show index from book\G;
*************************** 1. row ***************************
Table: book
Non_unique: 1
Key_name: year_publication
Seq_in_index: 1
Column_name: year_publication
Collation: A
Cardinality: 0
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
*************************** 2. row ***************************
Table: book
Non_unique: 1
Key_name: BkNameIdx
Seq_in_index: 1
Column_name: bookname
Collation: A
Cardinality: 0
Sub_part: 30
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
2 rows in set (0.00 sec)

看输出结果,就能知道,添加索引成功了。

这里只是拿普通索引做个例子,添加其他索引也是一样的。依葫芦画瓢而已。这里就不一一做讲解了。

使用CREATE INDEX创建索引

格式:

1
格式:CREATE [UNIQUE|FULLTEXT|SPATIAL] [INDEX|KEY] 索引名称 ON 表名(创建索引的字段名[length])[ASC|DESC]

解释:其实就是换汤不换药,格式改变了一下而已,做的事情跟上面完全一样,做一个例子:在为 book 表增加一个普通索引,字段为 authors。

1
2
3
CREATE INDEX BkBookNameIdx ON book(bookname);

SHOW INDEX FROM book\G;  //查看book表中的索引

结果分析:

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
28
29
30
mysql> SHOW INDEX FROM book\G;
*************************** 1. row ***************************
Table: book
Non_unique: 1
Key_name: year_publication
Seq_in_index: 1
Column_name: year_publication
Collation: A
Cardinality: 0
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
*************************** 2. row ***************************
Table: book
Non_unique: 1
Key_name: BkBookNameIdx
Seq_in_index: 1
Column_name: bookname
Collation: A
Cardinality: 0
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
2 rows in set (0.00 sec)

删除索引

ALTER TABLE 表名 DROP INDEX 索引名。

很简单的语句,现在通过一个例子来看看,还是对book表进行操作,删除我们刚才为其添加的索引。

删除 book 表中的名称为 BkBookNameIdx 的索引。

1
2
3
ALTER TABLE book DROP INDEX BkBookNameIdx;

SHOW INDEX FROM book\G;  //在查看book表中的索引,就会发现BkBookNameIdx这个索引已经不在了
DROP INDEX 索引名 ON 表名;

删除book表中名为BkNameIdx的索引 。

1
2
3
DROP INDEX BkNameIdx ON book;

SHOW INDEX FROM book\G;

索引使用策略及优化

MySQL的优化主要分为结构优化(Scheme optimization)和查询优化(Query optimization)。

示例数据库

为了讨论索引策略,需要一个数据量不算小的数据库作为示例。本文选用MySQL官方文档中提供的示例数据库之一:employees。这个数据库关系复杂度适中,且数据量较大。下图是这个数据库的E-R关系图(引用自MySQL官方手册):

MySQL官方文档中关于此数据库的页面为http://dev.mysql.com/doc/employee/en/employee.html。里面详细介绍了此数据库,并提供了下载地址和导入方法,如果有兴趣导入此数据库到自己的MySQL可以参考文中内容。

最左前缀原理与相关优化

高效使用索引的首要条件是知道什么样的查询会使用到索引,这个问题和 B+Tree 中的“最左前缀原理”有关,下面通过例子说明最左前缀原理。

这里先说一下联合索引的概念。在上文中,我们都是假设索引只引用了单个的列,实际上,MySQL 中的索引可以以一定顺序引用多个列,这种索引叫做联合索引,一般的,一个联合索引是一个有序元组<a1, a2, …, an>,其中各个元素均为数据表的一列,实际上要严格定义索引需要用到关系代数,但是这里我不想讨论太多关系代数的话题,因为那样会显得很枯燥,所以这里就不再做严格定义。另外,单列索引可以看成联合索引元素数为1的特例。

以 employees.titles 表为例,下面先查看其上都有哪些索引:

1
2
3
4
5
6
7
8
9
SHOW INDEX FROM employees.titles;
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Null | Index_type |
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+
| titles | 0 | PRIMARY | 1 | emp_no | A | NULL | | BTREE |
| titles | 0 | PRIMARY | 2 | title | A | NULL | | BTREE |
| titles | 0 | PRIMARY | 3 | from_date | A | 443308 | | BTREE |
| titles | 1 | emp_no | 1 | emp_no | A | 443308 | | BTREE |
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+

从结果中可以到titles表的主索引为<emp_no, title, from_date>,还有一个辅助索引<emp_no>。为了避免多个索引使事情变复杂(MySQL的SQL优化器在多索引时行为比较复杂),这里我们将辅助索引drop掉:

1
ALTER TABLE employees.titles DROP INDEX emp_no;

这样就可以专心分析索引PRIMARY的行为了。

情况一:全列匹配。
1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26';
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+

很明显,当按照索引中所有列进行精确匹配(这里精确匹配指“=”或“IN”匹配)时,索引可以被用到。这里有一点需要注意,理论上索引对顺序是敏感的,但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引,例如我们将where中的条件顺序颠倒:

1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26' AND emp_no='10001' AND title='Senior Engineer';
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+

效果是一样的。

情况二:最左前缀匹配。
1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
| 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+

当查询条件精确匹配索引的左边连续一个或几个列时,如<emp_no>或<emp_no, title>,所以可以被用到,但是只能用到一部分,即条件所组成的最左前缀。上面的查询从分析结果看用到了PRIMARY索引,但是key_len为4,说明只用到了索引的第一列前缀。

情况三:查询条件用到了索引中列的精确匹配,但是中间某个条件未提供。
1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

此时索引使用情况和情况二相同,因为title未提供,所以查询只用到了索引的第一列,而后面的from_date虽然也在索引中,但是由于title不存在而无法和左前缀连接,因此需要对结果进行扫描过滤from_date(这里由于emp_no唯一,所以不存在扫描)。如果想让from_date也使用索引而不是where过滤,可以增加一个辅助索引<emp_no, from_date>,此时上面的查询会使用这个索引。除此之外,还可以使用一种称之为“隔离列”的优化方法,将emp_no与from_date之间的“坑”填上。

首先我们看下title一共有几种不同的值:

1
2
3
4
5
6
7
8
9
10
11
12
SELECT DISTINCT(title) FROM employees.titles;
+--------------------+
| title |
+--------------------+
| Senior Engineer |
| Staff |
| Engineer |
| Senior Staff |
| Assistant Engineer |
| Technique Leader |
| Manager |
+--------------------+

只有7种。在这种成为“坑”的列值比较少的情况下,可以考虑用“IN”来填补这个“坑”从而形成最左前缀:

1
2
3
4
5
6
7
8
9
EXPLAIN SELECT * FROM employees.titles
WHERE emp_no='10001'
AND title IN ('Senior Engineer', 'Staff', 'Engineer', 'Senior Staff', 'Assistant Engineer', 'Technique Leader', 'Manager')
AND from_date='1986-06-26';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 7 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

这次key_len为59,说明索引被用全了,但是从type和rows看出IN实际上执行了一个range查询,这里检查了7个key。看下两种查询的性能比较:

1
2
3
4
5
6
7
SHOW PROFILES;
+----------+------------+-------------------------------------------------------------------------------+
| Query_ID | Duration | Query |
+----------+------------+-------------------------------------------------------------------------------+
| 10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26'|
| 11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no='10001' AND title IN ... |
+----------+------------+-------------------------------------------------------------------------------+

“填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据,则后者性能优势会更加明显。当然,如果title的值很多,用填坑就不合适了,必须建立辅助索引。

情况四:查询条件没有指定索引第一列。
1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26';
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
| 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+

由于不是最左前缀,索引这样的查询显然用不到索引。

情况五:匹配某列的前缀字符串。
1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title LIKE 'Senior%';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 56 | NULL | 1 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

此时可以用到索引,但是如果通配符不是只出现在末尾,则无法使用索引。(原文表述有误,如果通配符%不出现在开头,则可以用到索引,但根据具体情况不同可能只会用其中一个前缀)

情况六:范围查询。
1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE emp_no < '10010' and title='Senior Engineer';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

范围列可以用到索引(必须是最左前缀),但是范围列后面的列无法用到索引。同时,索引最多用于一个范围列,因此如果查询条件中有两个范围列则无法全用到索引。

1
2
3
4
5
6
7
8
9
EXPLAIN SELECT * FROM employees.titles
WHERE emp_no < '10010'
AND title='Senior Engineer'
AND from_date BETWEEN '1986-01-01' AND '1986-12-31';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方,那就是仅用explain可能无法区分范围索引和多值匹配,因为在type中这两者都显示为range。同时,用了“between”并不意味着就是范围查询,例如下面的查询:

1
2
3
4
5
6
7
8
9
EXPLAIN SELECT * FROM employees.titles
WHERE emp_no BETWEEN '10001' AND '10010'
AND title='Senior Engineer'
AND from_date BETWEEN '1986-01-01' AND '1986-12-31';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

看起来是用了两个范围查询,但作用于emp_no上的“BETWEEN”实际上相当于“IN”,也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配,否则会对MySQL的行为产生困惑。

情况七:查询条件中含有函数或表达式。

很不幸,如果查询条件中含有函数或表达式,则MySQL不会为这列使用索引(虽然某些在数学意义上可以使用)。例如:

1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND left(title, 6)='Senior';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

虽然这个查询和情况五中功能相同,但是由于使用了函数left,则无法为title列应用索引,而情况五中用LIKE则可以。再如:

1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.titles WHERE emp_no - 1='10000';
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
| 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+

显然这个查询等价于查询emp_no为10001的函数,但是由于查询条件是一个表达式,MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度,因此在写查询语句时尽量避免表达式出现在查询中,而是先手工私下代数运算,转换为无表达式的查询语句。

索引选择性与前缀索引

既然索引可以加快查询速度,那么是不是只要是查询语句需要,就建上索引?答案是否定的。因为索引虽然加快了查询速度,但索引也是有代价的:索引文件本身要消耗存储空间,同时索引会加重插入、删除和修改记录时的负担,另外,MySQL在运行时也要消耗资源维护索引,因此索引并不是越多越好。一般两种情况下不建议建索引。

第一种情况是表记录比较少,例如一两千条甚至只有几百条记录的表,没必要建索引,让查询做全表扫描就好了。至于多少条记录才算多,这个个人有个人的看法,我个人的经验是以2000作为分界线,记录数不超过 2000可以考虑不建索引,超过2000条可以酌情考虑索引。

另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性(Selectivity),是指不重复的索引值(也叫基数,Cardinality)与表记录数(#T)的比值:

Index Selectivity = Cardinality / #T

显然选择性的取值范围为(0, 1],选择性越高的索引价值越大,这是由B+Tree的性质决定的。例如,上文用到的employees.titles表,如果title字段经常被单独查询,是否需要建索引,我们看一下它的选择性:

1
2
3
4
5
6
SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;
+-------------+
| Selectivity |
+-------------+
| 0.0000 |
+-------------+

title的选择性不足0.0001(精确值为0.00001579),所以实在没有什么必要为其单独建索引。

有一种与索引选择性有关的索引优化策略叫做前缀索引,就是用列的前缀代替整个列作为索引key,当前缀长度合适时,可以做到既使得前缀索引的选择性接近全列索引,同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。

从图12可以看到employees表只有一个索引<emp_no>,那么如果我们想按名字搜索一个人,就只能全表扫描了:

1
2
3
4
5
6
EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido';
+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
| 1 | SIMPLE | employees | ALL | NULL | NULL | NULL | NULL | 300024 | Using where |
+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

如果频繁按名字搜索员工,这样显然效率很低,因此我们可以考虑建索引。有两种选择,建<first_name>或<first_name, last_name>,看下两个索引的选择性:

1
2
3
4
5
6
7
8
9
10
11
12
SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
| 0.0042 |
+-------------+
SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
| 0.9313 |
+-------------+

<first_name>显然选择性太低,<first_name, last_name>选择性很好,但是first_name和last_name加起来长度为30,有没有兼顾长度和选择性的办法?可以考虑用first_name和last_name的前几个字符建立索引,例如<first_name, left(last_name, 3)>,看看其选择性:

1
2
3
4
5
6
SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
| 0.7879 |
+-------------+

选择性还不错,但离0.9313还是有点距离,那么把last_name前缀加到4:

1
2
3
4
5
6
SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
| 0.9007 |
+-------------+

这时选择性已经很理想了,而这个索引的长度只有18,比<first_name, last_name>短了接近一半,我们把这个前缀索引 建上:

1
2
ALTER TABLE employees.employees
ADD INDEX `first_name_last_name4` (first_name, last_name(4));

此时再执行一遍按名字查询,比较分析一下与建索引前的结果:

1
2
3
4
5
6
7
SHOW PROFILES;
+----------+------------+---------------------------------------------------------------------------------+
| Query_ID | Duration | Query |
+----------+------------+---------------------------------------------------------------------------------+
| 87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |
| 90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |
+----------+------------+---------------------------------------------------------------------------------+

性能的提升是显著的,查询速度提高了120多倍。

前缀索引兼顾索引大小和查询速度,但是其缺点是不能用于ORDER BY和GROUP BY操作,也不能用于Covering index(即当索引本身包含查询所需全部数据时,不再访问数据文件本身)。

InnoDB的主键选择与插入优化

在使用InnoDB存储引擎时,如果没有特别的需要,请永远使用一个与业务无关的自增字段作为主键。

经常看到有帖子或博客讨论主键选择问题,有人建议使用业务无关的自增主键,有人觉得没有必要,完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点,大多数论据都是业务层面的。如果从数据库索引优化角度看,使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。

上文讨论过InnoDB的索引实现,InnoDB使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。

如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置:

此时 MySQL 不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过 OPTIMIZE TABLE 来重建表并优化填充页面。

因此,只要可以,请尽量在 InnoDB 上采用自增字段做主键。

参考文章

  1. 姜承尧 著《MySQL技术内幕:InnoDB存储引擎》
  2. MySQL(五) MySQL中的索引详讲
  3. MySQL索引总结
  4. MySQL索引背后的数据结构及算法原理
  5. MySQL 索引及查询优化总结
如果这篇文章对您很有帮助,不妨
-------------    本文结束  感谢您的阅读    -------------
0%