mysql索引

索引的本质

假设现在有100000条从0到10000且从大到小排列的整型数据，1条数据的大小假设(真的只是假设)是1KB,操作系统的每次I/O数据块(页)大小是8KB。
如果现在我要查找其中 50001 这个数据值，有如下几个方式：
1.最蠢的方式，遍历，每次遍历到一个值，就用这个值跟目标值做对比，如果不等于那么查找下一个。这样的话那么每次I/O是8条数据，目标数据在50001/8 约6600多次I/O 才能找到目标数据。
2.二分查找，最好一次性将100000条数据全部读到内存，这样查找也是很快的。

但是即使二分查找很快，但这些数据也不能单单通过一次I/O全部进入内存，进行运算。
那么怎样在I/O 块大小的限制下快速利用二分查找找到目标值呢？我们得引入新的数据结构，B+树正好可以解决上述I/O块大小的限制，解决限制不是说增大了限制范围，而是我们在此限制上改变了数据的存储结构，即在同等限制条件下，快速检索到目标数据，如下是B+树的原理讲解：

现在我们来看下查找数据 60 的查找过程，如下所示:

1.I/O第一次：读入5、28、65 数据块，在此同级别节点块上，60在28到65之间(其实是二分查找)，那走P2指针指向的子树。
2.I/O第二次：读入28、35、56 数据块，在此同级别节点块上，60大于56，所以走P3指针指向的子树(上图中就是叶子节点)。
3.I/O第三次：读入叶子节点，在这个叶子节点中，使用二分查找算法找到目标值60。
由上述查找过程所示统共需要三次I/O就能查到目标值，性能大大提升。

需要注意的是存储引擎端只会根据主键或者二级索引的值来过滤数据行（当出现覆盖索引的时候，则不需要再回表查询数据行），不会做其他非索引字段的过滤，如果有其他非索引字段的过滤，则需要返回到服务器端再做过滤（查询执行计划中，extra列出现using where）。和客户端从服务器端获取数据的方式类似，服务器端从存储引擎端获取数据也是通过游标的方式逐行获取的

索引类型

B树索引
解析: B树索引是最常见的索引,内部按照顺序存储数据，所以mysql可以用来做order by和group by操作。因为数据是有序的，所以相关的列会存储在一起。最后，因为索引中存储了实际的列值，所以某些查询只是用索引就能够完成全部索引。
限制
如果不是按照索引的最左列开始查找，则无法使用索引
不能跳过索引中的列
如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找
哈希索引
R树索引
全文索引

InnoDB索引构成

InnoDB的索引是一棵B+树,B+树是一个N叉树，N叉树种的N取决于数据块的大小。

为什么要设计成N叉树呢？
对于一个高度20的树来说，一次查询需要访问20个数据块，磁盘每次随机读取一个数据块需要10ms时间的话，访问一行(查20个数据块)可能需要20*10ms的时间。为了让一个查询尽量少的读磁盘，就必须让查询过程访问尽量少的数据块，所以我们不应该使用二叉树，而是N叉树。
简单来说B+树能够很好地配合磁盘的读写特性，减少单次查询的磁盘访问次数。

基于主键索引和普通索引查询的区别

基于主键索引，只需要搜索主键这棵B+树
普通索引查询需要先搜索K索引树，得到ID的值为500，再到ID索引树搜索一次，这个过程称为回表
即非主键索引的查询需要多扫描一棵索引树

一次回表查询的详细流程

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;
insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

索引结构

select * from T where k between 3 and 5语句执行流程:

在k索引树上找到k=3的记录，取得ID=300;
再到ID索引树上查到ID=300对应的R3;
在k索引树上取下一个值k=5,取得ID=500;
再回到ID索引树上查到ID=500对应的R4;
在k索引树去下一个值k=6，不满足条件，循环结束
在这个过程中，回到主键索引树搜索的过程，我们成为回表。在这个查询过程读了k索引树的3条记录(步骤135)，回表2次(步骤2、4)

那么有没有可能经过索引优化，避免回表呢？有的，覆盖索引

如果每一种查询都设计一个索引，索引太多了，有没有什么办法可能尽可能减少浪费？

当你的需求是查到所有”张三”的人时，可以快速定位到ID4，然后向后遍历得到所有需要的结果。

