MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。
数据库查询是数据库的最主要功能之一,我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化,这篇文章对索引做一个系统的梳理,希望对大家有帮助。
一、MySQL有哪些索引类型
索引的分类可以从多个角度进行,下面分别从数据结构,物理存储和业务逻辑三个维度进行划分。
1、从数据结构角度
(1)B+树索引(O(log(n)))
关于B+树索引,后面会深入解析
(2)hash索引
- 仅仅能满足"=","IN"和"<=>"查询,不能使用范围查询
- 其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引
- 只有Memory存储引擎显示支持hash索引
(3)FULLTEXT索引
现在MyISAM和InnoDB引擎都支持了
(4)R-Tree索引
用于对GIS数据类型创建SPATIAL索引
2、从物理存储角度
(1)聚集索引(clustered index)
- 正文内容按照一个特定维度排序存储,这个特定的维度就是聚集索引;
- Innodb存储引擎中行记录就是按照聚集索引维度顺序存储的,Innodb的表也称为索引表;因为行记录只能按照一个维度进行排序,所以一张表只能有一个聚集索引。
(2)非聚集索引(non-clustered index)
索引是通过二叉树的数据结构来描述的,我们可以这么理解聚簇索引:索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点,只不过有一个指针指向对应的数据块。
非聚集索引索引项顺序存储,但索引项对应的内容却是随机存储的;
举个例子说明下:
create table student (
`id` INT UNSIGNED AUTO_INCREMENT,
`name` VARCHAR(255),
PRIMARY KEY(`id`),
KEY(`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
该表中主键id是该表的聚集索引、name为非聚集索引;表中的每行数据都是按照聚集索引id排序存储的;比如要查找name='Arla'和name='Arle'的两个同学,他们在name索引表中位置可能是相邻的,但是实际存储位置可能差的很远。name索引表节点按照name排序,检索的是每一行数据的主键。聚集索引表按照主键id排序,检索的是每一行数据的真实内容。
3、从逻辑角度
(1)主键索引
主键索引是一种特殊的唯一索引,不允许有空值
(2)普通索引或者单列索引
(3)多列索引(复合索引)
复合索引指多个字段上创建的索引,只有在查询条件中使用了创建索引时的第一个字段,索引才会被使用。使用复合索引时遵循最左前缀集合
(4)唯一索引或者非唯一索引
(5)空间索引
空间索引是对空间数据类型的字段建立的索引,MYSQL中的空间数据类型有4种,分别是GEOMETRY、POINT、LINESTRING、POLYGON。
MYSQL使用SPATIAL关键字进行扩展,使得能够用于创建正规索引类型的语法创建空间索引。创建空间索引的列,必须将其声明为NOT NULL,空间索引只能在存储引擎为MYISAM的表中创建.
二、索引创建方式
CREATE TABLE table_name[col_name data type]
[unique|fulltext|spatial][index|key][index_name](col_name[length])[asc|desc]
- unique|fulltext|spatial为可选参数,分别表示唯一索引、全文索引和空间索引;
- index和key为同义词,两者作用相同,用来指定创建索引
- col_name为需要创建索引的字段列,该列必须从数据表中该定义的多个列中选择;
- index_name指定索引的名称,为可选参数,如果不指定,MYSQL默认col_name为索引值;length为可选参数,表示索引的长度,只有字符串类型的字段才能指定索引长度;
- asc或desc指定升序或降序的索引值存储
1、创建表时建立索引
(1)创建普通索引
create table table_name(
id int(11),
name varchar(20),
sex boolean,
INDEX(id)
);
查看表结构
show create table table_name;
可以使 EXPLAIN 语句查看索引是否被使用
explain select * from table_name where id = 1\G
(2)创建唯一索引
create table index2(
id int unique,
name varchar(20),
unique INDEX index_2(id asc)
);
(3)创建全文索引
全文索引只能在char,varchar或者text 类型的字段上。而且,只有MyISAM 储存引擎支持全文索引。
create table idnex3(
id int,
info varchar(20),
FULLTEXT INDEX index3_info(info)
)ENGINE=MyISAM;
(4)创建单列索引
create table index4(
id int,
subject varchar(255),
index index4_st(subject(10))
);
这里需要注意的,subject 的长度为255,但是index4_st索引只有10。这样做的目的还是为了提高查询速度。对于字符型的数据,可以不用查询全部信息,只查询其前面的若干字符信息。
(5)创建多列索引
create table index5(
id int,
name varchar(20),
sex char(4),
index index5_ns(name.sex)
);
这是我们可以看到,name 和sex字段上已经创建了index_ns索引。
2、在已经存在的表中创建索引
(1)创建普通索引
在example0() 表中的id 创建名为index7_id 的索引。
create index index7_id on example0(id);
(2)创建唯一索引
create UNIQUE index index_name on table_name(name);
(3)创建全文索引
create FULLTEXT index index_name on table_name(info);
(4)创建单列索引
create INDEX index_name ON table_name(name(10));
(5)创建多列索引
create INDEX index_name ON table_name(name,sex);
3、用alter table 语句来创建索引
(1)创建普通索引
在name字段上创建名为indx_name 的索引
alter table table_name ADD INDEX index_name(name(20));
(2)创建唯一性索引
alter table table_name ADD UNIQUE INDEX index_name(id);
(3)创建全文索引
alter table table_name ADD FULLTEXT INDEX index_name(info);
(4)创建单列索引
alter table table_name ADD INDEX index_name(name(4));
(5)创建多列索引
alter tabel table_name ADD INDEX index_name(name.sex);
4、删除索引
DROP INDEX index_name ON table_name;
三、索引树是如何维护的
目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,那么索引树是如何维护的?
1、查找结构进化史
查找是数据结构和算法中一个非常重要的概念。
- 线性查找:一个个找;实现简单;太慢
- 二分查找:有序;简单;要求是有序的,插入特别慢
- HASH查找:查询快;占用空间;不太适合存储大规模数据
- 二叉查找树:插入和查询很快(log(n));无法存大规模数据,复杂度退化
- 平衡树:解决 BST 退化问题,树是平衡的;节点非常多的时候,依然树高很高
- 多路查找树:一个父亲多个孩子节点(度);节点过多树高不会特别深
- 多路平衡查找树:B-Tree
2、B-Tree
B-Tree是一种多路搜索树(并不是二叉的):
- 定义任意非叶子结点最多只有M个儿子;且M>2;
- 根结点的儿子数为[2, M];
- 除根结点以外的非叶子结点的儿子数为[M/2, M];
- 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
- 非叶子结点的关键字个数=指向儿子的指针个数-1;
- 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
- 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的
子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树; - 所有叶子结点位于同一层;
- 每个k对应一个data。
如:(M=3)相当于一个2–3树,2–3树是一个这样的一棵树, 它的每个节点要么有2个孩子和1个数据元素,要么有3个孩子和2个数据元素,叶子节点没有孩子,并且有1个或2个数据元素。
B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;B-Tree上查找算法的伪代码如下:
BTree_Search(node, key) { if(node == null) return null; foreach(node.key) { if(node.key[i] == key) return node.data[i]; if(node.key[i] > key) return BTree_Search(point[i]->node); } return BTree_Search(point[i+1]->node); } data = BTree_Search(root, my_key);
(1)B-树的特性
- 关键字集合分布在整颗树中;
- 任何一个关键字出现且只出现在一个结点中;
- 搜索有可能在非叶子结点结束;
- 其搜索性能等价于在关键字全集内做一次二分查找;
- 自动层次控制;
(2)B-树的自控制
B树中每一个内部节点会包含一定数量的键值。通常,键值的数量被选定在d和2d之间。在实际中,键值占用了节点中大部分的空间。因数2将保证节点可以被拆分或组合。如果一个内部节点有2d个键值,那么添加一个键值给此节点的过程,将会拆分2d键值为2个d键值的节点,并把此键值添加给父节点。每一个拆分的节点需要最小数目的键值。相似地,如果一个内部节点和他的邻居两者都有d个键值,那么将通过它与邻居的合并来删除一个键值。删除此键值将导致此节点拥有d-1个键值;与邻居的合并则加上d个键值,再加上从邻居节点的父节点移来的一个键值。结果为完全填充的2d个键值。
(3)B-树的构造过程
下面是往B树中依次插入
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
3、B+Tree
B-Tree有许多变种,其中最常见的是B+Tree,MySQL就普遍使用B+Tree实现其索引结构。
与B-Tree相比,B+Tree有以下不同点:
- 非叶子结点的子树指针与关键字个数相同;
- 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
- 为所有叶子结点增加一个链指针;
- 所有关键字都在叶子结点出现;
- 内节点不存储data,只存储key
如:(M=3)
B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
(1)B+的特性
- 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
- 不可能在非叶子结点命中;
- 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
- 更适合文件索引系统;
(2)B+树的构造过程
下面是往B+树中依次插入
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
3、索引的物理存储
一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。
这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
假如每个盘块可以正好存放一个B树的结点(正好存放2个文件名)。那么一个BTNODE结点就代表一个盘块,而子树指针就是存放另外一个盘块的地址。
(1)模拟B+树查找过程
下面,咱们来模拟下查找文件29的过程:
- 根据根结点指针找到文件目录的根磁盘块1,将其中的信息导入内存。【磁盘IO操作 1次】
- 此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现:17<29<35,因此我们找到指针p2。
- 根据p2指针,我们定位到磁盘块3,并将其中的信息导入内存。【磁盘IO操作 2次】
- 此时内存中有两个文件名26,30和三个存储其他磁盘页面地址的数据。根据算法我们发现:26<29<30,因此我们找到指针p2。
- 根据p2指针,我们定位到磁盘块8,并将其中的信息导入内存。【磁盘IO操作 3次】
- 此时内存中有两个文件名28,29。根据算法我们查找到文件名29,并定位了该文件内存的磁盘地址。
分析上面的过程,发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找,由于是一个有序表结构,可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。
当然,如果我们使用平衡二叉树的磁盘存储结构来进行查找,磁盘4次,最多5次,而且文件越多,B树比平衡二叉树所用的磁盘IO操作次数将越少,效率也越高。
4、B+tree的优点
(1)B+-tree的磁盘读写代价更低
B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+
树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B 树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
(2)B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。
四、索引创建有哪些原则
索引查询是数据库中重要的记录查询方法,要不要进入索引以及在那些字段上建立索引都要和实际数据库系统的查询要求结合来考虑,下面给出实际中的一些通用的原则:
- 在经常用作过滤器的字段上建立索引;
- 在SQL语句中经常进行GROUP BY、ORDER BY的字段上建立索引;
- 在不同值较少的字段上不必要建立索引,如性别字段;
- 对于经常存取的列避免建立索引;
- 用于联接的列(主健/外健)上建立索引;
- 在经常存取的多个列上建立复合索引,但要注意复合索引的建立顺序要按照使用的频度来确定;
- 缺省情况下建立的是非簇集索引,但在以下情况下最好考虑簇集索引,如:含有有限数目(不是很少)唯一的列;进行大范围的查询;充分的利用索引可以减少表扫描I/0的次数,有效的避免对整表的搜索。
- 经常用在WHERE子句中的数据列;
- 经常出现在关键字order by、group by、distinct后面的字段,建立索引。如果建立的是复合索引,索引的字段顺序要和这些关键字后面的字段顺序一致,否则索引不会被使用;
- 对于那些查询中很少涉及的列,重复值比较多的列不要建立索引;
- 对于定义为text、image和bit的数据类型的列不要建立索引;
- 对于经常存取的列避免建立索引;
- 限制表上的索引数目。对一个存在大量更新操作的表,所建索引的数目一般不要超过3个,最多不要超过5个。索引虽说提高了访问速度,但太多索引会影响数据的更新操作。
- 对复合索引,按照字段在查询条件中出现的频度建立索引。在复合索引中,记录首先按照第一个字段排序。对于在第一个字段上取值相同的记录,系统再按照第二个字段的取值排序,以此类推。因此只有复合索引的第一个字段出现在查询条件中,该索引才可能被使用,因此将应用频度高的字段,放置在复合索引的前面,会使系统最大可能地使用此索引,发挥索引的作用。
1、组合多个索引
一个单独的索引扫描只能用于这样的条件子句:使用被索引字段和索引操作符类中的操作符, 并且这些条件以AND连接。
假设在(a, b)上有一个索引, 那么类似WHERE a = 5 AND b = 6的条件可以使用索引,但是像WHERE a = 5 OR b = 6的条件就不能直接使用索引。
一个类似WHERE x =42 OR x = 47 OR x = 53 OR x = 99 这样的查询可以分解成四个在x上的独立扫描,每个扫描使用一个条件, 最后将这些扫描的结果OR 在一起,生成最终结果。
另外一个例子是,如果我们在x 和y上有独立的索引,一个类似WHERE x = 5 AND y = 6 这样的查询可以分解为几个使用独立索引的子句,然后把这几个结果AND 在一起,生成最终结果。
五、索引失效有哪几种情况
- 如果条件中有or,即使其中有条件带索引也不会使用(这也是为什么尽量少用or的原因)
- 对于多列索引,不是使用的第一部分(第一个),则不会使用索引
- like查询是以%开头
- 如果列类型是字符串,那一定要在条件中将数据使用引号引用起来,否则不使用索引
- 如果mysql估计使用全表扫描要比使用索引快,则不使用索引
1、联合索引失效的条件
联合索引又叫复合索引。两个或更多个列上的索引被称作复合索引。
对于复合索引:Mysql从左到右的使用索引中的字段,一个查询可以只使用索引中的一部份,但只能是最左侧部分。例如索引是key index (a,b,c)。 可以支持a | a,b| a,b,c 3种组合进行查找,但不支持 b,c进行查找 .当最左侧字段是常量引用时,索引就十分有效。
所以说创建复合索引时,应该仔细考虑列的顺序。对索引中的所有列执行搜索或仅对前几列执行搜索时,复合索引非常有用;仅对后面的任意列执行搜索时,复合索引则没有用处。
六、如何查看索引的使用情况
这里记录两种方式,分别是
1、使用Handler_read查看索引的使用情况
show status like ‘Handler_read%';
大家可以注意:
- handler_read_key:这个值越高越好,越高表示使用索引查询到的次数
- handler_read_rnd_next:这个值越高,说明查询低效
+-----------------------+--------------+
| Variable_name | Value |
+-----------------------+--------------+
| Handler_read_first | 153 |
| Handler_read_key | 364 |
| Handler_read_next | 425 |
| Handler_read_prev | 598 |
| Handler_read_rnd | 605 |
| Handler_read_rnd_next | 860571 |
+-----------------------+--------------+
6 rows in set (0.00 sec)
————————————————
分析这几个值,我们可以查看当前索引的使用情况:
- Handler_read_first:索引中第一条被读的次数。如果较高,它表示服务器正执行大量全索引扫描;例如,SELECT col1 FROM foo,假定col1有索引(这个值越低越好)。
- Handler_read_key:如果索引正在工作,这个值代表一个行被索引值读的次数,如果值越低,表示索引得到的性能改善不高,因为索引不经常使用(这个值越高越好)。
- Handler_read_next :按照键顺序读下一行的请求数。如果你用范围约束或如果执行索引扫描来查询索引列,该值增加。
- Handler_read_prev:按照键顺序读前一行的请求数。该读方法主要用于优化ORDER BY ... DESC。
- Handler_read_rnd :根据固定位置读一行的请求数。如果你正执行大量查询并需要对结果进行排序该值较高。你可能使用了大量需要MySQL扫描整个表的查询或你的连接没有正确使用键。这个值较高,意味着运行效率低,应该建立索引来补救。
- Handler_read_rnd_next:在数据文件中读下一行的请求数。如果你正进行大量的表扫描,该值较高。通常说明你的表索引不正确或写入的查询没有利用索引。
2、在sys库中查看没用的索引
查询 schema_unused_indexes库。
root@localhost [sys]>select * from schema_unused_indexes;
+-------------------+-------------+------------+
| object_schema | object_name | index_name |
+-------------------+-------------+------------+
| sysbench_testdata | sbtest1 | k_1 |
| sysbench_testdata | sbtest10 | k_10 |
| sysbench_testdata | sbtest3 | k_3 |
| sysbench_testdata | sbtest4 | k_4 |
| sysbench_testdata | sbtest5 | k_5 |
| sysbench_testdata | sbtest6 | k_6 |
| sysbench_testdata | sbtest7 | k_7 |
| sysbench_testdata | sbtest8 | k_8 |
| sysbench_testdata | sbtest9 | k_9 |
+-------------------+-------------+------------+
9 rows in set (0.00 sec)
七、EXPLAIN解释命令查看索引是否生效
explain显示了mysql如何使用索引来处理select语句以及连接表。可以帮助选择更好的索引和写出更优化的查询语句。
1、一个实际例子
新建一张表,
CREATE TABLE IF NOT EXISTS `article` (`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`author_id` int(10) unsigned NOT NULL,
`category_id` int(10) unsigned NOT NULL,
`views` int(10) unsigned NOT NULL,
`comments` int(10) unsigned NOT NULL,
`title` varbinary(255) NOT NULL,
`content` text NOT NULL,
PRIMARY KEY (`id`)
);
执行查询,
EXPLAIN
SELECT author_id
FROM `article`
WHERE category_id = 1 AND comments > 1
ORDER BY views DESC
LIMIT 1
响应数据如下,
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: article
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 3
Extra: Using where; Using filesort
1 row in set (0.00 sec)
type 是 ALL,即最坏的情况。Extra 里还出现了 Using filesort,也是最坏的情况。
2、EXPLAIN列的解释:
- table:显示这一行的数据是关于哪张表的
- type:这是重要的列,显示连接使用了何种类型。从最好到最差的连接类型为const、eq_reg、ref、range、indexhe和ALL
- possible_keys:显示可能应用在这张表中的索引。如果为空,没有可能的索引。可以为相关的域从WHERE语句中选择一个合适的语句
- key: 实际使用的索引。如果为NULL,则没有使用索引。很少的情况下,MYSQL会选择优化不足的索引。这种情况下,可以在SELECT语句中使用USE INDEX(indexname)来强制使用一个索引或者用IGNORE INDEX(indexname)来强制MYSQL忽略索引
- key_len:使用的索引的长度。在不损失精确性的情况下,长度越短越好
- ref:显示索引的哪一列被使用了,如果可能的话,是一个常数
- rows:MYSQL认为必须检查的用来返回请求数据的行数
- Extra:关于MYSQL如何解析查询的额外信息。将在表4.3中讨论,但这里可以看到的坏的例子是Using temporary和Using filesort,意思MYSQL根本不能使用索引,结果是检索会很慢
3、type返回结果的解释
MySQL 在表里找到所需行的方式。包括(由左至右,由最差到最好):
| All | index | range | ref | eq_ref | const,system | null |
- system 表只有一行:system表。这是const连接类型的特殊情况
- const:表中的一个记录的最大值能够匹配这个查询(索引可以是主键或惟一索引)。因为只有一行,这个值实际就是常数,因为MYSQL先读这个值然后把它当做常数来对待
- eq_ref:在连接中,MYSQL在查询时,从前面的表中,对每一个记录的联合都从表中读取一个记录,它在查询使用了索引为主键或惟一键的全部时使用
- ref:这个连接类型只有在查询使用了不是惟一或主键的键或者是这些类型的部分(比如,利用最左边前缀)时发生。对于之前的表的每一个行联合,全部记录都将从表中读出。这个类型严重依赖于根据索引匹配的记录多少—越少越好
- range:这个连接类型使用索引返回一个范围中的行,比如使用>或<查找东西时发生的情况
- index: 这个连接类型对前面的表中的每一个记录联合进行完全扫描(比ALL更好,因为索引一般小于表数据)
- ALL:这个连接类型对于前面的每一个记录联合进行完全扫描,这一般比较糟糕,应该尽量避免
4、extra列返回的描述的意义
- Distinct:一旦MYSQL找到了与行相联合匹配的行,就不再搜索了
- Not exists: MYSQL优化了LEFT JOIN,一旦它找到了匹配LEFT JOIN标准的行,就不再搜索了
- Range checked for each Record(index map:#):没有找到理想的索引,因此对于从前面表中来的每一个行组合,MYSQL检查使用哪个索引,并用它来从表中返回行。这是使用索引的最慢的连接之一
- Using filesort: 看到这个的时候,查询就需要优化了。MYSQL需要进行额外的步骤来发现如何对返回的行排序。它根据连接类型以及存储排序键值和匹配条件的全部行的行指针来排序全部行
- Using index: 列数据是从仅仅使用了索引中的信息而没有读取实际的行动的表返回的,这发生在对表的全部的请求列都是同一个索引的部分的时候
- Using temporary 看到这个的时候,查询需要优化了。这里,MYSQL需要创建一个临时表来存储结果,这通常发生在对不同的列集进行ORDER BY上,而不是GROUP BY上
- Using where 使用了WHERE从句来限制哪些行将与下一张表匹配或者是返回给用户。如果不想返回表中的全部行,并且连接类型ALL或index,这就会发生,或者是查询有问题不同连接类型的解释(按照效率高低的顺序排序)