Mysql - 索引
Mysql - 索引原理
索引目的
索引的目的在于提高查询效率，可以类比一本字典，如果要查询某个单词，可以先根据单词首字母查询字典目录，然后找到对应的页码，直接翻到指定页码在进行二分查找，提高查询效率。
磁盘IO与预读
磁盘IO是非常高昂的操作，计算机系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也会读取到内存缓冲区，这样可以方便计算机很快访问相邻的数据，这就是磁盘预读。每一次IO读取的数据称之为一页（page）,page大小和操作系统有关，一般为4k或8k。
索引数据结构 B+Tree
为了每次查询数据的时候把磁盘IO次数控制在一个很小的数量级，我们需要一个高度可控的多路搜索树。这就是B+Tree。
image.png
浅蓝色为一个磁盘块，每个磁盘块包含几个数据项（深蓝色）和指针(黄色）,如磁盘块1包含数据项17和35，包含指针P1、P2、P3表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块，真实的数据只存在于叶子节点。非叶子节点只存储指引搜索方向的数据项，而不存真实的数据。如17、35并不真实存在数据表中。
B+Tree的查找过程
比如要查找数据项29，需要先把磁盘块1加载到内存，发生一次IO，在内存中二分查找29在17和35之间，找到磁盘块1的P2指针；然后在通过P2指针在加载磁盘块3到内存，发生第二次IO，内存中二分查找29在26和30之间，锁定磁盘块3的P2指针；通过指针加载磁盘块8到内存，发生第三次IO，同时二分查找到29，结束查询，总计发生三次IO。
B+Tree性质
- 一次查询发生IO的次数取决于B+Tree的高度h,假设当前数据表的数据为N，每个磁盘块的数据项的数量是m,则有h=log(m+1)N,树的高度就是log以m+1为底N的对数，如果m等于1时，也是一个二叉树！当数据量N一定的情况下，m越大则h越小;比如m=1、N=8则h=log(2)8=3；而m=磁盘块大小/数据项的大小；磁盘块大小就是数据页大小，一般为4K或8K，是固定的。所以数据项占空间越小，每个磁盘块存储的数据项就越多，树的高度就越低，查询发生的磁盘ID次数就越少。所以索引字段尽量要小，int占4字节，要比bigint8字节少一半。所以真实的数据要放到叶子节点，如果放在中间节点，会导致树增高。
- 最左匹配特性，B+Tree是按照从左到右的顺序建立搜索树的，
联合索引数据结构
image.png
一个SQL只能利用到联合索引中的其中一列进行范围查找，因为B+Tree的每个叶子节点有一个指针指向下一个节点，把某一索引列的所有叶子节点串在了一起，只能根据单列的叶子节点进行范围查询。
Mysql - 索引原则
- 最左前缀匹配原则，mysql会一直向右匹配直到遇到范围查询（>、<、between、like）就停止匹配，比如 a=1 and b=2 and c>3 and d=4 如果建立了（a,b,c,d)顺序的索引，d是用不到索引的，如果建立（a,b,d,c)的索引则都可以用到，a、b、d的顺序可以任意调整。
- =和in可以乱序，比如 a=1 and b=2 and c=3 建立（a,b,c)索引可以任意顺序，mysql的查询优化器会帮助优化成索引可以识别的形式。
- 尽量选择区分度高的列作为索引，区分度公式count(distinct col)/count(*)，表示字段不重复的比例。
- 索引列不能参与计算，否则索引会失效。
- 尽量扩展索引，不要新建索引。
Mysql - 索引类型
索引主要分为两大类，聚簇索引和非聚簇索引
聚簇索引 (clustered index)
聚簇索引的叶子节点存储行记录，InnoDB必须要有且只有一个聚簇索引：
- 如果表定义了主键，则主键索引就是聚簇索引；
- 如果没有定义主键，则第一个非空的唯一索引列是聚簇索引；
- 如果没有唯一索引，则创建一个隐藏的row-id列作为聚簇索引。主键索引查询非常快，可以直接定位行记录。
非聚簇索引 （secondary index)
InnoDB非聚簇索引的叶子节点存储的是行记录的主键值，而MyISAM叶子节点存储的是行指针。
通常情况下，需要先遍历非聚簇索引获得聚簇索引的主键ID，然后在遍历聚簇索引获取对应行记录。
非聚簇索引需要扫描两遍索引树：又叫回表查询
1、先扫描非聚簇索引根据where条件定位到主键值id=9;
2、再根据主键ID扫描聚簇索引定位到行记录。
回表查询
回表查询就是先定位主键值，在根据主键值定位行记录，需要扫描两遍索引。
解决方案：
只需要在一颗索引树上能够获取SQL所需要的所有列数据，则无需回表查询，速度更快。
常见方法：
将要查询的字段，建立到联合索引里去，这就是索引覆盖。
查询sql在进行explain解析时，Extra字段为Using Index时，则触发索引覆盖。
没有触发索引覆盖，发生了回表查询时，Extra字段为Using Index condition.
索引覆盖进行回表查询优化场景
select id, name, sex from table where name = 'tom'; #单列索引（name）联合索引(name,sex)，可避免回表
select id, name, sex from table order by name limit 5 ,10 # 单列索引（name）联合索引(name,sex)，可避免回表
索引条件下推 （Index Condition Pushdown)
mysql5.6引入了索引下推优化，默认开启，使用 SET optimizer_switch = 'index_condition_pushdown=off'; 可以关闭。
索引下推示例
数据库表中创建了联合索引 （a,b,c)
select * from table where a = 'a' and b like '%b%' and c like '%c%';
没有索引下推技术：
由于b和c使用了like，将导致索引匹配失效，所以只有a字段使用了索引，在索引中通过字段a查询到所有的数据，然后返回服务端，然后在服务端基于模糊匹配条件进行数据过滤。
使用索引下推技术：
可以在索引中首先通过字段a进行查询，然后在根据索引上的b和c判断是否符合模糊匹配条件，如果符合条件则根据该索引来定位对应数据，不符合则直接拒绝，有了索引下推技术，可以在有like条件的情况下减少回表次数，提高查询性能。
