1、索引基础知识

索引的作用就是为了提高数据查询效率，就像根据书的目录一样查询内容；



1-1、索引的类型与优点

1-1-1、InnoDB引擎的索引类型

提高读写效率的数据结构有很多，InnoDB引擎最主要的数据结构有以下三类：

• B+Tree

• 哈希索引

• 全文索引



B+Tree

B+Tree或B-Tree是MySQL多数引擎常用且有效的索引类型，构造类似二叉树，能根据键值快速查找数据；支持全值匹配，最左前缀匹配，范围查询等；在后续的章节会重点分析B+Tree的数据结构和索引；



哈希索引

哈希索引（hash index）基于哈希表（Key-Value）实现，只有【精确匹配】索引所有列的查询才有效；

对于每一行数据，存储引擎都会对所有的索引列计算一个hash code，哈希索引将所有hash code存储在索引中，同时在哈希表中保存指向每个数据行的指针；

适合的应用场景：手机号，身份证等值的全值匹配；



HashIndex.png



哈希索引的限制：

• 哈希索引值包含哈希值和行指针，不存储字段值；

• 哈希索引数据并不是按照索引值顺序存储，所以无法用于排序；

• 哈希索引不支持部分索引列匹配；

• 哈希索引仅支持等值比较查询，包括 =、in()等操作，也不支持任何范围查询；

• 哈希访问的数据很快，但遇到哈希冲突时，必须便利链表中的行指针，进行逐行比较；

• 哈希冲突多，增加维护成本；



支持哈希索引的存储引擎：

• Memory引擎；

• NDB引擎；

• InnoDB：自适应哈希索引（adaptive hash index），当某些索引值被频繁使用，会自动创建哈希索引，无法人为干预；



全文索引

背景：互联网全文或商品搜索，B+Tree或哈希索引都不能适合；

全文索引是查找文本中的关键字，而不是直接比较索引中的值；全文索引更类似于搜索引擎，而不是简单的WHERE条件匹配；



1-2、索引的优点

1. 减少了服务器需要扫描的数据量；

2. 可以帮助服务器避免排序和临时表；

3. 将随机I/O变为顺序I/O；



如何评价一个索引--三星（three-star system）

• 索引将相关的记录放到一起获得一星；

• 索引中的数据顺序和查找中的排列顺序一致则获得二星；

• 索引中的列包含了查询中需要的全部列则获得三星；



接下来，将通过分析B+Tree来展现如何实现以上优点；



1-3、索引数据结构与算法

首先，我们先来看看与搜索相关的数据结构与算法；



1-3-1、二分查找法

二分查找（binary search）又称折半查找，用来查询一组【有序记录】数组中的某一记录；

其基本思想是：将记录按有序化（递增或递减）排序，在查找过程中，先以【有序数列】的中点位置比较值，如果要找的元素值小于中点元素，则将待查序列缩小为左半部分，否则为右半部分；通过比较，逐渐缩小查找区间；

如一个有序数列 5、10、19、21、31、37、42、47、50、52，现在要查找47这条记录，查找过程如下：



BinarySearch.png



1-3-2、二叉查找树和平衡二叉树

在介绍B+Tree之前，需要先了解一下二叉查找树；B+树是通过二叉查找树，再由平衡二叉树演化而来；



1-3-2-1、二叉查找树

二叉查找树中，

• 每个节点最多有两个子节点；

• 左子树的键值总是小于根的键值，右子树的键值总是大于根的键值；



如下图所示，这颗二叉查找树的【中序遍历】顺序为：2、3、5、6、7、9；



image.png



如果要查键值为5的记录，从根节点开始，查询顺序为 6->3->5，查询次数为3次，【顺序查找】需要3次；查询键值等于9的记录，同样需要3次，而【顺序查找】需要6次；

顺序查找的【平均查找】次数 = （1 + 2 + 3 + 4 + 5 + 6）/ 6 = 3.3次；

二叉查找树的【平均查找】次数 = （1 + 2 + 2 + 3 + 3 + 3）/ 6 = 2.3次；

在多数情况下，二叉查找树的【平均查找速度】比顺序查找要快一些；



但是二叉查找树是可以任意构造的，如下图：

平均查找次数 = （1+2+3+4+5+6）/ 6 = 3.5



