https://www.jianshu.com/p/ace3cd6526c4
推荐up主https://space.bilibili.com/377905911
一丶什么是索引
索引是存储引擎快速找到记录的一种数据结构。数据库中的数据可以理解成字典中的单词，而索引就是目录，显而易见这是一种空间换时间的做法，目录占用了空间，但是加快了我们找到单词的速度，正如索引需要空间存储，但是利用索引我们可以快速的找到想要的数据。
InnoDB存储引擎存在几种常见的索引：
- B+树索引
- 全文索引
- 哈希索引
本文主要讨论B+树索引
二丶索引的数据结构
可以加快查找速度的数据结构很多，为什么mysql使用B+树来实现昵，换句话说哈希表，有序数组，跳表，平衡二叉搜索树，B-树等都可以优化搜索效率，为什么偏偏使用B+树
1.哈希表
哈希表，可以联想Java中的HashMap，在HashMap源码学习中，我们了解到Hash表的数据结构。如下图
哈希表通过hash算法将key映射到数组对应的下表进行存储，不可避免的会产生hash冲突（多个不同的key散列到相同的数组下标中），解决hash冲突常用拉链法，顾名思义，就是把相同hash值的节点组成链表。在根据key查找value的过程中，只需要再次使用相同的hash算法那么就能拿到对应的数组下表，然后遍历链表找到目标值即可,查找的效率是o(1)。
明明存在链表需要遍历为什么说时间复杂度o(1)
首先hash算法计算是常数时间，
hash表会在需要的时候进行扩容，
维持链表长度尽量在一个常数范围，从而保证遍历常数个链表节点
mysql中存在自适应哈希索引，由innodb存储引擎自己控制，利用查找O(1)的性质优化等值查询。我们可以看出，hash表并不适合范围查询，对于Id<10这种范围查询只能遍历hash表中每一个数据，相当于要进行一次全表扫描。我还有一个想法：从扩容的角度看，每次扩大数组大小后都需要移动一些数组到新的数组空间中，这部分的复制移动的开销也许是hash表不合适的原因（redis为了解决这个问题，使用渐进式hash的方式，在扩容的时候生成更大的数组，但是不是一次移动所以数据，而是把新数据的插入都是方法新数组，老数组使用到的数据才会移动到新数组）
2.有序数组
有序数组就是数据中元素有序，正因为有序，索引其在返回查找上非常优秀，正因为要维持有序，在更改数据的时候，也许需要移动大量数组（比如插入一个较小的值，大于此值的数据都需要后移动），所以有序数据只适用于静态数据（比如2020年人口信息，这种不会改变的数据）
3.跳表
为了解决有序数组需要移动元素的问题，我们可以使用链表来维护数组，从而使更改数组效率为o(1)，但是链表的查找非常慢，但是链表整体式有序的，那么我们可以使用二分法优化查找效率，如上我们建立多级的节点，在查找的时候我们首先通过多级的所有依次找到最下层。对于范围查找，由于底层数据是有序的，查找id<7的数组，首先我们找到id=7然后向左遍历集合（可以把跳表最下面一层优化为双向链表，从而让范围查找速度也很快）
哪为什么不使用跳表来做索引昵？其实我觉得完全可以使用跳表，可能是由于跳表在插入数据维护索引比较随机，比如上面的跳表插入数据6
理论上为了达到二分的效果，每一层的结点数需要是下一层结点数的二分之一。也就是说现在有一个新的数据插入了，它有50%的概率需要在第二层加入索引，有25%的概率需要在第三层加个索引，以此类推，直到最顶层。
4.平衡二叉搜索树
二叉搜索树，即左子树小于根，根小于右子树，这种结构在查找的时候可以进行二分，根据根节点的值就可以确定期望的数据在左树还是右树。
但是二叉搜索树在插入，删除节点的时候可能出现树极度不平衡的情况，出现树退化成链表。
这个时候就需要维持树的平衡——AVL:在满足二叉搜索树的条件下，要求任何节点的两个子树高度差不超过1。平衡二叉树的查找是趋近于O(log(N))，但是需要维护一颗树为AVL需要进行左旋，右旋的操作，更新的时间复杂度也是 O(log(N))。
为什么不使用AVL做索引：节点存储的数据内容太少。因为操作系统和磁盘之间一次数据交换是以页为单位的，一页 = 4K，即每次IO操作系统会将4K数据加载进内存。但是，在二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能够填满4K的内容。幸幸苦苦做了一次的IO操作，却只加载了一个关键字，在树的高度很高，恰好又搜索的关键字位于叶子节点或者支节点的时候，取一个关键字要做很多次的IO。
5.B-树，B+树
B-树就是B树，英文是B-Tree，所以国内有许多人称之为B-树。B树和B+树是多路平衡查找树，之所以多路，是为了契合磁盘的io操作——操作系统和磁盘之间一次数据交换是以页为单位的，多路能让读取一页能获取更多的数据，让树的高度更低。
上面两图，我们可以看出B树和B+树的区别
- B+树叶子节点使用双向指针串联起来，这让B+树相比于B树更加适合范围查找
- B+树非叶子节点并不存数据，所以每次查找数据都必须遍历到叶子节点，时间复杂度稳定为O(logN)，B-树在运气好的时候可以在根节点直接拿到数据。但是正是因为非叶子节点不存储数据，可以让一次磁盘读取一页中包含的索引数据更多，每个节点能索引的范围更大更精确，让我们可以更改定位到期望的数据。由于B+树的叶子节点的数据都是使用链表连接起来的，而且他们在磁盘里是顺序存储的，所以当读到某个值的时候，磁盘预读原理就会提前把这些数据都读进内存，使得范围查询和排序都很快
B+树在更改数据的时候，为了保证树的平衡可能存在节点的分裂和合并，所以我们一般建议使用自增主键，在插入的时候，不会频繁的发生节点的分裂。
三丶聚集索引和非聚集索引
InnoDB存储引擎是索引组织表——表中的数据按照主键顺序存放。非聚集索引也称做辅助索引，无论是聚集还是非聚集，其原理都是一颗B+树，叶子节点都存储数据，不同的是聚集索引叶子节点存储的是一整行的数据，非聚集索引叶子节点存储的是聚集索引值（主键值）。
如果数据表定义了主键，那么这个索引就是聚集索引，如果没有定义主键，mysql会选择该表的第一个非空唯一的索引构建聚集索引，如果都没有那么mysql会生成一个隐藏的列（6字节的列，并且插入自增）
自增主键会把数据自动向后插入，避免了插入过程中聚集索引节点分裂的问题。节点分裂会带来大范围的数据物理移动，带来磁盘IO的性能损耗，并且我们一般建议尽量不要改动主键，主键的更改也会带来page分裂，产生碎片。
四丶回表查询
如上图，加入我们有一张表存在三个字段id,age,name我们在id上建立了主键索引，这时候id主键索引也是聚集索引，在age上建立了普通索引，这时候age索引就是非聚集索引。如果我们执行select * from table where age=1这时候先走age索引（如果数据量较大，数据量少直接全表扫描了）那么会找到对应的主键id，继续到主键id索引中找到目标数据，这个操作叫做回表。
这就是为什么根据主键查找快于根据其他索引列查找，因为如果其他索引列没有包含我们select语句中需要的列（如果是select id from table where age<10,那么age索引是可以覆盖到需要的数据的(叶子节点存储了id)，那么也不会回表），那么会走主键索引拿到需要的数据，多了一步回表操作。
这里我们也可以看到为什么建议使用select * ,这意味着查找所有列，如果配合上普通索引，那么大概率这个普通索引不会覆盖到索引列，导致需要回表查询。并且select*这种"我全都要"大概率会查询到我们不需要的列，造成不必要的网络资源消耗，增加不必要的io，增加不必要的内存消耗。
五丶联合索引
联合索引是指对表上的多个列建立索引，如上图表存在四个字段id,address,name,age，我们在name和age上建立索引，上图我们粗略的展示了联合索引的B+树结构。我们可以观察到在叶子节点中name是有序的，但是age无序，联合索引是按照索引定义的顺序排序的，这就导致select xxx from table where name='b'是可以根据上面定义的联合索引查找数据的，但是``select xxx from table where age=12是无法走上面定义的联合索引的。这就是常说的最左前缀匹配原则`的原理。
-
联合索引可以减少回表
如果我们执行
select age,id from table where name='a' and age=10,这个时候由于我们定义的聚集索引一级包含了需要的数据就不需要进行回表操作了（这其实也被称为覆盖索引，即非聚集索引中可以查询到全部需要的列，那么就不需要走聚集索引回表查询数据） -
联合索引可以优化排序
上图中的联合索引，我们可以看到，名称相同的节点，其年龄是有序的
也就是说
select * from table where name='a' order by age这个语句将避免多一次的排序操作（select* from table where id=1 order by age会走主键索引拿到所有符合数据进行排序，这里说的避免一次排序操作指拿到的数据本身就是有序的 所有不需要再次排序） -
索引下推ICP
全称
Index Condition PushDown,mysql 5.6后支持的一种根据索引进行查询优化的操作。mysql数据库会在取出所有数据的同时判断是否进行where条件的过滤，将where的部分过滤放在存储引擎层。
mysql5.6之前如果执行
select * from table where name like '张%' and age=10这时候会先从name age的联合索引中拿到name满足张开头的数据，然后回表，mysql支持ICP后，效果图如下
mysql会根据联合索引中记录的age对数据进行过滤，这时候age不等于10的数据将不会回表，将回表次数从4优化到了2，这就是索引下推。
-
如何安排联合索引的顺序
第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的，比如业务中存在两个高频查询，根据name，以及根据name查询后根据age排序，这个时候我们应该建立
name age的联合索引，上面我们说过name,age的所有其中name是有序的，age只在name相同的情况下才是有序的，这样可以减少建立name的普通索引，并且优化排序，甚至利用索引下推减少回表。如果还存在根据age进行的查询，那么需要单独维护一个age的普通索引
六丶索引建立原则
1.为搜索，排序，分组的列建立索引
一般只为出现在where后面的列，连接子句中的列，出现在order by,或者group by的列进创建索引。不要无脑建立索引，索引是需要存储在磁盘上的，占用空间，并且在新增，删除，修改的时候还需要维护索引，是需要时间的。
比如select xxx from table where name= 'a' order by user_no,这条查询语句可以选择在name上建立索引，也可以选择在user_no 上建立索引，后者可以优化排序。
2.考虑列中不重复的个数建立索引
select xxxx from table where sex=1 这里不要为sex性别建立索引，性别通常只有男和女，为其建立索引，b+树只有两个节点，查找之后还要对一半的进行回表，不如直接走全表扫描
3.索引列尽可能小
mysql基本数据类型十分丰富，整数类型有tinyint,mediumint,int，bigint，我们因该尽量使用占用字节数小的数据类型，这样可以让每次读取磁盘获取一页的数据，可以获得更多的范围信息
4.为列前缀进行索引
比如说有英文名可能很长，每次都是根据FirstName 进行like查找，这时候可以选择为列的前10个字符建立索引(alter table user add index idx_name(name(10)))。但是十个字符之后将无法使用索引。
5.合理的建立覆盖索引
在聚集索引小节中，我们总结了聚集索引的好处，减少回表，优化排序，索引下推。
6.不要在uuid上建立索引
首先uuid占用字节大，导致每一页范围信息少，并且uuid无序，这会导致插入数据的时候节点的分裂。这里也说明了自增主键优秀的点，不会频繁的节点分裂，并且不要修改主键，避免不必要的节点分裂。相比于uuid作为主键，不如使用分布式自增主键生成的方案
7.存在联合索引的情况下，不要重复建立索引
存在name,age的联合索引，那么不需要再为name单独建立索引了，但是可以为age建立索引，原理在联合索引中进行了讲解。
七丶索引失效
上图是mysql的基本架构，其中存在优化器，其作用是不改变sql执行结构的情况下，让sql更加简单，并且根据成本分析，制定执行计划。是否走索引，走什么索引也是优化器来决定的（sql中可以提示使用什么索引，强制使用某一个索引）。
常见索引失效的原因有
-
不满足最左前缀原则
如果存在
a,b,c的联合索引，select * from table where b=2 and a=1这种时候还是可能走联合索引的，mysql会优化语句,但是select * from table where b=1 and c=2是无法走联合索引的，因为b，c在b+树中整体无序 -
使用了select*
使用select*需要回表，也许mysql优化器评估后觉得走非聚集索引，不如直接全表扫描
-
索引列上有计算，索引列上使用了函数
-
类型不匹配
select * from table where name = 123，可以理解成mysql把sql语句添加了类型转换函数，导致无法走索引 -
like查询左边有%
以xxx开头是可以走索引的，因为是有序的，但是以xxx结尾和包含xxx是无法走索引的。
-
or条件导致失效
select xxx from table where age=10 or name='zhangsan',age和 name上存在普通索引，但是mysql优化器觉得不如走全表扫描.这时候我们可以使用union，让其走索引 -
order by 使用了联合索引中不存在的列，或者顺序不符合最左前缀匹配
-
group by 使用了联合索引中不存在的列，或者顺序不符合最左前缀匹配