系列
MySQL实战45讲阅读笔记-MySQL入门
MySQL实战45讲阅读笔记-日志
MySQL实战45讲阅读笔记-锁
MySQL实战45讲阅读笔记-索引
MySQL实战45讲阅读笔记-MVCC

索引用于快速查找具有特定值的行。如果没有索引，MySQL必须从第一行开始，然后读取整个表以查找相关行。表越大，成本越高。如果表中有相关​​列的索引，MySQL可以快速确定要在数据文件中间寻找的位置，而无需进行全表扫描，这比按顺序读取每一行要快得多。

索引模型

B Tree是一种平衡多叉树，是为了磁盘或其它存储设备而设计的一种多叉平衡查找树；为什么这么说呢；磁盘的最小存储单位是扇区(sector)，而操作系统的块(block)通常是整数倍的sector，操作系统以页(page)为单位管理内存，一页(page)通常默认为4K，数据库的页通常设置为操作系统页的整数倍；数据库操作是以数据页为基本单位进行操作的，读取某一行数据时是去寻找该行所在的页，然后把这整个数据页(一般数据页大小为16k，可以查询Innodb_page_size)加载进内存里面，所以说加载的内存页的数量决定了加载速度；B Tree相比其他的数据模型例如平衡二叉树，它的树高远远小于平衡二叉树，树高小意味着IO次数少，每个节点保存的数据也远多于二叉树，这就意味着访问一次磁盘访问能加载更多的内存页；

B-Tree

B树对比平衡二叉树来看，每个节点允许有更多的子节点，每个节点都可以储存数据；
B树具有以下的特点：

• 每个节点都储存尽量多的数据，保证树的层级尽量的少；
• 查找时有可能在非叶子节点结束，查找性能接近二分查找算法；

B+Tree

相比于B树，B+树的所有数据都储存在叶子节点，非叶子节点只储存关键字，各叶子节点指针进行连接；
因为B+树所有数据都储存在叶子节点，所以在查找关键字的时候一次性加载进内存的关键字就越多(因为非叶节点不保存数据，每次能加载的key更多)，相对来说读取IO的次数就越少；每次查询的路径长度都是相同的所以查询效率相当，因为叶子节点连接起来了，可以实现遍历叶子节点就完成整个树的遍历，这样在范围查询的时候效率较高；

Innodb索引

Innodb索引类型分为主键索引和非主键索引，主键索引也称为聚簇索引，叶子节点储存的是整行的数据；非主键索引也称二级索引，叶子节点储存的是数据页；Innodb的索引和数据都是存储在一个文件中的，不像MyISAM索引文件和数据文件是分离，索引文件只保存数据的地址；

假如一个表结构是下面这个样的

mysql> create table test(
id int primary key, 
age int not null, 
name varchar(16),
index (age))engine=InnoDB;

那么对应的索引树大概是这样子的

二级索引树储存的内容是对应的主键，聚簇索引节点存储的是数据页，所以一般情况下用二级索引查询效率没有主键查询效率高；B+树索引并不能找到具体的某一行，只能定位到具体的数据页，把数据页加载到内存后再通过二分查找法查找；

为了保证索引的有序性，在插入数据的时候可能会对树做一些调整，如果现在要添加一个id为7的数据，直接添加在5的屁股后面就好了，但是又再添加一个id为6的数据的时候则需要在逻辑上挪动5后面的数据，这时不巧5所在的数据页满了，按照B+树的算法这时需要申请一个数据页，然后挪动部分数据过去，这种情况称为页分裂，同时一个页的数据分为了两个页，整体的利用率下降了大约50%；
当然有分裂就有合并，当相邻的两个数据页利用率很低的时候会将数据页合并；
所以推荐建表用自增主键，这样插入数据的时候都是追加操作，能带来较好的性能；还有主键若是占用的字节较小的话，二级索引占用的空间也越小，因为二级索引节点的内容是主键；

覆盖索引

在查询的时候在二级索引树找到主键再回溯主键索引树称为回表；而直接在二级索引树上面查找到数据则称为覆盖索引，因为少了回溯这一步骤，减少了树的搜索次数，查找性能有效的提高；

最左前缀匹配原则

当表中有联合索引时，比如有一个表test是下面这个样子

