MySQL系列一（索引、常见索引类型、索引下推、回表、聚簇索引与非聚簇索引、索引的数据结构B+树、索引失效的场景）_非聚簇索引回表

mysql数据（包括索引）存储在磁盘，而一般查询数据的性能问题主要是IO问题，提高IO效率的关键问题主要是减少磁盘IO次数和IO的量

局部性原理：数据和程序都有聚集成群的倾向，同时之前被访问过的数据很可能再次被查询，空间局部性和时间局部性。
磁盘预读：内存跟磁盘发生交互的时候，一般情况下有一个最小的逻辑单元，称为页（datapage），页一般由操作系统决定是多大，一般是4k或者8k，而我们在进行数据交互的时候，可以取页的整数倍来进行读取，InnoDB存储引擎每次读取数据，读取16k。

1. 索引

索引本质上是一种可以可以加快检索速度的、排好序的数据结构。索引运用在表中某些字段上，存储索引需要单独占据一定的空间。

1.1 索引的优缺点

索引的优点：

• 索引加快了数据库的检索速度，避免进行全表扫描，这也是创建索引的最主要的原因。
• 如果索引的数据结构是B+树，在使用分组和排序时，可以显著减少查询中分组和排序的时间。
• 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

索引的缺点：

• 当对表中的数据进行增加、删除和修改时，索引也要进行更新，维护的耗时随着数据量的增加而增加。
• 索引需要占一定的物理空间

1.2 索引的使用场景

在哪些列上面创建索引：

• WHERE子句中经常出现的列上面创建索引，加快条件的判断速度。
• 按范围存取的列或者在group by或order by中使用的列，因为索引已经排序，这样可以利用索引加快排序查询时间。
• 经常用于连接的列上，这些列主要是一些外键，可以加快连接的速度；
• 作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；

不在哪些列建索引？

• 只有很少数据值的列不应该增加索引。由于这些列的取值很少，例如性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。
• 在查询中很少的列不应该创建索引。由于这些列很少使用到，但增加了索引，反而降低了系统的维护速度和增大了空间需求。
• 当添加索引造成修改成本的提高 远远大于 检索性能的提高时，不应该创建索引。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。
• 定义为text, image和bit数据类型的列不应该增加索引。这些列的数据量要么相当大，要么取值很少。

1.3 索引的三种常见底层数据结构以及优缺点

三种常见的索引底层数据结构：分别是哈希表、有序数组和搜索树。

• 哈希表这种适用于等值查询的场景，比如 memcached 以及其它一些 NoSQL 引擎，不适合范围查询。
• 有序数组索引只适用于静态存储引擎，等值和范围查询性能好，但更新数据成本高。
• N 叉树由于读写上的性能优点以及适配磁盘访问模式以及广泛应用在数据库引擎中。
• 扩展（以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。）

2. 常见索引类型

常见的索引类型有：普通索引、唯一索引、主键索引、全文索引、组合索引。

2.1 普通索引

最基本的索引，没有任何限制；

--直接创建索引：
CREATE INDEX index_name ON table(column(length);
 
--修改表结构的方式添加索引：
ALTER TABLE table_name ADD INDEX index_name ON (column(length));
 
--创建表的时候同时创建索引：
CREATE TABLE ‘table’(  
ID INT NOT NULL,   
username VARCHAR(16) NOT NULL,  
INDEX [indexName] (username(length))  
);  
1
2
3
4
5
6
7
8
9
10
11
12

2.2 唯一索引

与普通索引类似，但索引列的值必须唯一，允许有空值，可以有多个NULL值。如果是组合索引，则列值的组合必须唯一，创建方法和普通索引类似。

--创建唯一性索引：
CREATE UNIQUE INDEX indexName ON mytable(username(length));
 
--修改表结构：
ALTER TABLE table_name ADD UNIQUE indexName ON (column(length));
 
--创建表的时候指定：
CREATE TABLE mytable(  
ID INT NOT NULL,   
username VARCHAR(16) NOT NULL,  
UNIQUE [indexName] (username(length))
);  
1
2
3
4
5
6
7
8
9
10
11
12

2.3 主键索引

可以理解为一种特殊的唯一索引，不允许有空值

--创建表的时候创建，当把某个列设为主键的时候,数据库会自动的创建一个以主键作为名称的主键索引。
CREATE TABLE table(
id INT PRIMARY KEY AUTO_INCREMENT,
NAME VARCHAR(32) NOT NULL)
);
 
--修改表结构：
ALTER TABLE `table_name` ADD PRIMARY KEY ( `col` );
1
2
3
4
5
6
7
8

2.4 全文索引（仅可用于 MyISAM 表）

