A database index is a data structure that improves the speed of operations in a table. Indexes can be created using one or more columns, providing the basis for both rapid random lookups and efficient ordering of access to records.
[TOC]
根据上面索引的定义,可以知道索引其实是一种数据结构,主要用于提高表中的查询效率,除此之外,索引还是数据库随机高速读取和对记录进行有效排序的基础。
除了像 Redis 这样的内存型数据库外,大部分的关系型数据库如 MySQL 等的数据都是直接存储在磁盘上的,而对于从磁盘查找数据来说,需要经历寻道, 寻址, 数据传输三个阶段。
所以直接从磁盘读取数据的 IO 耗时一般在 10ms 左右,为了避免频繁的磁盘 IO,所以操作系统在读取数据时会以页为单位,一次读取目标数据以及和目标数据相邻的一页大小(4K或8K)的数据并放在缓存中,这样下次再读取相邻的数据时就可以直接从缓存中返回了。
在不使用索引的情况下,如果要查询最后一条数据,就需要从头遍历到尾, 这种情况下,数据库需要读取所有的片才能得到目标数据,大量时间会浪费在磁盘 IO 上,为此,我们需要一种数据结构去记录数据项和磁盘中页的关系,这样在查询某条记录时就可以直接定位到某一页,这样只需要进行一次磁盘IO便可以得到目标数据,可以大大优化查询效率,这种数据结构便是索引。
要实现上面的功能,首先可以采用 Hash Table 的方式,将索引键 Hash 之后存储哈希值和键对应的行指针,这样一来,在使用哈希索引查询的时候就可以直接计算出要查询记录的哈希值,然后查询此哈希值对应的行指针,由于每一行所需要的存储空间是固定的,所以得到行指针就相当于定位到了记录对应的页,这时每次查询只需要进行一次磁盘 IO, 可以大大优化查询效率,但哈希索引存在一些问题:
IN
, =
, <=>
)时才能起到优化效率的效果,在进行非等值操作(如 !=
, >
, <
, <>
)时起不到任何作用。除了使用 Hash Table, 另一个思路是使用排序树,以排序树的结构组织页后,可以将原来查询 O(n)的复杂度降低到 \lg n 而 o(n)的复杂度就意味着每次查询需要进行 n 次磁盘IO,使用排序树后虽然不能像哈希表一样达到 O(1) 的复杂度,但相比不使用索引可以大大减少磁盘 IO 的次数 。
MySQL 中默认使用 B+ 树构建索引,之所以使用 B+ 树而不是 B 树或二叉排序树的原因在于:
B+ 树就满足上面两点要求,首先 B+ 树是一棵多路平衡二叉树,其次由于磁盘IO以固定大小的页为单位,所以每次进行磁盘IO能够查询出的数据量是有限制的,这同样意味着树的一个父节点能够持有的子节点数量是有限的,而 B+ 树的数据只存储在叶子节点,中间节点只存储指针,这使得每个中间节点能持有更多的子节点,相比 B 树,B+ 树的高度更低,且每次查询都必须遍历到叶子节点,使得 B+ 树的查询稳定性更高。
虽然上面说 B+ 树的叶子节点存储数据,但具体到 MySQL 对索引的实现上,叶子节点存储的依然不是真正的数据,存储的只是指向真实数据的指针,当然聚簇索引除外,聚簇索引存储数据的顺序和索引顺序是一致的,一张表也只能建立一个聚簇索引,一般用于主键索引。
MySQL 索引根据用途不同可以分为以下几种类型:
char、varchar,text
列上, 需要注意的是,直到 MySQL 5.6 InnoDB 引擎才支持了全文索引,在这之前只有 MyISAM 支持, 同时,全文索引一般配合 match against
使用,而不是 where
, 关于全文索引的用法,可以参考知乎这篇文章
值得一提的是,在数据量较大时候,现将数据放入一个没有全局索引的表中,然后再用CREATE index创建fulltext索引,要比先为一张表建立fulltext然后再将数据写入的速度快很多。
创建索引有三种方式;
创建表时直接定义
使用 ALTER
语句修改表结构创建
直接使用 CREATE TABLE
命令创建:
CREATE TABLE table_name[col_name data type]
[unique|fulltext][index|key][index_name](col_name[length])[asc|desc]
unique|fulltext
为可选参数,分别表示唯一索引、全文索引
index
和 key
为同义词,两者作用相同,用来指定创建索引
col_name
为需要创建索引的字段列,该列必须从数据表中该定义的多个列中选择
index_name
指定索引的名称,为可选参数,如果不指定,默认col_name为索引值
length
为可选参数,表示索引的长度,只有字符串类型的字段才能指定索引长度
asc
或 desc
指定升序或降序的索引值存储
删除索引:
直接删除:
DROP index_name ON table_name;
通过修改表结构删除
ALTER TABLE table_name DROP index_name;
天下没有免费的午餐,索引也并不是万能的,它带来高查询效率的同时也会带来一些问题:
所以对一些不应该建立索引的列建立索引后可能导致更差的性能,在考量某一列是否应该建立索引时需要参考一个重要的法则:最左前缀法则,不满足该法则可能导致索引失效进而退化成全表扫描。
最左前缀法则是建立联合索引时最重要的法则。
mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配.
如以下的表结构:
CREATE TABLE `left` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`a` varchar(255) NOT NULL,
`b` varchar(255) NOT NULL,
`c` varchar(255) NOT NULL,
`d` varchar(255) NOT NULL,
PRIMARY KEY (`id`),
KEY `index1` (`a`,`b`,`c`)
) ENGINE=InnoDB AUTO_INCREMENT=86139 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
我们建立了 a, b, c
的组合索引后:
在进行等值查询如=
或 IN
时, 可以不考虑顺序,SQL 查询优化器会自动调整语句顺序,如执行下面两条语句的效果是一样的(根据索引长度我们可以推断出对哪几个列使用了索引):
可以查询建立了聚合索引的某几列,DBS会根据建立索引时的顺序从左开始匹配能够使用索引的列,如执行a = “” AND b = “”
时会对 a 和 b 使用索引,而在执行 a = “” AND c = “"
时则只会对 a 使用索引,而如果只执行 b = “”
时,由于第一个索引 a 就无法匹配到,所以不会使用索引
最左匹配原则在遇到范围查询:**>、<、between、like** 时会停止匹配,如执行 a = “” AND b > 10 AND c = “”
时只会对 a 使用索引。
对索引列进行运算操作会导致索引失效,原因与 like 的通配符一样,还有需要注意一点,如果索引字段是字符类型,查询时不加引号也会导致索引失效,原因在于MySQL会自动为我们的查询语句转化成字符,这就相当于引入了运算操作:
SELECT * FROM `left` WHERE a = "" AND b = 1
-- 将 1 转化为 '1' 的过程引入了运算操作导致索引失效
如果 OR
之后的字段没有使用索引,那么整个索引都将失效。
NOT IN
可能导致的索引失效
首先要明确的是最左匹配原则适用于联合索引,对于普通索引,不存在匹配的问题,而之所以要严格进行最左匹配,也是由联合索引的数据结构形式决定的:
我们知道 MySQL 默认情况下使用 B+ 树组织索引的数据结构,对于像上文中的联合索引,它的结构是这样的:
相比普通索引的叶子节点,联合索引的叶子节点存储所有关键字的数据,比如建立了a, b, c
的索引,那么如上图,每个叶子节点都会存储a, b, c 三个关键字的数据信息,并且会按照建立索引时的顺序排序,但中间节点只会存储第一个关键字的位置指针,当我们执行类似
SELECT * FROM `table` WHERE a = "1" AND b = "2" AND c = "4"
时,数据库会根据第一个关键字 a 的值 1 定位到某个叶子(图中左边的叶子节点),然后从所有叶子节点的数据里检索出符合第一条规则a = "1"
的数据(图中前六行),然后再从这些数据里检索出符合第二条规则的数据(图中2, 3, 4)行,依次类推直到找到或确认找不到期望数据为止。
而之所以遵循最左匹配原则,也是因为叶子节点的排序方式是按照索引建立时的顺序排序的,也就是 b 只有在 a 相等的情况下才是有序的(如图中第二列整体并不是有序的,但只看 a = 1 前提下的 b 就是有序的了),所以如果跳过 a 去查询 b, 因为无法保证 b 的有序性,只能进行全表扫描。
like
之所以遇到以通配符开头的情况才停止匹配也是由叶子节点的这种数据排序方式决定的,因为 like 字句如果不以通配符开头那他开头的部分是可以利用到排序信息的,如执行:
SELECT * FROM `left` WHERE a = "1" AND b LIKE "2%"
虽然 b 的检索不是等值检索,但我们任然可以根据 like 子句开头的 “2” 快速定位到 2 ~ 4 行,但如果以通配符开头,显然就定位不到了。
最好的区分度为
加入我们建立了 a, b, c
顺序的组合索引,但 a
的区分度不高,然后执行了 WHERE b = "" AND ...
就会出现 INDEX SKIP SCAN 的情况, 也就是说 SQL 查询优化器跳过了 a 对后面的列使用了索引,如下面这种情况:
上图中 songs 表结构如下:
+--------+--------------+------+-----+---------+-------+
| Field | Type | Null | Key | Default | Extra |
+--------+--------------+------+-----+---------+-------+
| id | bigint(25) | NO | PRI | NULL | |
| name | varchar(255) | NO | | NULL | |
| link | varchar(200) | NO | | NULL | |
| singer | int(11) | YES | | NULL | |
+--------+--------------+------+-----+---------+-------+
并且为该表建立了 singer, name, link
顺序的组合索引, 但 singer 的区分度约为 0.04, 很低:
mysql> select COUNT(DISTINCT left(singer,110))/COUNT(*) AS singer, COUNT(DISTINCT left(name,255))/COUNT(*) AS name, COUNT(DISTINCT left(link,200))/COUNT(*) AS link FROM songs ;
+--------+--------+--------+
| singer | name | link |
+--------+--------+--------+
| 0.0390 | 0.7715 | 1.0000 |
+--------+--------+--------+
1 row in set (25.82 sec)
在这种情况下,由于 singer 的区分度很低,所以全表扫描查询 singer 字段的代价并不是很高,同样对于 singer 来说,使用索引的效果并不明显,但相比之下,后面的 name 和 link 字段的区分度很高,使用索引的效果会非常明显,这时如果由于 “无关紧要” 的 singer 导致后面真正需要索引的 name 和 link 无法使用索引显然得不偿失,因此在 MySQL 8.0 之后加入了 ISS 机制,它允许组合索引在左边的列唯一值较少的情况下跳过左边列对右边列使用索引。
索引的出现本就是为了降低查询成本的,但若在某些情况下使用索引反而增加了查询成本,那就不应该使用索引,MySQL 在执行查询前会预估查询成本,然后根据成本决定是否使用索引或使用哪个索引,不使用索引时的查询成本包括两部分:
而如果表中有索引,在执行查询前,数据库引擎会估算使用索引所需要的成本,具体估算方法参考:xx , 估算出的值可以通过 optimizer_trace
工具查看,如果索引的成本高于全表扫描的成本,那就会放弃索引。
如执行 :
SET optimizer_trace="enabled=on";
SELECT * FROM `left` WHERE a > "1";
SELECT * FROM information_schema.OPTIMIZER_TRACE;
SET optimizer_trace="enabled=off";
后得到使用 index1 索引的成本为 54705
"analyzing_range_alternatives": {
"range_scan_alternatives": [
{
"index": "index1",
"ranges": [
"1 < a"
],
"index_dives_for_eq_ranges": true,
"rowid_ordered": false,
"using_mrr": false,
"index_only": false,
"rows": 49977,
"cost": 54705,
"chosen": false,
"cause": "cost"
}
],
"analyzing_roworder_intersect": {
"usable": false,
"cause": "too_few_roworder_scans"
}
}
但全表扫描成本为:
显然全表扫描的效率要高于使用索引的效率。
需要注意的是数据库引擎只是只是在估算成本,这个值不一定准确,上面的例子从最左前缀的角度也不应该使用索引,只是为了说明并不是在任何时候数据库引擎都会去使用索引的在涉及到低区分度,Null 值等的时候,引擎会选取一个相对最优的方案。
OR
IN
, NOT IN
, EXISTS
覆盖索引指的是索引字段覆盖了需要查询的所有字段,这时根据索引便可以拿到所有数据而不需要回表查询,反之,如果使用类似 SELECT *
或 索引字段未覆盖期望的所有字段时,未被覆盖的字段就需要回表查询,这便又增加了磁盘 IO 的次数,如果发生了回表查询, EXPLAIN 的描述(Extra)字段会显示 Using index condition
这时我们应该考虑是否需要优化。
索引不一定能 100% 提高查询效率,使用不当反而会使性能下降
在每次查询时,数据库只会选择一个最优的索引使用,所以使用复合索引往往优于使用多个单列索引。
WHERE
子句中的列。SELECT *