image.png



为了最大性能的构造一颗二叉查找树，那么这颗二叉树必须是平衡的；

平衡二叉树【AVL（Adelson-Velskii and Landis）】的特点如下：

• 首先是一颗二叉查找树；

• 其次任何节点的两个子树的最大高度差为1；

• 二叉树的查询性能较快，但是维护一颗平衡二叉树的代价非常大；在插入或删除后，通常需要一次左旋或右旋，保证树的平衡；

还是上面的例子，这颗二叉树，当插入【10】时，节点【7】的左右子树差值为2，此时需要通过一次【左旋】保证树的平衡；



AVL.png



此时，就需要对二叉树进行【左旋】操作，就是把右子树中向左旋转；得到新的二叉树如下所示：



image.png



1-4、B+Tree

1-4-1、B+Tree数据结构

B+树可以看做一颗M阶树：

• 一棵树有M阶（节点【最大】【键值】数量M）；

• 叶子节点（无子节点）和非叶子节点；

• 非叶子节点有M+1个指针，指向其子节点；

• 数据按键值存在在【叶子节点】；

• 键值从左到右，数字从大到小排序，字母按字母表顺序排序；

• 叶子节点间为双向链表；



image.png

（图片来自《 高性能MySQL》）



例如，下图为一棵高度为2的B+树如下图所示，阶数为4

所有的记录都在叶子节点，且顺序存放，用于从最左边的叶子节点开始顺序遍历，可以得到所有的键值顺序排序：

5、10、15、20、25、30、50、55、60、65、75、80、85；

通常叶子节点所在的页（MySQL中的数据页和其他存储格式概念，会在其他文章中介绍，一个页存放多行记录）通常被称为 LeafPage，而非叶子节点所在页被称为 IndexPage;

以下图为例，介绍MySQL中如何插入或删除一个值，可以理解为 插入 或 删除 一行数据；



image.png



1-4-2、B+Tree的插入

当向B+树的插入一个值时，需要考虑以下3种情况:

• Leaf Page未满；

• Leaf Page 满，而 Index Page 未满；

• Leaf Page 与 Index Page 都满；



(1) Leaf Page 和 Index Page 都未满

直接将记录插入叶子节点



(2) Leaf Page满，Index Page未满

1) 拆分Leaf Page;

2) 将中间节点放入到 Index Page中；

3) 小于中间节点的记录放到左边；

4) 大于或等于中间节点的记录放右边；



(3) Leaf Page满，Index Page满

1) 拆分 Leaf Page;

2) 小于中间节点的记录放到左边；

3) 大于或等于中间节点的记录放右边；

4) 拆分 Index Page；

5) 小于中间节点的记录放到左边；

6) 大于或等于中间节点的记录放右边；

7) 中间节点放入上一层 Index Page；



接下来，通过上面的二叉树，演示三种情况的节点插入；

(1) Leaf Page未满

插入28这个键值，第二页的Leaf Page 和 Index Page 都未满，直接插入即可；



image.png



(2) Leaf Page满，Index Page未满

当插入70这个键值，这时第三个叶子节点Leaf Page已满，此时插入的过程如下图所示：



image.png



(3) Leaf Page 与 Index Page 都已满

先插入键值90，此时 第四个 Leaf Page未满，可以直接插入；当再插入键值95时，第四个Leaf Page已满，并且 Index Page也满，具体的操作过程如下：



image.png



（4）B+Tree的旋转（重点）

B+Tree为了保持平衡，在插入新键值时需要做大量拆分页（split）操作；

因为B+Tree结构主要用于磁盘，【页的拆分意味着磁盘操作，所以应该尽量减少页的拆分操作】，因此B+Tree也有类似平衡二叉树的【旋转(Rotation)功能】；

还是刚才的例子，当插入键值70时，B+Tree不会立刻拆分叶子节点，而是根据左右兄弟节点是否已满，将记录移到兄弟节点；

采用【旋转操作】是B+树【减少一次页的拆分】操作，这样B+树的高度依然是2；



B+Tree_Rotation.png



1-4-3、B+Tree的删除

B+树使用【填充因子】来控制树的删除变化，50%是填充因子可设的【最小值】；

