MySQL深入04-深入浅出索引
# 索引概述
索引（index）是帮助 MySQL 高效获取数据的数据结构（有序）。在数据之外，数据库系统还维护者满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。如下面的示意图所示 :
索引优点
- 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性。
- 可以大大加快数据的查询速度，这也是创建索引的最主要的原因。
- 在实现数据的参考完整性方面，可以加速表和表之间的连接。
- 在使用分组和排序子句进行数据查询时，也可以显著减少查询中分组和排序的时间。
- 通过索引列对数据进行排序，降低数据排序的成本，降低 CPU 的消耗。
索引缺点
- 实际上索引也是一张表，该表中保存了主键与索引字段，并指向实体类的记录，所以索引列也是要 占用空间的。
- 虽然索引大大提高了查询效率，同时却也降低更新表的速度，如对表进行INSERT、UPDATE、 DELETE。因为更新表时，MySQL 不仅要保存数据，还要保存一下索引文件。每次更新添加了索引列的字 段，都会调整因为更新所带来的键值变化后的索引信息
# 索引模型
索引的出现是为了提高查询效率，但是实现索引的方式有多种，下面介绍三种提高读写效率的数据结构。
# 哈希表
哈希表是通过key和value存储的数据结构，只需要key就能找到与之对应的value。哈希的实现是把value存储在数组中，通过hash函数确定key的对应位置，然后取出对应位置的value。
哈希表的话存在一个问题：当数据越来越多的时候，必然存在多个key通过hash函数映射到同一个位置。处理的方式就是在数组的基础上，进行链表的扩展，如图所示：
但这样仍存在一个问题，由于我们的key并非是有序的，如果我们需要查询某个区间的数值，就需要去遍历整个key了，因此哈希表比较适用于等值查询。
# 有序数组
为了解决上述的范围查询问题，我们可以引入有序数组。有序数组使得key和value一一对应，同时让key顺序递增。这时候如果我们要查询
某个具体的数值，就可以通过二分法来查询。同时对二分法查询进行适当扩展，就可以实现范围查询。
单从查询效率来说，有序数组可能是最好的数据结构。但是数组都有一个通病：修改操作成本太高。
所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。
# 搜索树
这个就是典型的二叉树或者多叉树，二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。
100万的数据，如果用二叉树来存储，需要树高20。那么意味着一次查询，可能会访问到20个节点，那么如果要在100万的数据进行查找其中一个节点，适用二叉树是很慢的。
为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。
N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。
# InnoDB的索引模型
假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
现有5行数据对应如下：
100 1 k1 200 2 k2 300 3 k3 500 5 k5 600 6 k6
那么这5行数据对应索引树如下：
可以看到索引类型分为主键索引和非主键索引.
主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
再来思考一下基于主键索引的查询和基于非主键索引查询的区别。
主键索引的查询：
select * from T where ID=500
主键索引的查询是只有查询ID这棵B+树。
非主键索引的查询：
select * from T where k=5
非主键索引的查询是先去查询K索引树，得到ID的值为500，再把这个ID为500去ID索引树再查询一次。这个过程成为回表。
基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
# 索引的维护
有一个问题是：为什么要设置自增主键？
B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。如果插入ID为700的数据，只需要在R5后面进行添加；如果添加ID为400的数据，则需要进行一定的逻辑移动；如果R5所在数据页满了，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。
一般情况下我们建表会设置一个自增主键。这样插入新记录的时候可以不指定ID的值，系统会获取当前ID最大值加1作为下一条记录的ID值。这样做有两个好处：
- 性能方面：由于我们每次插入的ID都是递增的，这样就不会导致主键索引发生叶子节点的分裂。
- 存储方面：主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间就越小。
所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。
# 覆盖索引
现在有如下的表：
mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;
如果执行select * from T where k between 3 and 5，会执行几次树的搜索操作。
由于k是非主键索引，通过上面的学习，我们肯定知道这个过程会发生回表。
这条 SQL 查询语句的执行流程：
- 在 k 索引树上找到 k=3 的记录，取得 ID = 300；
- 再到 ID 索引树查到 ID=300 对应的 R3；
- 在 k 索引树取下一个值 k=5，取得 ID=500；
- 再回到 ID 索引树查到 ID=500 对应的 R4；
- 在 k 索引树取下一个值 k=6，不满足条件，循环结束。
这个过程读了K索引树的三次记录，发生了两次回表。
那么现在我们把查询语句改变一下：select ID from T where k between 3 and 5，这时只需要查ID的值，而ID的值已经在K索引树上了，因此可以直接得到结果，不需要发生回表。在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。
由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。
再来一张表分析一下：
CREATE TABLE `tuser` (
`id` int(11) NOT NULL,
`id_card` varchar(32) DEFAULT NULL,
`name` varchar(32) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
`ismale` tinyint(1) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `id_card` (`id_card`),
KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB
对于一个用户，身份证是他的唯一标识，如果我们需要通过身份证来得到对应用户的信息，只要在身份证字段上建立索引就足够了。
现在突然来了一个高频请求，需要通过身份证得到用户的姓名，这时候我们建立一个（身份证号、姓名）的联合索引，使用覆盖索引的优化方式，就不需要回表查整行记录，减少语句的执行时间。
# 最左前缀原则（联合索引）
实际情况中，我们不可能为每一个请求去设计一个索引。索引太多就会导致使用SQL语句的时候没注意最左前缀原则导致索引失效。
对于一个（name，age）的联合索引，如果我们查询语句的条件是where name = 'wxx'，那么是能够快速定位到name为wxx的数据行，然后向后遍历得到想要的结果。如果我们要查询名字带有“w”的人，我们查询语句的条件是where name like ‘w%’，这时候该查询也能够使用到（name，age）的联合索引。
不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。
在建立联合索引的时候，如何安排索引内的字段顺序
比如我们已经建立了（name，age）的联合索引，如果要单独查询name，就不必为name单独建立一个索引了，
因为这条查询语句是可以通过最左前缀原则走（name，age）这条联合索引的。
所以我们的原则就是：索引的复用能力。如果通过调整顺序，可以少维护一个索引，那么这个顺序就是需要优先考虑的。
那么，如果既有联合查询，又有基于 a、b 各自的查询呢？查询条件里面只有 b 的语句，是无法使用 (a,b) 这个联合索引的，这时候你不得不维护另外一个索引，也就是说你需要同时维护 (a,b)、(b) 这两个索引。
name和age字段，一般来说age字段要小一点，所以我们就需要创建（name，age）和（age）这两个索引，这样无论是联合查询还是name单独查询或者age单独查询都能走到索引。
# 索引下推
现有一查询语句：
select * from tuser where name like '张 %' and age=10 and ismale=1;
对于这条语句的第一个判断条件，是能够走（name，age）索引的，而age和ismale是不满足最左前缀原则的，那么他们是如何执行判断呢？
在 MySQL 5.6 之前，只能从 找到符合name条件开始一个个回表。到主键索引上找出数据行，再对比字段值。
而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
无索引下推：
有索引下推：
可以发现，在第一张图中，InnoDB引擎是不会去看age字段的数值的，找到符合条件的name，就会去回表。而第二张图中，对于age字段数值不为10的就直接不进行回表，这样减少了回表的次数，提高了查询的性能。