关于mysql的索引
本篇文章于2021年7月18日15:25:27。。重构之
主要最近在看一个 mysql 的课，然后看到之前写过索引相关的文章，看不下去了，重构之。（捂脸）
什么是索引呢？简单来说，索引就像是书本的目录一样，目的是提高查询效率。
索引的常见实现
哈希表：
哈希表适用于等值查询的场景，是最快的 O(1)
区间查询就需要全部扫描一遍了，速度很慢 O(n)
有序数组：
- 有序数组无论是等值查询和区间查询性能都不错
- 但是新增数据的时候，有序数组要保证有序，需要把插入位置之后的数据全部后移，成本太高
- 所以，有序数组只适合用于静态存储引擎
平衡二叉树：
- 二叉搜索树是一个很常见的数据结构，它的查询操作平均复杂度为 O(lgn)，相应的平衡二叉树的平衡操作时间复杂度也是O(lgn)
- 虽然二叉搜索树的效率很高，但是层数太多了，每多一层可能都意味着一次磁盘IO操作，这样看来是很慢的
- N 叉树，我们增加树的 “叉”，就可以减少树的深度，就可以尽量检查访问磁盘的次数
InnoDB索引模型
本文主要说的 mysql 的索引，InnoDB是 mysql 的主要引擎（虽然MyISAM也使用B+Tree作为索引结构，但是本文默认都是基于InnoDB）。
最重要的一点是，b+树的非叶子结点只做索引，叶子结点保存有全部的数据，并且只有叶子节点带有指向卫星数据的指针。
主键索引和非主键索引
主键索引叶子结点的卫星数据，保存的是整行的数据。
非主键索引叶子结点的卫星数据，保存的是主键的值。
回表
我们知道了主键索引和非主键索引的区别了，假设有一张表t，id是主键索引，name是非主键索引，那么请问：
1 | select * from t where id = xx; |
这两条查询有什么区别吗？哪个效率更高？
答案显然是第一条：
- 第一条sql：从 id 这个索引对应的B+树上，找到 xx 这条数据，然后卫星数据已经是整行记录了，直接返回就行了
- 第二条sql：从 name 这个索引对应的B+树上，找到xx这条数据，然后得到主键的值，在用这个值重复上一步，然后返回这行数据
从非主键索引树查询到主键数据，再回主键索引树查找最终数据，这个过程我们称之为回表。
覆盖索引
前面我们知道了什么是回表，那我怎么样可以不回表呢？
覆盖索引的概念和回表刚好是相反的。。就是说无需回表，就可以获取到所需数据。
所以这是为什么我们尽量要减少 select * 的写法。
联合索引
前面我们知道一个索引就对应一个B+树，创建的索引越多内存占用就越大。。
所以我们可以创建联合索引。。
并且联合索引的命中是 “最左匹配原则”，就是说联合索引的创建顺序是会对索引命中有影响的。
关于联合索引的命中和失效情况，有非常多，这里不展开讲。随便一搜能搜到很多。（涉及范围查询，排序等等）
索引下推
这个其实也没什么好说的，就是mysql5.6之后的一个优化。
假设表t，有 id 的主键索引，有 （name, age） 的联合索引：
1 | select * from t where name=ruomu and age=23; |
在 mysql5.6 之前：
- 去 (a,b) 索引对应b+树，查询到满足 name=ruomu 的结点
- 回表去判断是否满足 age=23 这个条件
有了索引下推之后：
- 去 (a,b) 索引对应b+树，查询到 name=ruomu 的结点
- 因为是联合索引，所以 b 的值应该也在结点中呀，所以直接排除掉不满足 age=23 的
- 用满足条件的数据取回表，(因为是 select * 嘛。。还是会回表)，这样会少很多次回表。
唯一索引
唯一索引，使用数据库的机制来约束数据的唯一性。
和普通索引的区别就是，新增数据的时候，需要判断数据的唯一性，要把磁盘的数据读取到内存中，不能使用change buffer 来缓存。
这里不展开说了，后面可能会整理一些关于， redo log、undo log、binlog、change buffer的文章。
为什么b+树比b树更适合作为索引？
这是一个面试高频题吧？当做对本文的一个总结
- b+树的非叶子结点只有关键字，不保存卫星数据，所以一页能保存的关键字就更多，减少了IO读取的次数
- b+树的卫星数据都在叶子节点上，查询效率固定为O(lgn)，比较稳定
- b+树的所有叶子结点，使用链表有序连接，这样扫库和范围查询时效率更高
ps: 本文只是一个框架吧，没有太多展开，对之前文章的一个重新整理。。
参考链接：
- 极客时间《mysql实战45讲》
- 网络资料