如果你要查的是所有名字第一个字是”张”的人，你的SQL语句的条件是”where name like ‘张%’”。这时，你也能用上这个索引，查到第一个符合条件的记录是ID3，然后向后遍历，直到不满足条件为止。

可以看到只要满足最左前缀，就可以利用索引来加速索引，这个最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

最左前缀可以用于在索引中定位记录，对于不符合最最左前缀的部分，会怎么样呢？

1	mysql> select * from tuser where name like '张 %' and age=10 and ismale=1;

这条语句只能用到”张”，找到第一个满足条件的记录ID3，然后呢？

在Mysql5.6之前，只能从ID3开始一个个回表，到主键索引上能找出数据行，在对比字段值
MySql5.6引入的索引下推优化(index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数

无索引下推执行流程

有索引下推执行流程

第一幅图中，InnoDB不会看age值，只是按顺序把”name第一个字是’张’”的记录一条条取出来回表。因此，需要回表4次。
第二幅图中，InnoDB在(name,age)索引内部就判断了age是否等于10，对于不等于10的记录，直接判断并跳过。着我们的这个例子中，只需要对ID4、ID5这两条记录回表取数据判断，就只需要回表2次。

高性能索引策略

独立的列

独立的列意味着索引列不能是表达式的一部分，也不能是函数的参数。

1 2	select id from user where id+1=5; select ... where to_days(current_date) - to_days(date_col) <=10

同样需要注意where条件的值类型。

1
2
3

name varchar(10),在name上创建索引
select * from user where name = 1;      不走索引，相当于是对name通过函数做了类型转换，所以无法走索引
select * from user where name = "1";    走索引

索引列值避免为null

Mysql难以优化引用了null列的查询。

前缀索引和索引选择性

前缀索引是一种能使索引更小、更快的有效方法
缺点: Mysql无法使用前缀索引做order by 和group by，也无法使用前缀索引做覆盖扫描。
创建前缀索引: alter table user add key(name(7))

索引的选择性: 指不重复的索引值和数据表的记录总数的比值。选择性越高则查询效率越高。

多列索引

ABC创建联合索引，等于A\AB\ABC三个索引

选择合适的索引顺序

聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。innoDB支持聚簇索引，myisam不支持。

一个表只能有一个聚簇索引(覆盖索引可以模拟多个聚簇索引的情况),默认在主键上做聚簇索引，如果没有主键，InnoDB会选择一个唯一的非空索引代替主键做聚簇索引。如果没有这样的索引，innoDB会隐式定义一个主键来作为聚簇索引。

innoDB的聚簇索引在同一个结构中保存了B树索引和数据行;非聚簇索引在叶子结点中保存了索引值及行的主键值，非聚簇索引又叫二级索引。

myisam索引在在叶子结点中保存了索引值和行指针

聚簇索引能最大限度提高i/o密集型应用的性能，但是它有几个限制:

插入速度严重依赖插入顺序，按照主键的顺序插入是最快的方式，否则会导致页分裂，严重影响性能。因此，对于innodb表，我们一般定义一个自增的id列作为主键。
更新主键的代价很高，因为将会导致被更新的行移动。因此，对于innodb表，我们一般定义主键为不可更新。
二级索引的叶结点保存的是主键值而不是行指针，这是为了减少当出现行移动或数据页分裂时二级索引的维护工作，但会让二级索引占用更多的空间

表数据

Myisam存储引擎索引

Myisam是按值和行号来组织索引的。它的叶子结点中实际保存了指向存放数据的物理块的指针。从Myisam的物理文件来看，Myisam引擎索引文件.MYI和数据文件.MYD是相互独立的。

InnoDB存储引擎聚簇索引

InnoDB聚簇索引叶子结点中保存了主键值、事务id、回滚指针(用于事务和MVCC)和余下的列。

InnoDB存储引擎二级索引

InnoDB的二级索引与主键索引有很大不同，InnoDB的二级索引叶子结点包含主键值而不是行指针，这减小了移动数据或数据页面分裂时维护二级索引的开销，因为InnoDB不需要更新索引的行指针。

二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。

根据聚簇索引的原理不难发现，如果用户的查询是使用二级索引进行范围检索的时候（实际情况中很大部分查询是这种情况），如果结果没有命中查询缓存的话，势必会造成大量的磁盘随机IO访问。因为对二级索引进行范围检索得出的一级索引本身是无序的，再根据一级索引去检索数据行就会出现对磁盘的大量随机IO操作。

InnoDB会使用一种叫Multi-Range Read的优化方式，来降低随机IO的读取。其原理就是先将二级索引范围检索得到的一级索引放入缓存进行排序，在回表的时候就用有序的一级索引进行查找，从而将大量的随机IO转换成顺序IO。这个缓存的大小受限于系统变量read_rnd_buffer_size的大小，这个系统变量是客户端级别的，对其调整需要谨慎。

INNODB和MYISAM的主键索引与二级索引的对比：

覆盖索引

如果一个索引包含所有需要查询的列，我们称之为覆盖索引。这是一种查询策略，InnoDB或Myisam都可以使用覆盖索引。

使用覆盖索引时mysql直接使用索引返回需要的数据，无需回表反查。
由于innoDB使用聚簇索引，所以覆盖索引对InnoDB表特别有用。innoDB的二级索引在叶子结点中保存了行的主键，所以如果能覆盖查询，同样十分有效。这句话我的理解是可以利用二级索引查询到主键值，然后利用聚簇索引查询行数据，即延迟关联。

当使用覆盖索引时，explain中的Extra列可以看到using index信息

表t有id A B C 三个字段
在ABC上有联合索引
第一种情况: select A from t where A=1 and B=2 and C=3
1   SIMPLE  t   NULL    ref idx idx 775 const,const,const   1   100.00  Using index
结果: type是ref，而且用到了覆盖索引
第二种情况: select * from t where A=1 and B=2 and C=3
1   SIMPLE  t   NULL    ref idx idx 775 const,const,const   1   100.00  NULL
结果: type是ref，但extra是NULL 没有用到覆盖索引，(个人认为是通过索引拿到了主键，然后通过主键再回聚簇索引查询)
第三种情况: select A from t where B=2 and C=3
1   SIMPLE  film_copy   NULL    index   NULL    idx 775 NULL    1001    1.00    Using where; Using index
结果: type是index，extra是Using where;Using index,type是index表示超级慢
总结
* 过滤条件用到的索引如果覆盖所有查询字段，则使用覆盖索引Using index
* 如果查询字段中包含非索引字段，则不能使用覆盖索引

使用索引扫描来做排序

在mysql中，有两种方式生成有序结果集。

filesort
按索引顺序扫描

利用索引排序是非常快的，而且可以利用同一索引同时进行查找和排序。

当索引的列顺序和order by列顺序一致且所有列的排序方向一致(正序或倒序)时，可以使用索引来排序。
如果查询需要关联多张表，则只有order by子句引用的字段全部为第一个表时，才能使用索引做排序。
有一个特殊情况也可以使用排序，就是前导列为常量的时候，如果where子句或join子句中对这些列指定了常量，就可以填补并使用索引。

//索引是shop_id,goods_id,pay_type
select ... order by shop_id,goods_id,pay_type
select ... order by shop_id desc,goods_id desc,pay_type desc
select ... where shopid = 1 order by goods_id,pay_type   //特殊情况
以下不可以
select ... where shop_id>1 order by goods_id,pay_type

当mysql不能使用索引进行排序时，就会利用自己的排序算法(快排)在内存(sort buffer)中对数据进行排序，如果内存装不下，mysql会将磁盘上的数据分块，再对各个块排序，最后合并成有序的结果集(实际上就是外排)。

联合索引

联合索引是以索引的第一个字段建立的一棵B+树，其中叶子结点中的数据按照字段顺序依次排列(遵循最左原则)

在age,name,country上建立联合索引

如果执行
select * from student where name = 'Alice' and country = 'Canada'
或
select * from student where country = 'Canada'
时，无法使用索引。因为联合索引是先根据年龄进行排序的，如果年龄没有先确定，直接对name或country进行查询，就相当于乱序查询一样，因此索引无法生效，只能全表查询。
select * from student where age = 15 and country = 'Canada'
其中age部分索引有效，country部分无效，也就是说索引部分有效,5.6之后也会用到icp
select * from student where age=15 and name = 'Alice' and country = 'Canada'
先查到age等于15的数据，再顺序查询name为Alice，country为Canada的数据，索引有效。

参考1
参考2

延迟关联

延迟关联: 通过使用覆盖索引返回查询所需主键，再根据主键关联原表获取数据

表t有abcdef四个字段，其中a是主键，cbd上建有联合索引
select * from t where a = 1 and b = 2
这条语句无法使用索引，可以通过延迟关联调整为
select * from t where id in (select id from t  where a = 1 and b = 2)

索引与锁

innodb仅对需要访问的行加锁，而索引能够减少访问的行数。但是只有在存储引擎层过滤掉那些不需要的数据才能达到这种目的。一旦索引不允许innodb这么做（即达不到过滤的目的），mysql服务器只能对innodb返回的数据进行where操作，此时已经无法避免对这些行加锁了，因为innodb已经锁住了这些行，服务器是无法结果的。

innodb一般都是行锁，这个一般指的是sql用到索引的时候，行锁是加在索引上的，不是加在数据记录上的，如果sql没有用到索引，仍然会锁定表

1	select actor_id from actor where actor_id <4 and actor_id <>1 for update

该查询仅仅返回了2-3的数据，但实际上对1-3都加了锁。innodb锁住行1是因为使用了范围查询，where中的第二个条件已无法使用索引

索引扩展（Index Extension）

是InnoDB存储引擎针对二级索引的一个优化，存储引擎内部会对这个索引进行扩展，将一级索引对应的列自动添加到二级索引后面，从而生成更高效的查询执行计划，提高性能。

索引下推（Index Condition Pushdown）

是针对二级索引的另一个优化。
icp全称Index Condition Pushdown。当使用icp时可以有效降低server层和engine层之间交互的次数，从而有效降低运行时间。

5.6 之前，在 SQL 语句的执行过程中，server 层通过 engine 的 api 获取数据，然后再进行 where_cond 的判断，每一条数据都需要从engine层返回server层做判断。

5.6 之后，在利用索引扫描的过程中，如果发现 where_cond 中含有这个 index 相关的条件，则将此条件记录在 handler 接口中，在索引扫描的过程中，只有满足索引与handler接口的条件时，才会返回到 server 层做进一步的处理，在前缀索引区分度不够，其它字段区分度高的情况下可以有效的减少 server & engine之间的开销，提升查询性能。

1
2
3

ABC上建立联合索引
select ... from table where a=xx and c>xx
explain发现a利用到部分索引，C则通过ICP来进行过滤

ICP使用限制

只支持select语句
5.6及以上版本
不支持主建索引的 ICP
ICP的优化策略可用于range、ref、eq_ref、ref_or_null 类型的访问数据方法

MySQL · 特性分析 · Index Condition Pushdown (ICP)

Explain优化

select_type: SIMPLE — 查询类型（简单查询,联合查询,子查询）

table: user — 显示这一行的数据是关于哪张表的

type: range — 区间索引（在小于1990/2/2区间的数据),这是重要的列,显示连接使用了何种类型。从最好到最差的连接类型为system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL,const代表一次就命中,ALL代表扫描了全表才确定结果。一般来说,得保证查询至少达到range级别,最好能达到ref。

