MySQL 索引原理深入剖析

一、什么是索引

1.1 索引是什么

维基百科上对数据库索引的定义：

数据库索引，是数据库管理系统(DBMS)中一个排序的数据结构，以协助快速查询、 更新数据库表中数据。

据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址。如果没有索引的话，我们要从表的全部行数据里面检索一条数据，只能依次遍历这张表的全部数据, 直到找到这条数据。

1.2 索引的类型

在 InnoDB 里面，索引类型有三种，普通索引、唯一索引(主键索引是特殊的唯一 索引)、全文索引。

• 普通（Normal）：也叫非唯一索引，是最普通的索引，没有任^的限制。
• 唯一 （Unique）：唯一索弓|要求键值不能重复。另外需要注意的是，主键索引是一 种特殊的唯一索弘它还多了一个限制条件，要求键值不能为空。主键索引用 primay key 创建。
• 全文（Fulltext）：针对比较大的数据，比如我们存放的是消息内容、一篇文章，有 几KB的数据的这种情况，如果要解决 like 査询在全文匹配的时候效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如char、varchar、text。

全文（Fulltext）的示例：

CREATE TABLE ' fulltext_test' (
' content' varchar(50) DEFAULT NULL,
FULLTEXT KEY ' content' ( content )
);
----语法
语法：
select * fiom fiilltext test where match(content) against(*需要查找的字符串'IN NATURAL LANGUAGE MODE);

MylSAM 和 InnoDB 支持全文索引

二、索引的存储模型演变过程

索引使用的B+Tree，接下来说明从二叉査找树一步一步升级到 B+Tree

2.1 二叉查找树(BST Binary Search Tree)

二叉查找树的特点是什么？

左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。

二叉查找树既能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题：就是它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)

还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、6、11、13、17、22。它会变成链表（“斜树”）。这种情况下不能加快检索速度的目的，和顺序查找效率是没有区别的。

造成它倾斜的原因是什么呢？

因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。

所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？

这个就是平衡二叉树，叫做Balanced binary search trees,或者 AVL 树（AVL是发明这个数据结构的两位作者的名字简写：G. M. Adelson-Velsky和E. M. Landis）

2.2 平衡二叉树（AVL Tree）（左旋、右旋）

AVL Trees （Balanced binary search trees）

平衡二叉树的定义：左右子树深度差绝对值不能超过1

是什么意思呢？比如左子树的深度是2，右子树的深度只能是1或者3

这个时候我们再按顺序插入1、2、3、4、5、6,—定是这样，不会变成一棵“斜树“

通过左旋和右旋来保持树的平衡

平衡的问题我们解决了，那么平衡二叉树作为索弓I怎么査询数据?

在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

前面我们已经知道了，索引必须要存你建立索引的字段的值，叫做键值，比如 id 的 值。还要存完整记录在磁盘上的地址。由于AVL树是二叉树，所以还要额外地存储左右 子树的指针。

如图：

• 第一个是索弓I的键值。比如我们在id上面创建了一个索弓|,我在用where id =1的 条件查询的时候就会找到索引里面的id的这个键值。
• 第二个是数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
• 第三个，因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于26的时候，走右边，到下一个树的节点，继续判断。

如果是这样存储数据的话，我们来看一下会有什么问题。

2.3 AVL 树用于存储索引数据

索引的数据，是放在硬盘上的。

当我们用树的结构来存储索弓I的时候，访问一个节点就要跟磁盘之间发生一次10操作。InnoDB操作磁盘的最小的单位是一页(或者叫一个磁盘块)，大小是16K(16384 字节)。

那么，一个树的节点必须设计成 16K 的大小，不然就会出现读不完或者读不够的情 况。

如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到16K的容量。

想象一下，我们基于索引査找数据的时候，肯定是希望一次从磁盘加载很多的数据到内存中进行比较，这样就可以尽快拿到完整的数据。如果一个节点只存1个这样的单 元，就需要读更多的节点，发生更多的I/O操作。

如果是机械硬盘时代，每次从磁盘读取数据需要10ms左右的寻址时间，交互次数 越多，消耗的时间就越多。

