本文是学习MySQL索引知识后进行得整理，部分图片来源马士兵老师的公开课，仅作笔记使用
一、MySql架构图
二、几种常见的数据结构用于索引结构分析
1、hash表
缺点:
- 利用Hash存储索引的话，需要将所有的数据文件添加到内存中，比较耗费内存空间。
- hash适用于等值查询，但是在实际工作环境下范围查询的操作更多，所以hash就不太适用了。
2、BST（二分查找树）、AVL（平衡二叉树）、红黑树
①BST、AVL
②红黑树
红黑（ Red 一 bIack ）树是一种自平衡二叉查找树． 1972 年由 RudOlfBaye 泼明．它与 AvL 树类似，都在插入和删除操作时能通过旋转操作时，保持二叉查找树的平衡，以便能获得高效的查找性能．它可以在 O ( Iogn ）时间内做查找，插入和删除等操作。红黑树是 2-3-4树的一种等同，但有些红黑树设定只能左边是红树．这种情况就是 2-3 树的一种等同了。对于 AVL 树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于 AVL 树。
①②缺点：
无论是BST、AVL、红黑树，都会因为树的深度过深，而造成磁盘IO次数过多，影响数据的读取效率。
3、B树
B树的特点：
- 所有的键值分布在整颗树中。
- 搜索有可能在非叶子节点结束，在关键字全集内做一次查找，性能逼近二分查找。
- 每个节点最多拥有m个子树。
- 根节点至少有两个子树。
- 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
- 所有的叶子节点都在同一层，每个节点最多可以有m-1个key,并且以升序排列
总结：根据 B-Tree 的定义，可知检索一次最多需要访问 h 个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入。（操作系统中一页大小通常是4KB）
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次 I/O。
而检索的时候，一次检索最多需要 h-1 次 I/O（根节点常驻内存），其渐进复杂度为
但在实际应用中，出度 d 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过 3）。而其他搜索二叉树，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以其它树的 I/O 渐进复杂度也为 O(h)，效率明显比 B-Tree 差很多。
4、B+树
注意：
- Mysql的存储引擎的Innodb和MyISAM的B+树索引结构的Data区域存放的值是不一样的。Innodb的主键索引如图中解释的存放的是行数据，而辅助索引的key是索引列字段，data存放的是主键（通过辅助索引查找到主键，在通过主键到主键索引中查找到行数据叫回表）;MyIsam存储引擎的索引都是非聚簇索引，它的B+树索引的Data区域存放的都是内存地址
- 索引分为聚簇索引（Innodb存储引擎的主键索引）和非聚簇索引（除Innodb存储引擎的主键索引外）
- B+树的只有叶子节点才会存放data
B+Tree索引的性能分析
一般使用磁盘I/O次数评价索引结构的优劣
1、预读：磁盘一般会顺序向后读取一定长度的数据(页（4K）的整数倍)放入内存
2、局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用
3、B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O
4、B+Tree的度d一般会超过100，因此h（树的高度）非常小(一般为3到5之间)
三、索引（Innodb存储引擎）
1. 索引简述
索引是一种用于快速查找排序的数据结构。
优点：
1、MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度;
2、帮助服务器避免排序和临时表。
3、将随机io变成顺序io
注：能够减少磁盘IO的次数，从而提高检索速度–>由于磁盘数据的存取会经过寻道时间（速度慢、耗时）和旋转时间（速度快）；
缺点：虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行INSERT、UPDATe和DELETE。因为更新表时，MySQL不仅要保存数据，还要保存一下索引文件。建立索引会占用磁盘空间的索引文件
2.索引分类
- 主键索引
基于该表主键自动生成成的索引，如果未给表定义主键，会查找该表中是否存在非空、整形、唯一索引作为其主键(可通过select _rowid from 表名查看)，若都不满足会隐式生成一个rowid作为主键(无法直接查到)
- 唯一索引
基于表的唯一列生成的索引，允许为空值
3 普通索引
非主键，非唯一列的索引
- 全文索引
将存储于数据库中的整本书或整篇文章中任意内容信息查找出来，如大量级的文字中如like %关键字%，普通索引的效率与全文索引相比是非常低的
- 组合索引
上面1-4讲的只是单索引
create index id_name_subject on teacher(name, subject); 组合索引key(name ,subject)
索引中的key存放了name和subject两个字段,而data区域存放主键
3.回表
在B+树图片中提到过回表的过程，现在在回顾一下
先从Innodb存储引擎说起，Innodb有两种索引，一种聚簇索引，一种普通索引；
- 聚簇索引
Innodb必须要有一个聚簇索引，且只有一个。
若有主键的话，聚簇索引就是主键索引。
若没有主键，会选择一个非空的唯一键作为聚簇索引
若没有唯一键，则会生成一个6字节的rowid作为聚簇索引
- 普通索引
普通索引的key存的是name，叶子节点中的data区域存的主键id
回表： 比如有一张people表，里面有一个普通索引index（name）
SQL为;select * from people where name =‘zhangsan’
此时存储引擎会根据普通索引name查询到name=‘zhangsan’的对应的主键id，然后在根据主键id去聚簇索引中查询到行数据，这个过程叫回表操作。
4.最左匹配原则
两种方式： ①CBO-基于成本优化（默认），②RBO-基于规则优化
索引可以简单如一个列(a)，也可以复杂如多个列(a, b, c, d)，即组合索引。如果是组合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等），遇到范围查询(>、<、between、like左匹配)等就不能进一步匹配了，后续退化为线性查找。因此，列的排列顺序决定了可命中索引的列数。
如有索引(a, b, c, d)，查询条件a = 1 and b = 2 and c > 3 and d = 4，则会在每个节点依次命中a、b、c，无法命中d。也就是最左前缀匹配原则。
=、in自动优化顺序不需要考虑=、in等的顺序，mysql会自动优化这些条件的顺序，以匹配尽可能多的索引列。
如有索引(a, b, c, d)，查询条件where c > 3 and b = 2 and a = 1 and d < 4与where a = 1 and c > 3 and b = 2 and d < 4等顺序都是可以的，MySQL的优化器会自动优化为where a = 1 and b = 2 and c > 3 and d < 4，依次命中a、b、c。
--一张表table，组合索引为（name，age，addr）
select * from table where name = 'zhangsan' and age = 10 and addr='hubei' --匹配（name，age，addr）
select * from table where name = 'zhangsan' and age = 10 --匹配到name，age
select * from table where name = 'zhangsan' --只走索引name
select * from table where age = 10 --丢失头部索引name，不会走索引
select * from table where age = 10 and name = 'zhangsan' --匹配到name，age，sql优化器会优化
select * from table where name = 'zhangsan' and addr = ‘湖北’ --name走索引，addr不会，由于中间age断了
--上述情况在select * from table where条件下， 后面如果没有name就不会走索引。中间断了，后面就不会继续走索引
SELECt NAME FROM people WHERe age =40 --会走索引，---覆盖索引
5.索引覆盖
一张表table，组合索引为（name，age，addr），自增主键为id
SELECt NAME FROM people WHERe age =40
SELECt id,NAME FROM people WHERe age =40
SELECt id,NAME,idCard FROM people WHERe age =40
SELECt id,NAME,idCard FROM people WHERe name='zhangsan'
第一条SQL查询条件与需要查询的字段都在组合索引（name，age，addr）中，所以会走索引，这种情况就是索引覆盖，此时就不需要在进行回表操作了，会直接在组合索引中查询到值，减少了磁盘IO的次数。
至于第二条SQL，也是索引覆盖，因为id为主键，在组合索引中除了有name，age，addr外还有data中的主键id，所以可以直接在组合索引中拿到值。
第三条SQL不会走索引 ，因为查询的列有IDcard，该列不在组合索引（name，age，addr）中，所以会全表扫描。
第四条SQL会走索引name，但由于查询的列有IDCard，所以会在组合索引查询到对应的主键id，在通过聚簇索引中查询到对应行数据取出IDcard，这个过程会有回表操作，效率比走覆盖索引低。
6.索引下推（ICP） mysql5.6及之后
ICP：Index Condition Pushdown
一张表people，组合索引为（name，age，addr），自增主键为id
SELECt * FROM people WHERe age >20 AND NAME LIKE 'zhnags%'
上面的SQL有两种执行可能的过程
1、根据组合索引查询满足name以“zhangs”开头的索引，然后回表查询出相应的全行数据，然后再筛选出满足年龄age大于10的数据
2、根据组合索引查询满足name以“zhangs”开头的索引，然后直接在磁盘中再筛选出年龄大于10的索引，之后再回表查询全行数据
根据上面两种可能，可以明显看出第二种效率更高，减少了回表了次数，从而提高效率
mysql5.6之前版本
在没有索引下推之前，①先从存储引擎中拉取name=‘zhangs’的行数据②mysql Server 再根据age进行数据筛选
mysql5.6及之后版本
有索引下推之后，根据组合索引查询满足name以“zhangs”开头的索引，然后直接在磁盘中再筛选出年龄大于10的索引，之后再回表查询全行数据
实践 mysql5.7版本
索引下推总结：
优点：索引下推在普通索引上的优化，可以有效减少回表的次数，大大提升了查询的效率。
注：关闭索引下推可以使用如下命令
set optimizer_switch='index_condition_pushdown=off';
7.谓词下推
有两张表A,B，id分别为各自的主键
select * from A Join B on A.id = B.id
上面的SQL有两种执行可能
①先做表连接，在做查询需要的字段
②先取出所有需要的字段，然后在做表关联 --------- 谓词下推
MySQL优化器会进行优化成方式②，使用第②种能减少IO量，效率更高
---------------------------如有错误之处，欢迎指出
