零、什么是索引？
- 索引是帮助MySQL 高效获取数据的数据结构
- 索引存储在文件系统中
- 索引的文件存储形式与存储引擎有关
- 索引的文件结构
4.1 hash
4.2 二叉树
4.3 B树
4.4 B+ 树
一、索引的常见模型
hash：键值对存储数据结构（实现方式：数组+链表），值放在数组中，用hash 函数把key 换算成一个确定的位置，然后把value 放在数组的这个位置。
哈希碰撞：不同的key 值通过hash 函数算出的值相同，处理方式就是在数组的该位置拉出一个链表。
hash 存储只适合等值查询，不适合范围查询，实际工作中范围查询的情况更多，所以hash 存储更适合一些NoSQL 引擎。
hash 索引并不是按照索引顺序存储的，无法排序。当存在hash 冲突，维护操作的成本也会增加。-
BST树（二叉搜索树）：二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。二叉树的查询效率挺高的（时间复杂度是O(log2(n))），但是有可能出现一条链式结构。
-
AVL 树（自平衡二叉搜索树）：AVL树定义是任意节点的两个子节点高度差不超过1。AVL树本质上是带了平衡功能的二叉搜索树。
解决上图的办法：通过 左旋维护去维护平衡。
也就是说AVL树维护平衡的成本很高，每次增加或删除一个节点需要多次左旋或者右旋去维护树的平衡。如果节点多的情况下AVL 树的高度还是会比较高且查询不稳定（看运气）。
AVL 树节点存储的数据内容太少，在二叉树每个节点的结构只能保存一个关键字，一个数据区，两个子节点的引用，并不能填满4k的内容，即每次IO操作系统会将4k 数据加载到内存。 B 树：有序数组+ 平衡二叉树；B树每个节点都存储了key和data，B树提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。
B+ 树：有序数组链表+平衡多叉树；B+ 树的data 存储在叶子节点上，B+树能够很好地配合磁盘的读写特性，减少单次查询的磁盘访问次数。每一个索引在InnoDB里面对应一棵B+树，主键索引的叶子节点存的是整行数据，在InnoDB里，主键索引也被称为聚簇索引。非主键索引的叶子节点内容是主键的值，在InnoDB里，非主键索引也被称为二级索引。
二、MySQL索引类型
Normal 普通索引
Unique 唯一索引：表示唯一的，不允许重复的索引。添加唯一性索引的数据列可以为空，但是只要存在数据值，就必须是唯一的。创建唯一索引的目的不是为了提高访问速度，而只是为了避免数据出现重复。
Full Text 全文索引：MySQL5.6.24上InnoDB引擎也加入了全文索引。全文索引的运用见《https://blog.csdn.net/yygg329405/article/details/97110984
》SPATIAL 空间索引：空间索引是对空间数据类型的字段建立的索引，MYSQL中的空间数据类型有4种。
btree索引和hash索引的区别：BTREE（B树（可以是多叉树）） {主流使用}；HASH（key,value） 这种方式对范围查询支持得不是很好《https://blog.csdn.net/guo_qiangqiang/article/details/88794971
》
三、索引的技术名称
- 回表：回到主键索引树搜索的过程，我们称为回表。
- 索引覆盖：不需要回表操作，如通过二级索引查询主键，二级索引的叶子节点已经存储了主键值，所以不需要回表，减少树的搜索次数。
- 最左匹配：创建一个组合索引，最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。
联合索引为key idx_a_b_c(a,b,c)
是否使用索引
where a = x and b = x and c = x 是
where a = x and b = x 是，部分索引
where a = x 是，部分索引
where b = x 否，不包含最左列a
where b = x and c = x 否，不包含最左列a
MySQL中，有两种方式生成有序结果集：
1. 通过有序索引顺序扫描直接返回有序数据
2. Filesort排序，对返回的数据进行排序
可以用export 命令查看Extra列是否有Using filesort进行了额外排序
假如说有如下联合索引，key idx_a_b_c(a,b,c)
order by 能使用索引排序
order by a
order by a,b
order by a,b,c
order by a desc, b desc, c desc
where a = const order by b,c
where a = const and b = const order by c
where a = const and b > const order by b,c
order by 不能使用索引进行排序
rder by b
order by c
order by b, c
order by a asc, b desc, c desc //排序不一致
where g = const order by b,c //丢失a索引
where a = const order by c //丢失b索引
where a = const order by a,d //d不是索引的一部分
where a in (...) order by b,c //范围查询
建一个联合索引(col1,col2,col3)，实际相当于建了(col1),(col1,col2),(col1,col2,col3)三个索引。
每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大增加开销！
- 索引下推：对于不符合最左前缀的部分在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
建一个联合索引（name, age）
SQL语句是这么写：
mysql> select * from tuser where name like '张%' and age=10 and ismale=1;
根据最左前缀索引规则，搜索索引树的时候，只能用 “张”。MySQL 5.6之前只能从匹配出的数据一个一个的回表再对比字段值。
MySQL 5.6 引入的索引下推优化， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