比如上面这张图，我们一张表里面有6条数据，当我们查询id = 66的时候，要查询 两个子节点，就需要跟磁盘交互3次，如果我们有几百万的数据呢？这个时间更加难以 估计。

我们怎么解决这个问题？

• 第一个就是让每个节点存储更多的数据
• 第二个，节点上的关键字的数量越多，我们的指与十数也越多，也就是意味着可以有 更多的分叉（我们把它叫做”路数”）

因为分叉数越多，树的深度就会减少（根节点是0）。

这样，我们的树是不是从原来的高瘦高瘦的样子，变成了矮胖矮胖的样子？

这个时候，我们的树就不再是二叉了，而是多叉，或者叫做多路。

2.4 多路平衡查找树（B Tree）（分裂、合并）Balanced Tree

这个就是我们的多路平衡查找树，叫做BTree （B代表平衡）。

跟AVL树一样，B树在枝节点和叶子节点存储键值、数据地址、节点引用。

它有一个特点：分叉数（路数）永远比关键字数多1。比如我们画的这棵树，每个节 点存储两个关键字，那么就会有三个指钉指向三个子节点（当然肯定不只存3个这么少）。

比如我们要在这张表里面查找15。

因为15小于17，走左边。

因为15大于12，走右边。

在磁盘块7里面就找到了 15,只用了 3次 IO

这个是不是比AVL树效率更高呢？

那B Tree又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟AVL树有什 么区别？

比如Max Degree (路数)是3的时候，我们插入数据1、2、3,在插入3的时候, 本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有4个指针, 子节点会变成4路，所以这个时候必须进行分裂。把中间的数据2提上去，把1和3变 成2的子节点。

如果删除节点，会有相反的合并的操作。

注意这里是分裂和合并，跟AVL树的左旋和右旋是不一样的。

我们继续插入4和5, B Tree又会出现分裂和合并的操作。

从这个里面我们也能看到，在更新索引的时候会有大量的索引的结构的调整，所以 解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。

节点的分裂和合并，其实就是 InnoDB 页的分裂和合并。

如果索引键值有序，写满一页接着开辟一个新的页：

如果索引键值无序，存储过程造成大量磁盘碎片，带来频繁的page分裂和合并：

2.5 B+树（加强版多路平衡查找树）

B Tree的效率已经很高了,为什么MySQL还要对B Tree进行改良，最终使用了B+Tree 呢？

总体上来说，这个B树的改良版本解决的问题比B Tree更全面。

我们来看一下InnoDB里面的B+树的存储结构：

MySQL 中的B+Tree有几个特点：

• 它的关键字的数量是跟路数相等的；
• B+Tree的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。 目前我们的认知：这里要存放的数据是什么？是完整记录的地址。搜索到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索id=28, 虽然在第一层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜 索，一直到叶子节点。
• B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个 数据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。

我们来看一下B+Tree的数据搜寻过程：

1） 比如我们要查找28，在根节点就找到了键值，但是因为它不是页子节点，所以 会继续往下搜寻，28是［28,66）的左闭右开的区间的临界值，所以会走中间的子节点，然 后继续搜索，它又是［28,34）的左闭右开的区间的临界值，所以会走左边的子节点，最后 在叶子节点上找到了需要的数据。

2） 第二个，如果是范围查询，比如要查询从22到60的数据，当找到22之后，只 需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点，这样就极大地提高 了区间查询效率（不需要返回上层父节点重复遍历查找）。

总结一下，InnoDB中的B+Tree特性带来的优势：

1） 它是BTree的变种，BTree能解决的问题，它都能解决。B Tree解决的两大问题 是什么？（每个节点存储更多关键字；路数更多）

2） 扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以 了，不需要遍历整棵B+Tree拿到所有的数据）

3） B+Tree的磁盘读写能力相对于B Tree来说更强（根节点和枝节点不保存数据区, 所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）

4） 排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）

5） 效率更加稳定（B+Tree永远是在叶子节点拿到数据，所以I0次数是稳定的）

我们举个例子：假设一条记录是［6bytes, 一个叶子节点（一页）可以存储10条记 录。非叶子节点可以存储多少个指针？

