mysql 索引相关整理
一.索引的本质
数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速查询、更新数据库表中数据
我们常常会说索引会极大的提高检索的效率，这是因为，数据存储在磁盘结构中，每一条数据都有其对应的磁盘地址，在没有建立索引的情况下，我们只能全表扫描，扫到符合条件的数据。假设数据有500W条，那么查询的时间复杂度就是O(n)。索引这是一种存有索引字段和对应物理磁盘地址的数据结构，这样一种数据结构本身是一棵树（基于二分法演变而来），你可以把它简单的理解为它的遍历至少少了一半（实际效果远远不止，这个之后会说的到）
贴一张图 来表示索引和物理磁盘存储的映射
这边索引的存储结构我稍后继续写
索引的类型：
在 InnoDB 里面，索引类型有三种，普通索引、唯一索引（主键索引是特殊的唯一索引）、全文索引。
普通（Normal）：也叫非唯一索引，是最普通的索引，没有任何的限制。
唯一（Unique）：唯一索引要求键值不能重复。另外需要注意的是，主键索引是一种特殊的唯一索引，它还多了一个限制条件，要求键值不能为空。主键索引用 primay key创建。
全文（Fulltext）：针对比较大的数据，比如我们存放的是消息内容，有几 KB 的数据的这种情况，如果要解决 like 查询效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如 char、varchar、text。
PS：这里还有这样一个分类，主键索引和辅助（二级）索引.就是把主键索引单独分来了
二.索引的数据结构
在讨论这个之前，笔者之前有加入过一个技术交流群，第一天进去讨论的话题就是为什么mysql用的是B+树而不是B树。嗯，看完一系列一年或者零年工作的大佬，回答完这个问题后，笔者的年龄就一直是一年（并不会随着GC，而分代年龄增加，我就要是yong区）
那么在知道索引的作用以及相关定以后，我们来推测一下他的数据结构。
笔者常见的数据结构有以下几种，第一种链表，第二种数组，第三种Map,还有树。
链表：首先是链表，链表又分单向链表和双向链表，区别无非在于我当前的node节点是进行一个node，还是指向前后两个node。官方链表最为精彩的使用，我以为在于AQS队列。但是在存储索引的时候，他明显不合适，因为他的时间复杂度还是O(n)
数组：其实是数组，或者说是有序数组，这种结构存储索引，查询效率极高，复杂度是O(1),但是，一旦发生数据变更，后面的index需要重新赋值，只适合于静态数据，然而这种场景比较少见
其实这两个结构，也暴露了自己的问题，链表插入快 只需要改自己的node节点，和它的关联节点（可能是一个，可能是两个，取决于单向或者双向）。数组查询快，时间复杂度永远为O（1），但是插入很慢，需要改后续的元素的index下标
Map：然后是Map，这里的map完美的解决了上面的两个问题，我插入快，我查询也快。似乎很好，但是它会有一个问题，那就是范围查询，HashMap只能实现等值查询，而实现不了范围查询。通用的HashMap他实现不了order by排序。
其实还有很多问题，比如数据量过大的hash冲突。不支持联合索引的部分查询（建立ABC三列查询，使用AB查询走索引）
树：
其实主键的存储结构就是树，其实也很简单，想想二分法，猜一猜这件东西多少钱，高了低了，都是用截取一半的方式来猜测。而这样的一种行为本质上就是减少遍历深度
树是有很多故事的，我们一个个来，从先到后，分别是二叉查找树，平衡二叉树（AVL树），多路平衡查找树（B树），加强版多路平衡查找树（B+树），红黑树
二叉查找树（BST Binary Search Tree）
二叉查找树的特点是，左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。
二叉查找树，能够实现快速查找和快速插入，但是在最坏场景下，他的遍历深度是O(n)。所谓的最坏场景就是 数据呈现递增排序，但是我要查找的数据是最大的
就是像这样，这个时候 我要找5这个元素我遍历的是O(n)
很明显这样的数据结构不太合适，为了避免元素深度问题，我们要的是一颗平衡的树，所以平衡二叉树来了
平衡二叉树（AVL Tree）
平衡二叉树的定义：左右子树深度差绝对值不能超过 1。
在顺序录入1 2 3时，由于3是在2的右侧，但是如果直接塞进去，不符合限制条件，左右深度，绝对值不大于1，所以他做了一次旋转。
这个很重要，旋转是AVL树的方式，原本是1 2 3的是属于右右型 那么中间节点左旋，这样可以使得两边遍历的深度保持在一个范围内
同理当我输入3 2 1时 它属于左左型，进行了右旋，来达到平衡
这样一种数据结构可以达到平衡的效果，但是最终为什么没有采用这种结构呢。原因是浪费了极大的空间，数据一旦过大，进行的磁盘IO过多。
这里需要引入一系列的InnoDB逻辑处理结构
Mysql存储引擎分为5级，表空间，段，簇，页，行（这里直接抄了一张图）
Table Space ： 表空间可以看做是 InnoDB 存储引擎逻辑结构的最高层，所有的数据都存放在表空间中。分为：系统表空间、独占表空间、通用表空间、临时表空间、Undo 表空间。
Segment：表空间是由各个段组成的，常见的段有数据段、索引段、回滚段等，段是一个逻辑的概念。一个 ibd 文件（独立表空间文件）里面会由很多个段组成。
创建一个索引会创建两个段，一个是索引段：leaf node segment，一个是数据段：non-leaf node segment。索引段管理非叶子节点的数据。数据段管理叶子节点的数据。也就是说，一个表的段数，就是索引的个数乘以 2。
Extent：一个段（Segment）又由很多的簇（也可以叫区）组成，每个区的大小是 1MB（64个连续的页）。
每一个段至少会有一个簇，一个段所管理的空间大小是无限的，可以一直扩展下去，但是扩展的最小单位就是簇。
Page：为了高效管理物理空间，对簇进一步细分，就得到了页。簇是由连续的页（Page）组成的空间，一个簇中有 64 个连续的页。 （1MB／16KB=64）。这些页面在物理上和逻辑上都是连续的。
一个数据页，有16K大小。
往表中插入数据时，如果一个页面已经写完，产生一个新的叶页面。如果一个簇的所有的页面都被用完，会从当前页面所在段新分配一个簇。
如果数据不是连续的，往已经写满的页中插入数据，会导致叶页面分裂
Row：InnoDB 存储引擎是面向行的（row-oriented），也就是说数据的存放按行进行存放
这个时候，在知道了这些前提后，我们就可以绕过来了。当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次 IO。
InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)
等价于：一个树的节点就是16KB大小。
然后我们知道，索引会去存储，物理磁盘地址和对应的索引列以及对应的他的节点引用，而这些字段加起来是远远不到16KB的。然后这就产生了两个问题，一个是空间的极大浪费，一个是遍历的深度变高。
其实他们指向的都是一个问题，这个问题的本身是由于树的结构导致的。
好比是这样的
浪费么浪费了一堆空间，6个数据找一个37还要磁盘交互3次。当然了，当初我们说的是“二分法”嘛，这个很严格遵守了。
那么有什么办法可以救的吗，很明显，每个节点上多存一些数据不就好了。所以多路平衡查找树来了
多路平衡查找树（B Tree）
跟 AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。
它有一个特点：分叉数（路数）永远比关键字数多 1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。
你看这样一来，我存储20个数据，深度最多是3，如果是刚刚的AVL树 他就会长成这样，最坏深度是5（不要问我是怎么左右旋转的，我看的也晕）
之前有说到，AVL树靠左右旋转来保持树的平衡，那么B树是怎么保持平衡的呢，他其实是靠分裂
我们继续演示一下
当我们插入3的时候，他就分裂了 插入5之后是这样，插入6之后就合并了
加强版多路平衡查找树（B+ Tree）
概念图如上
从结构图上可以看出来B+数的一些特性：mysql的B+数是和普通B+树有区别的（上一张图是mysql的，下一张是普通的）
1.叶子节点上存储数据，根节点和枝节点都不存储数据
2.关键字数量和根路数相等
3.叶子节点增加了对下一个节点的引用，同时末级节点指向了第一个节点，形成了一个有序列表。这样可以更好的支持范围查询
4.根据左闭右开来检索数据
这张图说明了在实际存储数据时，B+树能够存储的数据量级
比较一下B+树与B树的区别：
1)它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。B Tree 解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
2)扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵 B+Tree 拿到所有的数据）
3) B+Tree 的磁盘读写能力相对于 B Tree 来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
4)排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
5)效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）
红黑树
红黑树并不是严格平均的，而且它是二叉的。这也是为什么底层结构不用这个的原因
红黑是有以下几个约束
1、节点分为红色或者黑色。
2、根节点必须是黑色的。
3、叶子节点都是黑色的 NULL 节点。
4、红色节点的两个子节点都是黑色（不允许两个相邻的红色节点）。
5、从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点。
基于以上规则，可以推导出：
从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全部是黑色节点）的 2 倍。
三.B+树在实际数据库中的查询
之前也有说过，索引可以分为主键索引和非主键索引。其实是有专业名词的，叫做聚簇索引（聚集索引）。
所谓聚集索引，就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。所以主键索引是聚集索引，非主键都是非聚集索引。
InnoDB 中，主键索引和辅助索引是有一个主次之分的。
辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终取得数据。
这个会导致一个问题，如果我没有主键怎么办
1、如果我们定义了主键(PRIMARY KEY)，那么 InnoDB 会选择主键作为聚集索引。
2、如果没有显式定义主键，则 InnoDB 会选择第一个不包含有 NULL 值的唯一索引作为主键索引。
3、如果也没有这样的唯一索引，则 InnoDB 会选择内置 6 字节长的 ROWID 作为隐藏的聚集索引，它会随着行记录的写入而主键递增。
四.索引的使用原则
1.列的离散度
首先有一个规则是不要再重复度高的列上，使用索引。
离散度的公式：count(distinct(column_name)) : count(*)，列的全部不同值和所有数据行的比例。
数据行数相同的情况下，分子越大，列的离散度就越高。
其实这个也很好理解，如果有500W的数据，然后这一列有250W的数据是0，250W的数据是1，这个时候让我找所有0的数据，那就是近乎于全表扫描了
看一下执行计划
同样的如果是搜索离散度大的字段 比如名称，那么他的扫描行数就是1
2.联合索引最左匹配原则
所谓的联合索引，就是我在表上面创建了ABC三列索引。此时A索引有效，AB索引有效，ABC索引有效
之所以左边的带头大哥不能少，是因为索引是按照从左到右的格式创建的。
只有左边的排序完成后，才会对右边的字段进行排序。单纯的看右边的字段，而不去带有左边的字段，本身是无序的
ps，当建立ab两个查询字段的时候，如果你查询你的语句是where b = xxx and a = xxx.这个也是可以走索引的 mysql的优化器会帮你优化的
3.覆盖索引
回表：非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查出索引里面没有的数据，它比基于主键索引的查询多扫描了一棵索引树，这个过程就叫回表。
在辅助索引里面，不管是单列索引还是联合索引，如果 select 的数据列只用从索引中就能够取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引，这样就避免了回表。
解释一下，就是用了ABC三列，然后如果只是查询这3列数据，就会只是在索引上获取，而不会去取树的节点。分析结果如下
4.索引下推（ICP）
索引下推是默认开启的，而他的意思很简单。
简单的来说，我们有A过滤条件和B过滤条件，数据有500W条，在不开启ICP下，A过滤条件筛选出200W条，B条件筛选出100W条。这两个条件都是从500W的初始数据中获取。然后两者之间取交集
然后假设我开启了这个开关，那么是A过滤条件筛出200W的数据后，在这200W数据内，在进行B条件的筛选。这样会极大的提高，B条件的筛选
就是这个，左边的图筛选出来姓名是wang的，右边在左边筛选出来的结果内筛选first_name = 0zi的
参数的开关是这个：show variables like 'optimizer_switch';
set optimizer_switch='index_condition_pushdown=off';（注意非全局，只是当前会话）
索引的创建与使用规则
索引的创建
1、在用于 where 判断 order 排序和 join 的（on）字段上创建索引
2、索引的个数不要过多。---浪费空间，更新慢
3、区分度低的字段，例如性别，不要建索引。
4、频繁更新的值，不要作为主键或者索引。
5、组合索引把散列性高（区分度高）的值放在前面
6、创建复合索引，而不是修改单列索引。
什么时候用不到索引
1、索引列上使用函数（replace\SUBSTR\CONCAT\sum count avg）、表达式、计算（+ - * /）
2、字符串不加引号，出现隐式转换
3、like 条件中前面带%
五.生产环境SQL调优
下面是一个生成环境的SQL然后做的一些列的调优
这是经过优化之后的
主要做了以下的一些优化，相关关联字段增加索引，bar对应的sku_id做了索引的增加，后续走的是ref索引
然后当时发现一个问题，在对主表进行日期过滤时时间超级长
效果如下：
分析如下：
其他的基本没有什么变化，只是由于主表的时间查询后，过滤出来1209条数据，这个时候明细进行查询出来34866条，两者之间的数据为两个集合的相乘。于是时间就到了9s多，这很明显无法接受
然后更好玩的事情出现了
这个时候我的时间点是在4月1号到5月28日，这个时间范围就变长了，然后很神奇的是，mysql的编译解析器换了一种走法
这边由有趣的是此时同样是时间范围查询，sql的走的索引就从range范围索引到了eq_ref的关联主键索引查询，瞬间只是匹配到对应的一条
所以这会变成一个很奇怪的现象，我时间范围放大，查询出来快，时间范围变小，查询出来就很慢
当然，原因是因为走得索引类型不一样。于是，笔者产生了极度的好奇，为什么
直到我看到了这句话
对于range类型，选择性小于17%了，就会走全表扫描，而非range
所以，我正在想是不是由于这个原因，导致时间范围变大了，不走索引，而去走了对应的全表扫描。而正因为走了全表扫描，然后又匹配到主键receipt_id,所以走了关联索引查询
那么解决方案还是比较简单的，我再外面套了一层select * from （） T，然后条件是跟的是T.billdate.
所以，这边走的全是eq_ref索引