possible_keys: birthday — 指出MySQL能使用哪个索引在该表中找到行。如果是空的,没有相关的索引。这时要提高性能,可通过检验WHERE子句,看是否引用某些字段,或者检查字段不是适合索引。

key: birthday — 实际使用到的索引。如果为NULL,则没有使用索引。如果为primary的话,表示使用了主键。

key_len: 4 — 最长的索引宽度。如果键是NULL,长度就是NULL。在不损失精确性的情况下,长度越短越好

ref: const — 显示哪个字段或常数与key一起被使用。

rows: 1 — 这个数表示mysql要遍历多少数据才能找到,在innodb上是不准确的。

Extra: Using where; Using index — 执行状态说明,这里可以看到的坏的例子是Using temporary和Using filesort

extra字段

system: 表中还有一条数据。这个类型是特殊的const类型
const: 针对主键或唯一索引的等值查询扫描，最多只返回一行数据。const速度非常快，因为仅读取了一次。
using index: 使用了覆盖索引
eq_ref: 最多只返回一条符合条件的记录。使用唯一性索引或主键查找时会发生（高效）
ref: 此类型通常出现在多表的join查询，针对非唯一或非主键索引，或者是使用了最左前缀规则索引的查询
range: 表示使用索引范围查询
index: 全索引扫描，和ALL类似，只不过ALL是全表扫描，而index则是扫描所有索引
ALL: 完全表扫描
using where: 表示数据从存储引擎返回服务层后再用where过滤
using filesort: 文件排序，需要优化
using temporary: 使用临时表，需要优化