假设索弓I字段+指针大小为16字节。非叶子节点（一页）可以存储1000个这样的 单元（键值+指针），代表有1000个指针。

树深度为2的时候，有1000^2个叶子节点，可以存储的数据为1000 * 1000 * 10=10000000 （千万级别）。

在査找数据时一次页的査找代表一次 IO ，也就是说，一张千万级别的表，査询数据 最多需要访问3次磁盘。

树的深度是怎么来的？根据你的键值类型和数据量计算出来的。字段值越大、数据 量越大，深度越大。

所以在 InnoDB 中 B+树 深度一般为1-3层，它就能满足千万级的数据存储。

2.6 为什么不适用红黑树

首先我们要知道红黑树是满足：

从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全部是黑色节点）的2倍。

不使用红黑树主要2点原因：

1、只有两路；

2、不够平衡。

三、B+Tree落地形式

3.1 MylSAM

在MylSAM里面，另外有两个文件:

• 一个是.MYD文件，D代表Data,是MylSAM的数据文件，存放数据记录，比如我 们的user myisam表的所有的表数据。
• 一个是.MYI文件，I代表Index,是MylSAM的索引文件，存放索引，比如我们在 id字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面。一个索引就 会有一棵B+Tree,所有的B+Tree都在这个myi文件里面。

也就是说，在MylSAM里面，索引和数据是两个独立的文件。

MylSAM的B+Tree里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索 引文件MYI中找到键值后，会到数据文件.MYD中获取相应的数据记录。

3.2 InnoDB

在InnoDB的某个索引的叶子节点上，它直接存储了我们的数据。 所以，为什么说在InnoDB中索引即数据，数据即索引，就是这个原因。

但是这里会有一个问题，一张InnoDB的表可能有很多个多索弓|，数据肯定是只有—份的，那数据在哪个索引的叶子节点上呢？

答案是聚集索引（聚簇索引）。

就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。

InnoDB 组织数据的方式就是（聚集）索引组织表（clustered index organize table）。如果说一张表创建了主键索引，那么这个主键索引就是聚集索引，决定数据行的物理存储顺序。

主键索引之外的索引，不会也把完整记录在叶子节点放一份，他们的叶子节点上没有数据怎么检索完整数据？

比如我们在name字段上面建的普通索引：

InnoDB中，主键索引和辅助索引是有一个主次之分的。刚才我们讲了，如果有主键索引，那么主键索引就是聚集索引。其他的索引统一叫做”二级索引”（secondary index）。

二级索引存储的是二级索弓I的键值，例如在name上建立索引，节点上存的是name 的值，qingshanmictom等等（很明显，它的键值逻辑顺序跟物理行的顺序不一致）。

而二级索引的叶子节点存的是这条记录对应的主键的值。比如qingshan id = 1, jack id=4

所以，二级索引检索数据的流程是这样的：

当我们用name索引查询一条记录，它会在二级索引的叶子节点找到 name=qingshan，拿到主键值，也就是id = 1,然后再到主键索引的叶子节点拿到数据。

为什么不存地址而是存键值？因为地址会变化。

从这个角度来说，因为主键索引比二级索引少扫描了一棵 B+Tree （避免了回表）， 它的速度相对会快一些。

但是，如果一张表没有主键怎么办？那完整的记录放在哪个索引的叶子节点？或者, 这张表根本没有索引呢？数据放在哪里？

1、 如果我们定义了主键（PRIMARY KEY），那么 InnoDB 会选择主键作为聚集索引

2、 如果没有显式定义主键，则 InnoDB 会选择第一个不包含有NULL值的唯一索引 作为主键索引。

3、 如果也没有这样的唯一索引，则 InnoDB 会选择内置6字节长的ROWID作为隐 藏的聚集索引，它会随着行记录的写入而主键递增。

select rowid name from 表名;

4、索引的使用原则

4.1 列的离散度

先来看一下列的离散度的公式:

count(distinct(column name)): count。)，列的全部不同值和所有数据行的比例。数据行数相同的情况下，分子越大，列的离散度就越高。

简单来说，如果列的重复值越多，离散度就越低，重复值越少，离散度就越高。