CREATE TABLE `test` (
  `id` int(11) NOT NULL,
  `age` int(11) NOT NULL,
  `name` varchar(16) DEFAULT NULL,
  `pwd` varchar(16) DEFAULT NULL,
  `email` varchar(16) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `name` (`name`,`age`,`pwd`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

现在需要查询的语句中包含name字段的时候是用到了索引的

explain select * from test where name = 'ss' and age = 10 and pwd = 'ss';
+----+-------------+-------+------------+------+---------------+------+---------+-------------------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref               | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+-------------------+------+----------+-------+
|  1 | SIMPLE      | test  | NULL       | ref  | name          | name | 42      | const,const,const |    1 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+------+---------+-------------------+------+----------+-------+

但是如果只使用pwd字段查找时

explain select * from test where pwd = 'ws'
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | test  | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+

可以看到并没有使用到索引，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配；最左前缀可以是联合索引的最左N个字段，也可以是最左M个字符；

• 什么时候索引会失效
  1. where条件中有or，即使其中有条件带索引也不会使用；如果要想使用or又想让索引生效，只能将or条件中的每个列都加上索引；
  2. 对于多列索引，不是使用的第一部分，则不会使用索引（即不符合最左前缀原则）；
  3. like查询是以%开头；
  4. 如果列类型是字符串，那一定要在条件中将数据使用引号引用起来，否则不使用索引；
  5. 如果mysql估计使用全表扫描要比使用索引快，则不使用索引；

索引下推(Index Condition Pushdown)

在Mysql5.6以后引入了索引下推优化，可以在索引遍历过程中对索引所包含的字段先做判断，直接过滤不满足的条件，旨在减少回表次数和减少MySQL server层和引擎层的交互次数；

select * from test where name like 's%' and age = 19;

根据最左前缀原则，上面查询语句只能用到's%'这个条件来搜索索引树

Innodb在name,age索引树内部就已经判断了age是否等于19，只取需要的数据进行回表；

唯一索引

UNIQUE KEY 可以保证不会出现重复的值( null 除外)，如果能确定某个数据列只能存在彼此各不相同的值，可以使用唯一索引，在插入新数据的时候MySQL会检查这个记录是否存在；

唯一索引查找

如果使用查询语句select * from test where age = 18;，首先根据索引树的根节点开始按层搜索到叶子节点，找到age18所在的数据页，数据页内部通过二分法定位到所在行；

• 对于唯一索引来说，查找到满足第一个符合条件的行就会停止搜索；
• 而对于普通索引来说，查找到满足第一个符合条件的行后还会继续搜索，直到找到第一个不满足条件的行；

因为引擎是按页读取到内存的，意味着如果在数据页内查找一条数据和多条数据的效率是一样的，所以唯一索引和普通索引在查找方面的效率没有什么区别；

唯一索引更新

当需要更新一个数据页的时候，如果数据页在内存中则直接更新，但是数据页不在内存的时候，则会把更新操作缓存在Change Buffer中，下次查询这个数据页的时候就把该页读取到内存中，然后执行Change Buffer中与该页相关的操作，通过这种方式能保证数据逻辑的正确性；

但是对于唯一索引来说，每一次的更新操作都需要判断该记录的唯一性，这就必须要把最新的数据页读取到内存中，再执行insert或update操作；
相比使用Change Buffer，这样做会导致大量的随机IO访问，这就是Change Buffer可以避免很多随机磁盘IO的原因；

所以在业务可以不需要去重或者可以用业务保证数据的唯一性的时候优先使用普通索引；

• ChangeBuffer和RedoLog的关系

假如现在需要执行insert into test(id, name, age) values(1, 'ss', 33), (2, 'sss', 18)，再假如前面所插入的values的数据页1在内存中，而后面的values的数据页2不在内存中；
那么会进行以下操作

1. 在数据页1直接更新(1, 'ss', 33)
2. 因为数据页2不在内存，所以在内存的ChangeBuffer中记录insert into test(id, name, age) values(2, 'sss', 18)
3. 将上面两个动作记录到redo log中；（redolog同样会记录Change Buffer里面的操作）
   完成后事务就可以提交了，这里写了两次内存(数据页1一次，ChangeBuffer一次)，写磁盘一次(redo log写盘)；

读取的时候假如行在数据页1中，直接可以从内存中返回，假如行在数据页2中，则需要把数据页2加载到内存中然后根据Change Buffer里面的日志进行更新后才会读取；

• 写ChangeBuffer时候MySQL异常退出了有什么影响？

如果在ChangeBuffer merge(ChangeBuffer应用到旧数据页得到新数据页的过程称为merge)之后掉电，这部分已经应用到数据页上面，所以不需要进行恢复；
主要是分析没有merge的部分

1. redolog没有完成二阶段提交，处于prepare-fsync阶段，binlog未fsync，这部分数据会丢失；
2. redolog没有完成二阶段提交，redolog已经fsync但是还未commit，binlog已经fsync，这部分数据可以通过binlog恢复redolog，然后通过redolog恢复ChangeBuffer；
3. redolog已经commit，可以直接使用redolog恢复ChangeBuffer；

前缀索引

索引是很方便，但是对于长度过长的字段建立索引是很耗空间的一种操作，所以就有了前缀索引，选取字段的前n个字符建立索引可以有效的缩小索引空间，但是也就意味着查询时通过索引判断的精度会有所变小，扫描的行数会变多；

• 语法

ALTER TABLE table_name ADD KEY(column_name(length));

前缀索引只能用在普通索引上面，且使用了前缀索引就不能使用覆盖索引了，因为系统不确定根据前缀索引查找出来的结果集是否全部满足需求，必须回到主索引树上面再过滤一遍；所以在选择使用前缀索引的时候还是要根据业务来判断是否是最优选项；

MRR优化

Multi-Range Read(MRR)是MySQL5.6版本推出来性能优化，主要功能是对于非聚簇索引查找时将随机IO转换为顺序IO；
因为不能保证二级索引上面储存的主键是顺序排序的，那么再回表的时候读取的数据页可能散落在各个节点上面，势必会造成随机IO读；

MRR的优化就是在回表的过程中，将二级索引树上查找的主键放在一块叫read_rnd_buffer的内存中先保存起来，然后对buffer的主键进行排序，排序后的主键在表中查找时效率就会变高；
buffer的大小由read_rnd_buffer_size参数控制，如果说一次MRR中buffer里面的主键越多那么优化效果也就越好；

MRR只是在范围查询中有效，optimizer_switch中的mrr控制是否使用MRR优化，mrr_cost_based表示优化器是否会计算mrr的使用成本来决定是否使用mrr机制；

Order By

Innodb里面有两种排序的方式，索引排序和filesort排序，所谓的索引排序是依赖B+树结构中数据一定是有序的；而filesort排序则是读出来的数据集需要经过额外的排序操作；

select a, b, c from test where a(非聚簇索引字段)='a' order by b(非索引字段) limit 10000;

上面语句的流程大概是这样的

1. 初始化sort_buffer，sort_buffer是排序时候用到的内存，是每个线程独有的，由参数sort_buffer_size控制大小；(还有一个Innodb_sort_buffer_size参数，这个参数是指在创建innodb索引期间用于对数据排序的排序缓存区大小)
2. 根据索引a找到主键值，回到主索引树上面取出a、b、c和主键的值存入sort_buffer中；
3. 从索引a中继续取下一个主键的值，重复步骤2和3直到找到所有满足的行；
4. 在sort_buffer中对数据按照b做快排；
5. 取排序后的前10000条数据当作结果集返回；

其中如果需要排序的数据小于sort_buffer_size，那么排序可以在内存中完成，如果大于缓存区，则需要借助磁盘的临时文件辅助排序；

使用下面这个方法可以确定一个排序语句是否用到了临时文件

/* 打开 optimizer_trace，只对本线程有效 */
SET optimizer_trace='enabled=on'; 
/* @a 保存 Innodb_rows_read 的初始值 */
select VARIABLE_VALUE into @a from  performance_schema.session_status where variable_name = 'Innodb_rows_read';
/* 执行语句 */
select a, b, c from test where a(非聚簇索引字段)='a' order by b(非索引字段) limit 10000;
/* 查看 OPTIMIZER_TRACE 输出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`
/* @b 保存 Innodb_rows_read 的当前值 */
select VARIABLE_VALUE into @b from performance_schema.session_status where variable_name = 'Innodb_rows_read';
/* 计算 Innodb_rows_read 差值 */
select @b-@a; #得到36764

### 关键部分
"filesort_summary": {
    "rows": 36764,
    "examined_rows": 36764,
    "number_of_tmp_files": 6,
    "sort_buffer_size": 262144,
    "sort_mode": "<sort_key, packed_additional_fields>"
}

number_of_tmp_files表示使用了6个临时文件，examined_rows表示有36764行数据参与排序，packed_additional_fields表示排序过程中对字符串做紧凑处理；

现在执行下面这个语句

SET max_length_for_sort_data = 16;

然后再一次执行一次上面的语句

select @b-@a; #得到46764
"filesort_summary": {
     "rows": 36764,
     "examined_rows": 36764,
     "number_of_tmp_files": 4,
     "sort_buffer_size": 262136,
     "sort_mode": "<sort_key, rowid>"
}

max_length_for_sort_data是控制用于排序行数据的最大长度，假设abc三个字段长度为36，改成16之后不能将abc都装入sort_buffer中，所以MySQL会选择只把主键和将要排序的b字段放入sort_buffer中，所以排序的流程变成了下面这样

1. 初始化sort_buffer，执行器查看表定义，发现abc三个字段长度大于max_length_for_sort_data，确认放入的字段有b和主键字段；
2. 执行器调用储存引擎的查找接口，根据索引a找到主键值，回到主索引树上面取出b的值和主键值存入sort_buffer中；
3. 从索引a中继续取下一个主键的值，重复步骤2和3直到找到所有满足的行；
4. 在sort_buffer中对数据按照b做快排；
5. 遍历排序结果取前10000行并按照主键值回到原表取出abc三个字段返回；

sort_buffer不属于innodb引擎内部，所以需要两次调用innodb引擎的查找接口，这就是方式二innodb读取行数比方式一多1w行的原因；
两种排序各有优缺点，方式一需要创建更多的临时文件，但是查询数据的次数少，方式二则相反；

当然更好的方法就是不使用filesort排序直接使用索引排序，比如建立(city, name, age)的联合索引；

JOIN

多表查询的时候可以使用join关键字，合理的join可以带来较好的性能，但是往往使用不当的情况较多，有些则干脆不推荐使用，像淘宝的阿里巴巴Java开发手册就有一条超过3个表就禁止使用join；到底join该怎么用还是需要了解关于它的基本信息；

JOIN的类型

Cross Join

返回表a和表b的笛卡尔乘积，即是a中所有行*b中所有行；

select * from a cross join b

Inner Join

inner join(内连接)是选取驱动表的数据集去匹配被驱动表的数据集中符合条件的集合；当不存在任何条件时，返回的结果和cross join是一样的， 当使用on ...返回的相当于两个表中符合条件的交集；

select * from a inner join b on condition where ...

当使用join或inner join时，mysql会选择数据量比较小的表作为驱动表，大表作为被驱动表；

Left Join

left join(左连接)查找的结果集包括表a的所有行并显示对应匹配表b的行，对于表a存在而表b不存在的行则显示null；如果要使用left\right join，对于等值判断或不等值判断就只能写到on里不能写在where中；

select * from a left join b on condition where ...

当使用left join时，左表是驱动表，右表是被驱动表；

Right Join

right join和left join相反，显示表b所有行和对应匹配表a的行，不存在则显示null；

select * from a right join b on condition where ...

当使用right join时，右表时驱动表，左表是驱动表；

Join的原理

Join使用的是Nested-Loop Join算法，即是驱动表的数据作为循环主体，然后把符合条件的行再拿去和被驱动表中符合条件的行组成结果集；NLJ算法总共细分了3种类型；

• Simple Nested-Loop Join
  拿驱动表所有的数据去被驱动表逐条匹配查找符合条件的行，每一次去被驱动表查找的时候走的是全表扫描，假设驱动表行数是n，被驱动表行数位m，那么总共扫描的行数为n*m；

• Index Nested-Loop Join
  和上面的相比最大的不同是被驱动表中关联的字段是有索引的，在查找的时候走的是树搜索，一次树查询的时间复杂度为log₂m，如果被驱动表所关联的字段是非聚簇索引的话，还需要回表到主索引树上，那么时间复杂度是2 * log₂m，所以整个查找是驱动表行数n * 2 * log₂m；在explain中发现没有关键字Using join buffer(Block Nested Loop)表明使用的就是NLJ算法；

• Block Nested-Loop Join
  被驱动表上面没有可用索引，那么是不会选择Simple Nested-Loop Join，而是Block Nested-Loop Join；
  会把驱动表的数据逐一放到一个叫做join_buffer的内存中，然后再到被驱动表的每一行数据拿出来到join_buffer中进行比较，符合条件的数据作为结果集返回；
  join_buffer的大小由参数join_buffer_size控制的，如果buffer中不能一次性装下驱动表的数据，则会再buffer装满的时候和被驱动表数据对比，对比完后清空buffer再继续装驱动表的数据，直到完成join；
  和Simple Nested-Loop Join对比这个算法的优势是判断是在内存中完成的，效率较高，join_buffer也是影响join速度的因素之一，越大的buffer，被驱动表被扫描次数就越少，IO次数也就越少；如果被驱动表扫描次数变多，可能会造成Innodb buffer pool中的Young区域被被驱动表的数据页填满，以至于正常访问的热点数据页被淘汰掉影响内存命中率；

• Batched Key Access
  MySQL5.6后引入了BKA算法，是对NLJ算法的优化，NLJ算法时从驱动表中遍历的数据一行行的拿去和被驱动表中匹配，而BKA算法则是从驱动表中拿出来的数据先储存在join_buffer中进行排序，然后使用MRR接口中去被驱动表中查找对应行；BKA算法提升性能的地方在于将原本一行一行的与被驱动表进行对比改成了批量拿去和被驱动表对比，将随机IO转换成了顺序IO；
  如果是多表join，那么每一次join得到的数据集会新增一个join_buffer用来存在下一次join的数据集；
  BNL和BKA都是用到了join_buffer，区别在于BKA用于被驱动表有可用索引的情况下，而BNL是用于被驱动表上没有可用索引；
  启用BKA之前需要启动MRR优化，然后设置set global optimizer_switch = 'batched_key_access=on'；

• Join的优化

1. 用小表做驱动表，尽量减少join语句中的Nested Loop的循环总次数；
2. 对被驱动表的join字段上建立索引；
3. 使用临时表建立索引，把原本被驱动表上的数据插入到临时表中，使用临时表作为被驱动表从而用上索引；
4. 当被驱动表的join字段上无法建立索引的时候，设置足够的Join Buffer Size。

join查询在有索引条件下

• 驱动表有索引不会使用到索引
• 被驱动表建立索引会使用到索引

Group By

Group By主要有3种方式实现

• 松散索引扫描(Loose Index Scan)
  依赖于索引的有序性直接使用索引，且只需扫描部分的索引而不用扫描全部索引，所以称为松散索引扫描；使用松散索引的条件是

  1. 只能单表查询
  2. group by选择的列还满足最左前缀原则且没有其他多余的列，如果有多余的列必须是以常量形式存在；
  3. 使用聚合函数(min、max)的列必须在group by的列里面；
  4. 只能对列的整个值进行group by，比如c varchar(20)，索引必须是index(c(20))而不能是前缀索引如index(c(10))；

• 紧凑索引扫描(Tight Index Scan)
  紧凑索引扫描可以是完整索引扫描也可以是范围索引扫描，如果不满足松散索引扫描的条件，则使用紧凑索引扫描，紧凑索引扫描仍然可以避免使用临时表来进行额外的排序；

• 创建临时表实现Group by
  创建一张内存临时表用来保存这个groupby的所有关联字段然后再在临时表中排序后得到结果集返回给客户端；
  在explain中显示Using index; Using temporary; Using filesort分别表示使用覆盖索引不需要回表，使用临时表和使用filesort排序；如果不需要排序可以在语句后面添加order by null;
  参数tmp_table_size是控制临时表的大小，默认16M，如果大于这个则会在磁盘中创建临时表；

• 优化总结

  1. 尽量使用索引，确保explain中不会出现Using temporary; Using filesort；
  2. 如果group by没有排序要求，在语句后面添加order by null，在使用临时表的时候能避免使用sort_buffer；
  3. 使用临时表时可以适当调大tmp_table_size来满足groupby，避免使用磁盘临时文件；

参考

https://draveness.me/sql-index-intro