3.MySQL索引原理与使用原则

本章要点

1.索引原理
2.索引类型
3.使用原则
4.有关索引的几个概念

1. 索引原理

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样；是一种排好序的数据结构。
本质就是：通过不断地缩小想要获取数据的范围来筛选出结果，同时把随机的事件变成顺序的事件。

1.1 索引的常见模型

常见的索引模型数据结构：哈希表、有序数组和搜索树。

哈希表：一种以键 - 值（key-value）存储数据的结构（Map），只要输入待查找的键即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。链表过长时，性能交叉，且不支持范围查询。

哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎

有序数组:有在等值查询和范围查询场景中的性能就都非常优秀。利用二分查找算法进行查找效率很快（O(log(N))）。但是，在需要更新数据的时候就麻烦了，往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

有序数组索引只适用于静态存储引擎

搜索树:他的特点是:父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值，树可以是二叉树也可以是多叉树。
使用搜索树其实能够保证数据按照键的顺序进行存储，也就是相邻的所有数据其实都是按照自然顺序排列的；
B 树和 B+ 树在数据结构上其实有一些类似，它们都可以按照某些顺序对索引中的内容进行遍历，对于排序和范围查询等操作，B 树和 B+ 树相比于哈希会带来更好的性能
B 树和 B+ 树相比，哈希作为底层的数据结构的表能够以 O(1) 的速度处理单个数据行的增删改查，但是面对范围查询或者排序时就会导致全表扫描的结果，而 B 树和 B+ 树虽然在单数据行的增删查改上需要 O(log n) 的时间，但是它会将索引列相近的数据按顺序存储，所以能够避免全表扫描。

总结：

使用B+树而不是二叉树的原因

二叉树单边插入可能会退化成链结构
大数据量下高度不可空

使用B+树而不是B树的原因

B+树节点大小更小，一次IO读入的节点数更多
B树数据存在各个节点中，而B+树的数据都在叶子节点中，遍历和区间访问性能大幅提高
B+树查询效率更加稳定

使用B+树而不是平衡二叉树或红黑树的原因

在数据量比较大的情况下，平衡二叉树或红黑树高度不可控，而B+树的树高比平衡二叉树或红黑树低，IO次数少

所以MySQL选择了B+Tree

对于InnoDB的哈希索引，确切的应该这么说：

（1）InnoDB用户无法手动创建哈希索引，这一层上说，InnoDB确实不支持哈希索引；
（2）InnoDB会自调优(self-tuning)，如果判定建立自适应哈希索引(Adaptive Hash Index, AHI)，能够提升查询效率，InnoDB自己会建立相关哈希索引，这一层上说，InnoDB又是支持哈希索引的；

2. 索引类型

索引分类

普通索引index :加速查找
唯一索引
主键索引：primary key ：加速查找+约束（不为空且唯一）
唯一索引：unique：加速查找+约束（唯一）
联合索引
-primary key(id,name):联合主键索引
-unique(id,name):联合唯一索引
-index(id,name):联合普通索引
全文索引fulltext :用于搜索很长一篇文章的时候，效果最好。

3. 使用原则

3.1 创建原则

对于经常查询的字段，且区分度大的字段，建议创建索引。
索引不是越多越好，一个表如果有大量索引，不仅占用磁盘空间，而且当表里数据有所更改，维护索引成本较大，且影响增、删、改的效率
避免对经常更新的表进行过多的索引，因为当表中数据更改的同时，索引也会进行调整和更新，十分消耗系统资源。
数据量小的表不需要创建索引，数据量小时索引不仅起不到明显的优化效果，对于索引结构的维护反而消耗系统资源。
不要在区分度低的字段建立索引。比如布尔字段，只有 “失效” 和 “有效” ，建索引完全起不到优化效果。
在频繁进行跑排列分组（即进行 group by 或 order by操作）的列上建立索引，如果待排序有多个，可以在这些列上建立组合索引

区分度公式：
count(distinct(column_name)) / count(*) -- 列的全部不同值个数/所有数据行行

3.2 联合索引的最左匹配原则

当B+Tree的数据项是复合的数据结构，比如(name,age,sex)的时候。

B+Tree是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，+Tree会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据；
但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。
比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了，这个是非常重要的性质，即索引的最左匹配特性。

4.有关索引的几个概念

回表： 如果语句是 select * from T where k=5（k含有索引字段），即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程回表。
覆盖索引：如果语句是 select k from T where k=5（k含有索引字段），即普通索引查询方式，则需要先搜索 k 索引树，这个称为覆盖索引(执行计划extra 字段为 Using index)。
索引合并：对多个索引分别进行条件扫描，然后将它们各自的结果进行合并(intersect/union)，当时and 关系的时候进行intersect操作，or关系的时候进行union操作。5.1版本以后才有的索引合并
索引下推：索引下推（index condition pushdown ）简称ICP，是指当进行查询的时候，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数(执行计划extra 字段为 Using index condition)。5.6版本以后才有的索引下推

以联合索引（name, age）为例。如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。

select * from tuser where name like '张%' and age=10 and ismale=1;

5.6版本以前，只是进行匹配查询：

image.png

5.6版本以后，索引下推：