我们不建议大家在离散度低的字段上建立索引。如果在B+Tree里面的重复值太多，MySQL的优化器发现走索引跟使用全表扫描差不了多少的时候，就算建了索引，也不一定会走索引。

4.2 联合索引最左匹配

联合索引在B+Tree中是复合的数据结构，它是按照从左到右的顺序来建立搜索树的 （name在左边，phone在右边）。

从这张图可以看岀来，name是有序的，phone是无序的。当name相等的时候， phone才是有序的。

这个时候我们使用 where name='XXX‘ and phone = '136xx'去査询数据的时候, B+Tree会优先比较name来确定下一步应该搜索的方向，往左还是往右。如果name相同的时候再比较phone。但是如果查询条件没有name，就不知道第一步应该查哪个 节点，因为建立搜索树的时候name是第一个比较因子，所以用不到索引。

什么时候用到联合索引？

所以，我们在建立联合索引的时候，一定要把最常用的列放在最左边。

如下方的联合索引桥，说明的联合索引命中索引的情况：

4.3 覆盖索引

回表: 非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查出索引里面没有的数据，它比基于主键索引的查询多扫描了一棵索引树，这个过程就叫回表。

在二级索引里面，不管是单列索引还是联合索引，如果select的数据列只用从索引中就能够取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引，这样就避免 了回表。

我们先来创建一个联合索引：

-创建联合索引
ALTER TABLE user_innodb DROP INDEX comixd_name_phone;
ALTER TABLE user_innodb add INDEX ' comixd_name_phone' ( name , phone );

Extra 里面值为Using index代表属于覆盖索引的情况。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FtnKtjrV-1648242093154)(D:\soft_install\work_install\typoraImages\image-20220326044550045.png)]

这三个查询语句属于覆盖索引:

EXPLAIN SELECT name,phone FROM user_innodb WHERE name='xxx' AND phone = '13666666666';
EXPLAIN SELECT name       FROM user_innodb WHERE name='xxx' AND phone = '13666666666';
EXPLAIN SELECT phone      FROM user innodb WHERE name='xxx' AND phone = '13666666666';

4.4 索引下推（ICP）

索引条件下推（Index Condition Pushdown)）, 5.6以后完善的功能。只适用于二 级索引。ICP的目标是减少访问表的完整行的读数量从而减少I/O操作。

这里说的下推，其实是意思是把过滤的动作在存储引擎做完，而不需要到Server层过滤。

ICP是默认开启的，也就是说与十对于二级索引，只要能够把条件下推给存储引擎，它就会下推，不需要我们干预：

set optimizer_switch='index_condition_pushdown=on';

索引下推情况的执行计划，Extra 里面值为Using index condition代表属于索引下推的情况。

关闭ICP：

set optimizer_switch='index_condition_pushdown=off';

五、索引的创建与使用

5.1 索引的创建

1、 在用于where 判断 order 排序和join的 on、group by的字段上创建索引

2、 索引的个数不要过多。——浪费空间，更新变慢。

3、 过长的字段，建立前缀索引。

CREATE TABLE ' pre_test' (

' content' varchar(20) DEFAULT NULL,

KEY ' pre idx' (' content' (6))

)ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

4、 区分度低的字段，例如性别，不要建索引。——离散度太低，导致扫描行数过多。

5、 频繁更新的值，不要作为主键或者索引。——页分裂

6、 随机无序的值，不建议作为索引，例如身份证、UUID。——无序，分裂

7、 组合索引把散列性高(区分度高)的值放在前面

8、 创建复合索引，而不是修改单列索引

5.2 什么时候用不到索引？

• 索引列上使用函数、表达式、运算符(是因为它得到的结果是不确定的，无法在B+Tree去匹配值)

• 出现类型隐式转换

• like条件字符前面带%（最左前缀）Index Condition Pushingdown

• 负向查询<> != NOT IN ，不是绝对的

其实，用不用索引，最终都是优化器说了算。

优化器是基于 cost 开销(Cost Base Optimizer)，它不是基于规则(Rule-Based Optimizer), 也不是基于语义。怎么样开销小就怎么来。