所谓填充因子，就是每个 Page上键值的数量占Page阶数的比例；

比如上面的例子，阶数为4，如果填充因子为50%，那么一个页上最少要包含2个键值；

与B+Tree的插入一样，B+Tree的删除也要考虑以下三种情况：

(1) 叶子节点和中间节点都不小于填充因子；

直接将记录从叶子节点删除，如果该节点还是 Index Page节点，用该节点的右节点代替；



(2) 叶子节点小于填充因子，中间节点不小于填充因子；

合并叶子节点和它的兄弟节点，同时更新 Index Page；



(3) 叶子节点和中间节点都小于填充因子；

1) 合并叶子节点和它的兄弟节点；

2) 更新 Index Page；

3) 合并 Index Page 和它的兄弟节点；



具体操作如下：

假如 B+树的 填充因子 = 50%，每页节点数为4；

1）删除后，叶子节点与中间节点都不小于填充因子

比如之前的例子，如果要删除键值等于70的值，70删除后，所在Leaf Page的为2，等于填充因子50%；

image.png



2）删除节点是 Index Page

如果要删除键值等于25的数据，因为25是Index Page，则25所在的位置用右节点28代替；

image.png



3）Leaf Page 和 Index Page都小于填充因子

此时要删除60这个键值，60删除后，所在的 Index Page 和 Leaf Page的填充因子都小于50%，此时就是需要如下操作：

1. 合并叶子节点和它的兄弟节点；

2. 更新 Index Page；

3. 合并 Index Page 和它的兄弟节点；

image.png

以上就是关于B+Tree的结构与相关操作；



1-5、B+树索引

B+树索引并不能【直接找到】一个给定键值的具体行，B+树索引能找到被查找数据行【所在的页】，然后把页读入内存，在内存中进行查找，最好得到要查找的数据。

1-5-1、聚集索引（Clustered Index）

聚集索引（又称聚簇索引），因为 InnoDB存储引擎表示【索引组织表】，表中数据按主键顺序存放。



1、聚簇索引的选择

MySQL通常【将主键】设置为聚簇索引，

如果没有定义主键，则会选择【唯一的】【非空索引】代替；

如果没有这样的索引，会隐式的定义一个主键作为聚簇索引；



2、聚簇索引的优点

• 可以把相关数据保存在一起；

• 数据访问更快，因为将索引和数据保存在同一颗B+Tree中，因此聚簇索引中获取数据比从非聚簇索引中查找更快；

• 使用覆盖索引扫描的查询可以直接使用页节点中的主键值；



3、聚簇索引的缺点

• 插入速度严重依赖插入顺序；

• 更新聚簇索引列的代价很高；

• 基于聚簇索引的表在插入新行，或者聚簇索引列被更新后，需要移动行，而这会导致“页分裂”；当插入页满之后，则会进行分页操作，从而导致表占用更多的空间；



4、聚集索引的特性：

• 每张表主键构成一颗B+树，叶子节点存放整张表的行记录数据；

• 每张表只有一个聚集索引，因为数据页只能按照一颗B+树进行排序；

• 聚集索引能够特别快的访问针对【范围值】的查询；

• 聚集索引的存储不是物理连续的，而是逻辑连续，页之间通过【双向链表】链接；

• 聚集索引的【排序】查找和【范围】查找速度快（可以参考文章最后，关于MySQL Explain的说明）；

   关于索引的【排序】，table 表 的 id 为表的主键；

   例如：explain select * from table order by id limit 10;

   可以看到，key的值为 PRIMARY，虽然使用order by，但是并没有进行filesort操作；

id：1

select_type：SIMPLE

table：table

partitions：NULL

type：index

possible_keys：NULL

key：PRIMARY

key_len：8

ref：NULL

rows：10

filtered：100.00

Extra：NULL



索引的【范围查找】，如果按主键查询某一范围内的数据，通过叶子节点的上层节点就可以得到页的范围，

然后 直接读取数据页；

例如：explain select * from table where id > 100 and id < 1000;

id：1

select_type：SIMPLE

table：table

partitions：NULL

type：range

possible_keys：PRIMARY

key：PRIMARY

key_len：8

ref：NULL

rows：19098

filtered：100.00

Extra：Using where