全文索引仅可用于 MyISAM 表，并只支持从CHAR、VARCHAR或TEXT类型，用于替代效率较低的like 模糊匹配操作，而且可以通过多字段组合的全文索引一次性全模糊匹配多个字段。对于大容量的数据表，生成全文索引是一个非常消耗时间和硬盘空间的做法。对于较大的数据集，将你的数据输入一个没有FULLTEXT索引的表中，然后创建索引，其速度比把数据输入现有FULLTEXT索引的速度更为快。

全文索引使用B树存放索引数据，但使用的是特定的算法，将字段数据分割后再进行索引（一般每4个字节一次分割），索引文件存储的是分割前的索引字符串集合，与分割后的索引信息，对应Btree结构的节点存储的是分割后的词信息以及它在分割前的索引字符串集合中的位置。

–创建表的适合添加全文索引
CREATE TABLE `table` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` char(255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL ,
`content` text CHARACTER SET utf8 COLLATE utf8_general_ci NULL ,
`time` int(10) NULL DEFAULT NULL ,
PRIMARY KEY (`id`),
FULLTEXT (content)
);
 
–修改表结构添加全文索引
ALTER TABLE article ADD FULLTEXT index_content(content);
 
–直接创建索引
CREATE FULLTEXT INDEX index_content ON article(content);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.5 联合索引、索引下推、回表

多个字段共同组成的索引，使用时需匹配最左匹配原则。

--创建组合索引：
ALTER TABLE `table_name` ADD INDEX index_name (col1(length), col2(length), col3(length));
1
2

索引下推：MySQL 5.6 引入的索引下推优化（Index Condition Pushdown，简称ICP)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。like KK%其实就是用到了索引下推优化。

例如对于辅助的联合索引(name,age,position)，正常情况按照最左前缀原则，SELECT * FROM employees WHERE name like ‘LiLei%’ AND age = 22 AND position =‘manager’ 这种情况只会走name字段索引，因为根据name字段过滤完，得到的索引行里的age和position是无序的，无法很好的利用索引。

在MySQL5.6之前的版本，这个查询只能在联合索引里匹配到名字是 ‘LiLei’ 开头的索引，然后拿这些索引对应的主键逐个回表，到主键索引上找出相应的记录，再比对age和position这两个字段的值是否符合。MySQL 5.6引入了索引下推优化，可以在索引遍历过程中，对索引中包含的所有字段先做判断，过滤掉不符合条件的记录之后再回表，可以有效的减少回表次数。使用了索引下推优化后，上面那个查询在联合索引里匹配到名字是 ‘LiLei’ 开头的索引之后，同时还会在索引里过滤age和position这两个字段，拿着过滤完剩下的索引对应的主键id再回表查整行数据。索引下推会减少回表次数，对于innodb引擎的表索引下推只能用于二级索引，innodb的主键索引（聚簇索引）树叶子节点上保存的是全行数据，所以这个时候索引下推并不会起到减少查询全行数据的效果。

回表：当查询的数据在索引树中找不到的时候，需要回到主键索引树中去获取，这个过程叫做回表。

为什么范围查找Mysql没有用索引下推优化？
估计应该是Mysql认为范围查找过滤的结果集过大，like KK% 在绝大多数情况来看，过滤后的结果集比较小，所以这里Mysql选择给 like KK% 用了索引下推优化，当然这也不是绝对的，有时like KK% 也不一定就会走索引下推。

2.6 覆盖索引

覆盖索引是select的数据列只用从索引中就能够取得，不必回表，换句话说，查询列要被所建的索引覆盖。 覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

2.7 聚簇索引与非聚簇索引

在MySQL中，聚簇索引和非聚簇索引的概念与一般的数据库系统相似，但是MySQL中的实现方式有一些特定的特点。

• 聚簇索引（Clustered Index）在MySQL中称为主键索引（Primary Key Index）。主键索引是一种特殊的聚簇索引，它将数据按照主键的顺序进行排序，并且将数据行存储在磁盘物理上相邻的位置。主键索引在MySQL中是默认创建的，如果没有显式地指定主键，MySQL会根据表的定义自动创建一个隐藏的主键。 主键索引对于频繁地按照主键进行查询非常高效，因为相关的数据行存储在物理上相邻的位置。
• 非聚簇索引（Non-Clustered Index）在MySQL中称为辅助索引（Secondary Index）。辅助索引是基于表的列创建的独立的索引结构，它包含了索引键值和对应的行指针。与主键索引不同，辅助索引的数据行并不直接存储在索引的叶子节点中，而是通过行指针指向实际的数据行。辅助索引可以在一个表上创建多个，并且可以在任意列上创建辅助索引。

在MySQL中，辅助索引的选择性是一个重要的因素。选择性指的是索引键值的唯一性，即索引键值的不重复程度。具有高选择性的辅助索引可以更有效地缩小搜索范围，从而提高查询性能。

需要注意的是，MySQL InnoDB存储引擎中的表默认使用聚簇索引（主键索引）来组织数据，即数据行按照主键的顺序进行排序。 而其他存储引擎，如MyISAM存储引擎，没有聚簇索引的概念，它使用B树索引来组织数据。在使用MyISAM引擎的表中，可以通过创建辅助索引来加速查询操作。

综上所述，MySQL中的聚簇索引即主键索引，将数据按照主键顺序进行排序和存储；非聚簇索引即辅助索引，基于表的其他列创建的独立索引结构，通过索引键值和行指针来加速查询操作。

聚簇索引一般在下面场景使用：
（1）主键列，InnoDB存储引擎中，默认为表的主键建立一个聚簇索引。
（2）按范围存取的列或者在group by或order by中使用的列。在聚簇索引下，因为表中数据存储的物理顺序与索引的逻辑顺序一致，所以在包含范围检查(between、<、<=、>、>=)或使用group by或order by的查询时，一旦找到具有范围中第一个键值的行，具有后续索引值的行保证物理上毗连在一起而不必进一步搜索，避免了大范围扫描，可以大大提高查询速度。
（3）在连接操作中使用的列。
（4）不经常修改的列。因为码值修改后，数据行必须移动到新的位置。

数据存储文件和索引文件是分开的。物理顺序与索引顺序不相同，可以有多个，小于249个；

3. 索引的数据结构

常见的索引的数据结构有：B+Tree、Hash索引。

3.1 B+Tree索引

B+Tree是MySQL中使用最频繁的索引数据结构。是Innodb和Myisam存储引擎模式的索引类型。相对Hash索引，B+Tree索引在查找时需要从根节点到叶节点进行多次IO操作，在查询速度比不上Hash索引，但是更适合排序等操作。

为什么选择 B+ 树

• 二叉树：最坏的情况下会成为一个链表，会成为顺序查找。相同的数据量下树比较高。**树越高就意味着需要更多次的磁盘访问。
• 红黑树：一个节点只有一个key（关键字），不适合大数据量的存储（2的n次方=N,n为层数），磁盘IO次数还是较大。
• 哈希索引虽然能提供O（1）复杂度查询，但对范围查询和排序却无法很好的支持，最终会导致全表扫描。 MySQL中，只有Memory存储引擎支持hash索引，是Memory表的默认索引类型。hash索引把数据以hash值形式组织起来，因此检索效率非常高，可以一次定位。
  • Hash索引仅能满足等值的查询，不能满足范围查询、排序。因为数据在经过Hash算法后，其大小关系就可能发生变化。
  • 当创建组合索引时，不能只适用组合索引的部分列进行查询。因为hash索引是把多个列数据合并后再计算Hash值，所以对单独列数据计算Hash值是没有意义的。
  • 当发生Hash碰撞时，Hash索引不能避免表数据的扫描。因为仅仅比较Hash值是不够的，需要比较实际的值以判定是否符合要求。
• B 树能够在非叶子节点存储数据，但会导致在查询连续数据可能带来更多的随机 IO。
• B+ 树的所有叶节点可以通过指针来相互连接，减少顺序遍历带来的随机 IO。

二叉树

• 最坏的情况下会成为一个链表，会成为顺序查找。相同的数据量下树比较高。树越高就意味着需要更多次的磁盘访问。

红黑树

• 一个节点只有一个key（关键字），不适合大数据量的存储（2的n次方=N,n为层数），磁盘IO次数还是 较大。

Hash表

• 对索引的key进行一次hash计算就可以定位出数据存储的位置
• 很多时候Hash索引要比B+树索引更高效
• 仅能满足“=”、“IN”，不支持范围查询
• hash冲突问题

B-Tree

• 叶子结点具有相同的深度，叶子结点的指针为空
• 所有索引元素不重复
• 结点中的数据索引从左到右递增排列

B+Tree（B-Tree变种）

• 非叶子结点不存储数据，只存储索引（冗余），可以放更多的索引
• 叶子结点包含所有索引字段
• 叶子结点用指针连接，提高了区间访问的速度

3.2 MyISAM和InnoDB索引实现

注：存储引擎最小是表级别的，不同的表可以有不同的存储引擎。

MyISAM存储引擎中索引是非聚集索引

• 即数据存储文件和索引文件是分开的（.MYI和.MYD文件），使用B+Tree作为索引结构
• 叶子节点保存了索引和数据记录的地址

InnoDB存储引擎中索引是聚集索引

• 索引和数据存储在同一个文件中（.idb文件），表数据文件本身就是按B+Tree组织的一个索引结构
• 叶子节点保存了索引和完整的数据记录。
• InnoDB只有一个聚集索引，就是主键索引。

为什么非主键索引结构叶子结点存储的是主键值？数据冗余、减少数据维护

• 数据冗余：虽然提升了查询性能，但是需要更多的空间来存储冗余的数据。
• 维护麻烦：一个地方修改数据，需要在多棵索引树上修改。

为什么InnoDB表必须有主键？？

• 创建主键就会自动创建主键索引，主键索引是聚集索引，聚集索引将索引和完整的记录数据放在同一个B+Tree中文件中，减少了磁盘IO次数。

为什么推荐使用整型的自增主键？

• B+Tree中有一个指向指针指向关键字最小的叶子结点，所有叶子结点链接成一个单链表。所以如果主键为自增主键，插入数据时会直接在链表的尾部插入，效率高并且实现简单。如果是非自增的，B+Tree发生分裂的概率就会增大。

3.3 联合索引的底层存储结构、最左匹配原则

按照联合索引的键值顺序排序的索引。

mysql建立联合索引时会遵循最左前缀匹配的原则，即最左优先，在检索数据时从联合索引的最左边开始匹配，示例：对列col1、列col2和列col3建一个联合索引

CREATE INDEX test_col1_col2_col3 ON test(col1,col2,col3);
1

联合索引 test_col1_col2_col3 实际建立了(col1)、(col1,col2)、(col,col2,col3)三个索引。

SELECT * FROM test WHERE col1=“1” AND clo2=“2” AND clo4=“4”
上面这个查询语句执行时会依照最左前缀匹配原则，检索时会使用索引(col1,col2)进行数据匹配。

创建联合索引时列的选择原则（参考博客创建联合索引时列的选择原则）：

• 经常使用的列优先
• 离散度高的列优先
• 宽度小的列优先

列的离散性计算：count（distinct col）/ count(col)
例如：
id列一共9列都不重复 9/9 = 1
性别列一共9列只有（男或者女）两列 2/9 约等于0.2
离散性越高选择性越大

4. 索引失效的场景

对索引使用左或者左右模糊匹配，也就是 like %xx 或者 like %xx% 这两种方式都会造成索引失效。原因在于查询的结果可能是多个，不知道从哪个索引值开始比较，于是就只能通过全表扫描的方式来查询。：

select * from doc where title like ‘%XX’； --不能使用索引
select * from doc where title like ‘XX%’； --非前导模糊查询，可以使用索引

反向条件不走索引：负向条件有：!=、<>、not in、not exists、not like 等

select * from doc where status != 1 and status != 2; --不能使用索引
select * from doc where status in (0,3,4); --优化为 in 查询，可以使用索引

IS NULL、IS NOT NULL 在无法使用索引，不过在mysql的高版本已经做了优化，允许使用索引

在索引列做任何操作（计算、函数、表达式）会导致索引失效而转向全表扫描

select * from doc where YEAR(create_time) <= ‘2016’; – 不能使用索引
select * from doc where create_time<= ‘2016-01-01’; – 可以使用索引
select * from order where date < = CURDATE()； – 不能使用索引
select * from order where date < = ‘2018-01-2412:00:00’; – 可以使用索引
select id from t where substring(name,1,3)=’abc’ – 不能使用索引
select id from t where name like ‘abc%’ – 可以使用索引
select id from t where num/2=100 – 不能使用索引
select id from t where num=100*2 – 可以使用索引

强制类型转换会导致全表扫描 ：字符串类型不加单引号会导致索引失效，因为mysql会自己做类型转换,相当于在索引列上进行了操作。

select * from user where phone=13800001234; – 不能使用索引
select * from user where phone=‘13800001234’; – 可以使用索引

使用联合索引时，要符合最左前缀原则，否则会不走索引： ：组合索引的字段数不允许超过5个。如果在a,b,c三个字段上建立联合索引 index(a,b,c)，那么他会自动建立 a、(a,b)、(a,b,c) 三组索引。

• 建立联合索引的时候，区分度最高的字段在最左边：
• 存在等号和非等号混合判断条件时，在建立索引时，把等号条件的列前置，如 where a > ? and b= ?，那么即使 a 的区分度更高，也必须把 b 放在索引的最前列。
• 最左前缀查询时，并不是指SQL语句的where顺序要和联合索引一致，但还是建议 where 条件的顺序和联合索引一致。
• 假如index(a,b,c), where a=3 and b like ‘abc%’ and c=4，a能用，b能用，c不能用。