一篇文章讲解清楚MySQL索引
目录 一丶什么是索引 二丶索引的数据结构 1.哈希表 2.有序数组 3.跳表 4.平衡二叉搜索树 5.B-树，B+树 三丶InnoDB索引方案 1.InnoDB行结构 2.InnoDB页结构 2.1行结构中记录头信息的作用 2.2页目
目录一丶什么是索引二丶索引的数据结构1.哈希表2.有序数组3.跳表4.平衡二叉搜索树5.B-树，B+树三丶InnoDB索引方案1.InnoDB行结构2.InnoDB页结构2.1行结构中记录头信息的作用2.2页目录3.InnoDB索引方案3.1为页建立目录项3.2 根据目录项定位数据行的过程三丶聚集索引和非聚集索引四丶回表查询五丶联合索引六丶索引与排序和分组1.索引用于排序2.索引用于分组七丶多范围读取MRR八丶索引合并1.交集索引合并2.并集索引合并3.排序并集索引合并九丶索引建立和使用原则1.为搜索，排序，分组的列建立索引2.考虑列中不重复的个数建立索引3.索引列尽可能小4.为列前缀进行索引5.合理的建立覆盖索引6.不要在uuid上建立索引7.存在联合索引的情况下，不要重复建立索引8.尽量使用自增主键9.普通索引和唯一索引如何做出抉择9.1普通索引唯一索引等值查询的性能差异微乎其微，唯一索引略胜一筹9.2插入和更新的效率，普通索引优于唯一索引十丶索引失效1.不满足最左前缀原则2.使用了select*3.like查询左边有%4.order by 使用了联合索引中不存在的列，或者顺序不符合最左前缀匹配5.group by 使用了联合索引中不存在的列，或者顺序不符合最左前缀匹配6.不要在条件字段函数操作，注意隐式类型转换，小心隐式字符编码转换6.1条件字段函数操作6.2 注意隐式类型转换6.3 小心隐式字符编码转换一丶什么是索引
索引是存储引擎快速找到记录的一种数据结构。数据库中的数据可以理解成字典中的单词，而索引就是目录，显而易见这是一种空间换时间的做法，目录占用了空间，但是加快了我们找到单词的速度，正如索引需要空间存储，但是利用索引我们可以快速的找到想要的数据。
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的方式，在扩容的时候生成更大的数组，但不是一次移动所以数据，而是插入的新元素都放到新数组，老数组使用到的数据才会慢慢移动到新数组）redis基于内存的数据库都需要通过渐进式hash优化扩容操作，基于磁盘的mysql若使用hash将惨不忍睹
2.有序数组
有序数组就是数据中元素有序，正因为有序，所以其在范围查找上非常优秀，正因为要维持有序，在更改数据的时候，也许需要移动大量数组元素（比如插入一个较小的值，大于此值的数据都需要后移动），所以有序数据只适用于静态数据（比如2020年人口信息，这种不会改变的数据）
3.跳表
为了解决有序数组需要移动元素的问题，我们可以使用链表来维护元素，从而使更改元素效率为o(1)，但是链表的查找非常慢。由于链表整体是有序的，那么我们可以使用二分查找优化查找效率，如上我们建立多级的节点，在查找的时候我们首先通过多级的索引依次找到最下层。对于范围查找，由于底层数据是有序的，查找id<7的数组，首先我们找到id=7然后向左遍历集合（可以把跳表最下面一层优化为双向链表，从而让范围查找速度也很快）
哪为什么不使用跳表来做索引昵？
跳表是链表结构，一条数据一个结点，如果最底层要存放2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在2的24次方左右，所以，跳表大概高度在24层左右。最坏情况下，这24层数据会分散在不同的数据页里，也即是查一次数据会经历24次磁盘IO。
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索引方案
1.InnoDB行结构
InnoDB存储引擎存储一行数据使用的数据结构称为行结构。
COMPACT
变长字段列表：如varchar(m),Text，Blob类型的列，称为变长字段，由于其字节数量不固定，需要在变成字段列表中存储这些字段的长度，在记录的真实数据中存储内容 null值列表：如果表中没用允许为null的列，那么null值列表就不存在，否则把每一个允许为null的列使用一个二进制位来表示，二进制为1的时候表示值为null 记录头信息：占用五个字节，其中包含delete_flag(标记记录是否被删除)，next_record(下一条记录的相对位置)等信息 记录的真实信息：如果表没用定义主键，也没有唯一不可重复不可为null的列，那么innodb为我们生成一个隐藏列row_id,如果定义了主键那么此列不存在，并且还有trx_id,roll_pointer两个隐藏列，后续便是每一个列的真实数据。（char(M)类型的列，如果使用定长字符编码，那么字节数不会加到变长字段列表中，如果使用变长编码，占用长度会加入到变成字段列表中（变长编码那么必须占用M个字节，varchar(M）则没用这个要求）
REDUNDANT
字段长度偏移列表：此种行格式会把记录所有列长度的偏移信息存储 null值的处理方式：先看偏移量的null比特位是否为1，如果为了那么表示为null
溢出列
如果一个列太长，并不会傻乎乎的存储所有数据在行记录中，而是使用溢出列，COMPACT和REDUNDANT只会存储该列的前768字节然后存储指向其他页的地址，剩下的数据存在其他页中。
DYNAMIC和COMPRESSED
和COMPACT类似，但是二者不会存储过长列的前768字节，而是把真实数据都存储到溢出中，记录只存储溢出页的地址。COMPRESSED 还会使用压缩算法对页面进行压缩
2.InnoDB页结构
页是InnoDB管理存储空间的基本单位，其默认大小为16k,InnoDB设计了很多不同的页结构：存放Change Buffer的页，存储undo log 日志的页等等。对于表中数据，也存在在页中
最开始的时候UserRecords并不存在，随着数据的插入，会从FreeSpace中申请一个记录大小的空间，将其划分到UserRecords部分，当FreeSpace用完只会继续插入就需要申请新的页。