在EXPLAIN中得到的MySQL数据库的执行计划（execute plan），在 rows 列中 给出的一个 查询结果的【预估返回行数】；所以rows是一个【预估值】，而不是确切的值；



1-5-2、非聚集索引（Secondary Index）

非聚集索引，叶子节点不包含行记录的全部数据，除了包含索引键值外，另外包含就是【聚集索引键】；

当通过非聚集索引查找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针，获得指向主键索引的主键，然后通过主键索引来找到一个完整的行记录；

这样带来的问题，会增加磁盘IO的次数，具体如何解决参考后续的内容；



1-6、为什么InnoDB使用B+Tree做索引？

首先，MySQL本身与B+树并没有直接关系，真正与B+树有直接关系的是InnoDB存储引擎；

1、从读写性能考虑

前面也分析了，如果用哈希表做索引，在范围查询和顺序查询时，会出现【全表扫描】的情况；



2、从数据加载考虑

与B+树不同，B-树数据除了存放在叶子节点，还存放在非叶子节点；当范围查询时，会增加数据从磁盘读取也的IO次数；



1-7、B+树索引的使用

1-7-1、联合索引

联合索引是指对表的【多个列】进行索引。

联合索引也是一棵B+树，键值数量>=2，且键值都是排序的；

联合索引对于第二个键值也进行排序处理；



1-7-2、覆盖索引

如果一个索引包含所有要查询字段的值，则称这个索引为【覆盖索引】；

覆盖索引（Covering Index），从【辅助索引】中可以得到查询的记录，不需要查询聚集索引中的记录；



覆盖索引能极大提高性能，只需要扫描索引，而无需回表，带来的好处有：

• 减少数据访问量，因为索引条目通常小于数据行大小；

• 因为按照列值顺序存储，对于I/O密集型的范围查询比随机从磁盘读取每一行数据的I/O少很多；

• 因为InnoDB引擎的非聚簇索引保存了主键值，如果非聚簇索引能够覆盖查询，则可以避免对主键索引的二次查询；



使用覆盖索引的好处：

辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量IO操作；

例如，count(*) 的统计操作，因为辅助索引远小于聚集索引，优化器会选择辅助索引可以减少IO操作；



1-7-3、优化器选择不使用索引的情况

在访问数据量较大的情况，优化器可能选择通过聚集索引来查找数据；

优化器通过【辅助索引】的情况：通过【辅助索引】查找的数据是【少量的】；这是由传统机械硬盘的特性决定，利用顺序读取替换随机读的查找；



1-7-4、Multi-Range Read优化

Multi-Range Read优化的目的：

(1) 减少磁盘的随机访问；

(2) 将随机访问转化为【较为顺序】的数据访问；

对IO-bound类型的SQL语句查询带来性能极大的提升；

可使用与 range，ref，eq_ref 类型的查询；

MRR的好处：

• MRR使数据访问变得较为顺序；在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按主键排序的顺序进行书签查找；

• 减少缓冲池中页被替换的次数；

• 批量处理对键值的查询操作；



对于 InnoDB 和 MyISAM 存储引擎的【范围查询】和【JOIN查询】操作，MRR的工作方式如下：

• 将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据是根据【辅助索引键值】排序的；

• 将缓存中的键值根据RowID进行排序；

• 根据RowID的排序顺序来访问实际的数据文件；



Multi-Range Read还可以将某些范围查询，拆分为键值对，以此来进行批量的数据查询；



1-7-5、Index Condition PushDown（ICP）优化

问题背景：

如果不支持 ICP ，当进行索引查询，首先根据索引来查找记录，然后再根据WHERE条件来过滤记录；

在支持 Index Condition Pushdown后，MySQL数据库会在取出索引的同时，判断是否可以进行WHERE条件的过滤，也就是将WHERE的部分过滤操作放在了【存储引擎层】；



好处：减少了SQL层对记录的索取（fetch），从而提高数据库的整体性能；



支持查询类型：

range、ref、eq_ref、ref_or_null ；



支持存储引擎：MyISAM 和 InnoDB；



当优化器选择 Index Condition Pushdown 时，可在执行计划的列Extra看到 Using index condition 提示



参考文章

https://mp.weixin.qq.com/s/q4uq0OLYWnrdlCf5je_yzQ