一、数据结构

AVL树

B树和B+树的插入、删除图文详解

1 B-tree

B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。

一颗5（m）阶的B树定义如下：

1. 每个结点最多有4（m-1）个关键字。
2. 根结点最少可以只有1个关键字。
3. 非根结点至少有2（Math.ceil(m/2)-1）个关键字。
4. 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5. 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

1.1 B树的插入

如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。
1）根据要插入的key的值，找到叶子结点并插入。
2）判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。
3）以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。

理解：

• 先直接插入【**7】4个数，当插入第5个数【22,39,41,53,97】时候，取中间数41为父结点，然后分开成22,394153,97两边，
• 当子结点达到5个时，就取中间结点到父结点，此时父结点就有两个，当父结点达到5个就又取中间结点进行同样的分裂。

下面以5阶B树为例，介绍B树的插入操作，在5阶B树中，结点最多有4个key,最少有2个key

a）在空树中插入39

此时根结点就一个key，此时根结点也是叶子结点

b）继续插入22，97和41

根结点此时有4个key

c）继续插入53

插入后超过了最大允许的关键字个数4，所以以key值为41为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。

d）依次插入13，21，40，同样会造成分裂，结果如下图所示。

e）依次插入30，27, 33 ；36，35，34 ；24，29，结果如下图所示。

f）插入key值为26的记录，插入后的结果如下图所示。
当前结点需要以27为中心分裂，并向父结点进位27，然后当前结点指向父结点，结果如下图所示。
进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。
分裂后当前结点指向新的根，此时无需调整。

g）最后再依次插入key为17,23, 28,31,32 的记录，结果如下图所示。

分配固定结点大小的方法会存在浪费的情况，比如key为28,29所在的结点，还有2个key的位置没有使用，但是已经不可能继续在插入任何值了，因为这个结点的前序key是27,后继key是30,所有整数值都用完了。所以如果记录先按key的大小排好序，再插入到B树中，结点的使用率就会很低，最差情况下使用率仅为50%。

1.2 B树的删除

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

2）该结点key个数大于等于2（Math.ceil(m/2)-1），结束删除操作，否则执行第3步。

3）如果兄弟结点key个数大于2（Math.ceil(m/2)-1），则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。
有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

理解：5阶B树为例
删除叶子结点

• 删除后，还是有>=2个元素，删除完成
• 删除后 ，只有一剩结点，父结点移动一个下来
  • 父结点移动后结果<2,并且兄弟结点不超过2，被删除后是剩余的结点和兄弟结点进行合并(父结点需要下来)。父结点和父结点也进行合并
  • 父结点移动后结果<2,并且兄弟结点超过2，兄弟结点移动一个到父结点

删除非叶子结点

• 用后继元素去替换需要删除的元素，删除原来的后继元素
  • 原来后继元素>=2，结束
  • 原来后继元素行只剩1个，后继元素的兄弟元素有3+个，父元素移动一个 到后继元素，兄弟元素移动一个到父元素

下面以5阶B树为例，介绍B树的删除操作，5阶B树中，结点最多有4个key,最少有2个key

a）原始状态

b）在上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以删除结束。

c）在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下图所示。

删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示。

d）在上述情况下接着32，结果如下图。

当删除后，当前结点中只key，而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。

当前结点key的个数满足条件，故删除结束。

e）上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。
同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

同理，对于当前结点而言只能继续合并了，最后结果如下所示。
合并后结点当前结点满足条件，删除结束。

2 B+Tree

定义

各种资料上B+树的定义各有不同，一种定义方式是关键字个数和孩子结点个数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子结点个数小1，这种方式是和B树基本等价的。上图就是一颗阶数为4的B+树。
除此之外B+树还有以下的要求。

1）B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。

2）B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

3） m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

4）内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

5）每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

2.1 B+树的插入

1）若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。

2）针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录。插入后，若当前结点key的个数小于等于m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。

3）针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分（包括key），然后将当前结点指向父结点然后重复第3步。

理解：和B树没有什么区别，无非是满5后，用中间那个创建一个父结点（只存索引） ，子节点分裂成（2+3）的形式

下面是一颗5阶B树的插入过程，5阶B数的结点最少2个key，最多4个key。

a）空树中插入5

b）依次插入8，10，15

c）插入16

插入16后超过了关键字的个数限制，所以要进行分裂。在叶子结点分裂时，分裂出来的左结点2个记录，右边3个记录，中间key成为索引结点中的key，分裂后当前结点指向了父结点（根结点）。结果如下图所示。

当然我们还有另一种分裂方式，给左结点3个记录，右结点2个记录，此时索引结点中的key就变为15。

d）插入17

e）插入18，插入后如下图所示

当前结点的关键字个数大于5，进行分裂。分裂成两个结点，左结点2个记录，右结点3个记录，关键字16进位到父结点（索引类型）中，将当前结点的指针指向父结点。

当前结点的关键字个数满足条件，插入结束。

f）插入若干数据后

g）在上图中插入7，结果如下图所示

当前结点的关键字个数超过4，需要分裂。左结点2个记录，右结点3个记录。分裂后关键字7进入到父结点中，将当前结点的指针指向父结点，结果如下图所示。

当前结点的关键字个数超过4，需要继续分裂。左结点2个关键字，右结点2个关键字，关键字16进入到父结点中，将当前结点指向父结点，结果如下图所示。

当前结点的关键字个数满足条件，插入结束。

2.2 B+树的删除

B+树的删除操作
如果叶子结点中没有相应的key，则删除失败。否则执行下面的步骤
1）删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m/2) – 1，删除操作结束,否则执行第2步。

2）若兄弟结点key有富余（大于Math.ceil(m/2) – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行第3步。

3）若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第4步（第4步以后的操作和B树就完全一样了，主要是为了更新索引结点）。

4）若索引结点的key的个数大于等于Math.ceil(m/2) – 1，则删除操作结束。否则执行第5步

5）若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行第6步

6）当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步。

注意，通过B+树的删除操作后，索引结点中存在的key，不一定在叶子结点中存在对应的记录。
下面是一颗5阶B树的删除过程，5阶B数的结点最少2个key，最多4个key。
理解：和B树差不多，只是索引会跟着删除而已

a）初始状态

b）删除22,删除后结果如下图

删除后叶子结点中key的个数大于等于2，删除结束

c）删除15，删除后的结果如下图所示
删除后当前结点只有一个key,不满足条件，而兄弟结点有三个key，可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9，删除结束。

d）删除7，删除后的结果如下图所示
当前结点关键字个数小于2，（左）兄弟结点中的也没有富余的关键字（当前结点还有个右兄弟，不过选择任意一个进行分析就可以了，这里我们选择了左边的），所以当前结点和兄弟结点合并，并删除父结点中的key，当前结点指向父结点。

此时当前结点的关键字个数小于2，兄弟结点的关键字也没有富余，所以父结点中的关键字下移，和两个孩子结点合并，结果如下图所示。

二、B+树与索引

1 线性结构

数组或链表

一个线性表如果存了42亿条数据，想要找到id=100的数据，游标只需爬99格即可返回，但如果id=10000000，就要爬将近1000w个格子才能返回。对于这42亿条数据，平均查询次数是21亿次！！

对于线性结构的数据集合，如果要使用二分查找，那么整个数据都要事先在内存中

2 二叉查找树

如果要找id=6的数据，那么只要比较3次，小于爬格子次数（5次）

在一棵树中找到目标数据所需的比较次数 = 目标数据所在的层级

如果用一棵树来存储42亿条数据，即232=42亿，树的层级是32，最差的情况也只要查32次（需要是二叉平衡树），远远小于线性结构的平均21亿次。

如果是1,2,3,4顺序插入就会变成线性结构

3 二叉平衡树（AVL Tree）

二叉平衡树会在数据插入完毕后自动调整节点，好让“树的层级”不至于太深。

42亿数据中找一条记录最多只需比较32次，有个前提条件：数据必须全部在内存中。

表数据都是持久化到磁盘中的，使用时需要从磁盘中载入内存。涉及磁盘-内存的IO操作。

没有人会直接把500w行数据一次性加载到内存中进行二分查找，内存极有可能顶不住

每一个节点存储“一小块数据”，分多次IO读取每一块数据到内存判断，直到找到匹配的数据。

我们组织数据库的方式只能是：

• 把数据存在磁盘中
• 数据按树结构组织
• 查询时分块读取数据并比较，持续进行磁盘IO读取节点，直到找到目标数据

但查询时分块读取数据，有一点点问题。

IO是非常耗时的，二叉平衡树虽然查找42亿数据最多只需32次，但是32次磁盘IO还是不能接受。

4 B树

响IO次数的关键因素就是树的层级（深度）

那么，如何减少树的层级呢（让树变矮）?

请大家思考一下232中的“2”指的是什么？

二叉平衡树”的“二”，而指数32代表树的层级。也就是说，如果以二叉平衡树的结构组织42亿行数据，那么树的深度是32。如果是“三叉平衡树”呢？

3?? = 232

3的指数大概为21。也就是说，如果用“三叉树”组织数据，那么层级将会减少到21，也就意味着磁盘IO次数最多为21次。

B树“三叉平衡”的B树其实叫“3阶B树”。“N阶B树”每个节点可以存N-1个数据（二叉平衡树每个节点只存1个数据），且每个节点至多可以连接N个子节点。

每次加载一个节点时都可以从磁盘带出更多条数据，从而减少磁盘IO的次数,“空间换时间”

实际上1个节点可以存更多数据，做成N阶B树：

5 B+树与索引

为了尽可能使树“变矮”从而减少磁盘IO，最好的做法是让一个节点尽可能地塞入更多的数据。,我们把每一行数据的主键存进去。

MySQL中也有“页”的概念，但大小为16k，你可以理解为MySQL中的“页”就是上面B树的一个个节点。

假设一张表中数据大小是1K，因为节点最大size是16k，所以每个节点最多只能存16行数据。

如果 bigint类型做主键，一个主键也就8个字节。假设每个主键对应一个addr（指针），MySQL中一个指针为6个字节，那么节点内每个主键-地址这样形式的数据能存16*1024/14=1170个。

所谓的B+树，就是把原先B树中分散在各个节点的数据都“赶到”最底层的叶子节点，非叶子节点只存储主键-addr形式的数据：

最终，一棵3层的B+树，最底下的叶子节点总共能存2000w条数据。

从MySQL学习者的角度而言，我们只需要知道B+树2个很重要的特征：

• 非叶子节点不存数据
• 叶子节点数据用链表相连

所以更详细的版本是：

对比一下B树和B+树：

• B树的节点都会存储整行数据，占用空间大存储addr少，而B+树的非叶子节点只存储主键，能容纳更多addr
• 由于非叶子节点能容纳更多addr，那么同一个节点能指向更多下级节点，所以相同数据量时，B+树通常更加“矮”，IO更少
• B树的查询效率是不稳定的，最好情况是根节点，最差情况是叶子节点，而B+树是稳定的，每次都要查询到叶子节点
• B+树的叶子节点是有序列表，非常便于范围查询

三、索引

对于一般的Java开发而言，SQL优化分为几个层次：

• 索引优化 70%
• 事务及锁 20%
• 读写分离等 10%

其中，索引优化是最重要、也是一般Java开发人员最常用的手段。

索引的类型

• 普通索引
• 唯一索引
• 全文索引
• 空间索引

普通索引就可以组织树结构了，而唯一索引在普通索引的基础上还要求索引列不能重复

实际开发常用的索引只有普通索引和唯一索引，其他的可以不用理会（主键索引其实相当于唯一索引+非NULL）

索引的实现方式

1）B + Tree
2）hash

hash索引，其实就是利用哈希算法为索引列计算得到唯一的存储地址，一般来说这个地址是不会重复的（重复的情况被称为哈希冲突）。

hash计算后没有规律，会被打散

hash索引除了无法进行范围查找外，还不能进行模糊搜索（无法计算得到唯一的值）。

hash索引的优劣势

• 优势：速度非常快，只需一次计算即可得到地址，时间复杂度O(1)，而B+树是O(logn)
• 劣势：不支持模糊查询、范围查询、索引排序（本身就是不规则的，如何利用索引排序呢）

1 索引的创建

索引的创建时机一般有两处：

• 起初，建表时顺便建立索引
• 后期，修改表结构创建索引（一般都是这样，因为很难未卜先知，提前优化等于瞎优化）

这张表有两个索引：主键索引、auditor_id普通索引。

主键索引并不属于上面介绍的4种索引类型之一，但所谓的Primary Key可以看做 唯一索引 + NOT NULL约束。

利用SQL创建索引

-- 1.添加PRIMARY KEY（主键索引） 
ALTER TABLE `table_name` ADD PRIMARY KEY (`column`) ;
-- 2.添加UNIQUE(唯一索引) 
ALTER TABLE `table_name` ADD UNIQUE (`column`);
-- 3.添加INDEX(普通索引) 
ALTER TABLE `table_name` ADD INDEX index_name (`column`);
-- 4.添加FULLTEXT(全文索引) 
ALTER TABLE `table_name` ADD FULLTEXT (`column`);
-- 5.添加联合索引 
ALTER TABLE `table_name` ADD INDEX index_name (`column1`, `column2`, `column3`);

图上可以写成

ALTER TABLE `moneywithdraw` ADD INDEX idx_auditor_id (`auditor_id`);

索引的好坏

索引的优势是：

• 加快查询速度（包括关联查询）
• 加快排序速度（ORDER BY）
• 加快分组速度（GROUP BY）

加快排序、加快分组最终还是体现在加快查询速度上（最左匹配原则）

索引的劣势：

• 创建索引是需要付出代价的，主要体现在维护成本、空间成本和回表成本。也就是说索引能提高查询效率，但往往会降低增删改的速度（字典新增几百个字，需要额外编排目录吧，要多占几页纸吧）
• 如果使用了联合索引，还需要考虑索引失效问题（下篇介绍联合索引）
• 太多的索引会增加查询优化器的选择时间（选择太多也麻烦）

建立索引的原则

创建索引有4个大原则：

• 索引并不是越多越好，联合索引应该优于多个单列索引
• 索引应该建立在区分度高的字段上
• 尽量给查询频繁的字段创建索引，避免为修改频繁的字段创建索引
• 避免重复索引

MySQL常用引擎

MyISAM和InnoDB存储数据的方式是不同的。

MyISAM的每张表在存储时会分为3个文件：

• 表结构
• 表数据
• 索引

也就是说，表数据和索引是分别独立存储的。

而InnoDB的表数据在存储时只分为2个文件：

• 表结构
• 表数据+索引

需要注意的是，InnoDB所有表的数据和索引都在同一个文件里。

2 聚簇索引与非聚簇索引

对于BTREE索引而言，从数据的组织形式来看，索引又可以分为两大类：

• 聚簇索引
• 非聚簇索引

聚簇索引：可以简单理解为索引和数据是“聚合”在一起的

非聚簇索引：数据和索引是分开的。

InnoDB引擎的主键索引查询时无需回表，每一行完整的数据都直接挂在叶子节点下，可以直接返回。也就是说，对于InnoDB的主键索引而言，数据即索引，索引即数据。

是否需要回表其实可以分为两类：主键索引、辅助索引（或者叫二级索引、普通索引）。

若name被加了索引

InnoDB的做法是，辅助索引只存储索引列+主键，必要时进行“回表”操作：

SELECT FROM stu WHERE name=’bravo’中，查询的数据是，也就是整行数据。而上面的辅助索引只存了主键+name，所以必须回表：拿着主键再去跑一遍主键索引，最终返回整行数据。

给MyISAM和InnoDB的索引分类做个简单的总结：

• MyISAM：非聚簇索引，需要回表
• InnoDB：
• 聚簇索引：主键索引，叶子节点是表数据，不需要回表
• 非聚簇索引：辅助索引（唯一索引、普通索引），叶子节点是主键，必要时需要根据主键回表查询

InnoDB每张表只能有一个主键索引，辅助索引则可以有多个。表数据只有一份，挂在主键索引下面。

如有可能，应该尽量避免回表。SQL优化的本质其实就是减少/减小磁盘IO，而回表必然会增加磁盘IO次数。

通常情况下辅助索引查询都是需要回表的，比主键索引查询多扫描一棵索引树（自身+主键索引），实际编写SQL时，应该尽量走主键索引。

那么，什么情况下辅助索引可以避免回表吗？查询的数据刚好等于辅助索引的数据，如查询 name,age 而我们已有index(name,age)的联合索引，就无需回表

索引覆盖

避免回表，非主键索引中就能查询出我们需要的字段，就无需再次查询主键索引

避免SELECT *（提高索引覆盖的记录，查询的字段越多，几率越低）。

索引的字段 >= 查询需要的字段

覆盖索引和联合索引没有必然关系

3 联合索引

3.1 联合索引长啥样？

• 还是一棵树，不会因为是联合索引，就变成多棵树
• 索引节点会存储多列，比如原先单列索引的节点会存储[name, name, name…]，而多列索引的节点内会存储[[name, age], [name, age], [name, age]…]

联合索引的键值数量大于 1（比如上图中有 a 和 b 两个键值），与单个键值的 B+ 树一样，也是按照键值排序的。比如图中 a、b 两个字段的值为 (1,1),(1,2),(1,3),(2,1),(2,2),(2,3)，是按(a,b) 进行排序的。因此，对于 a、b 两个字段都做为条件时，查询是可以走索引的；对于单独 a 字段查询也是可以走索引的。但是对于 b 字段单独查询就走不了索引了，因为在上图，b 字段对应的值为 1,2,3,1,2,3，显然不是有序的，所以走不了 b 字段的索引。

联合索引的建议：

• where 条件中，经常同时出现的列放在联合索引中。
• 把选择性最大的列放在联合索引的最左边。

测试表

use muke; /* 使用muke这个database */
drop table if exists t11; /* 如果表t11存在则删除表t11 */
CREATE TABLE `t11` ( /* 创建表t11 */
`id` int(11) NOT NULL AUTO_INCREMENT,
`a` int(20) DEFAULT NULL,
`b` int(20) DEFAULT NULL,
`c` int(20) DEFAULT NULL,
`d` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (`id`),
KEY `idx_a_b_c` (`a`,`b`,`c`)
) ENGINE=InnoDB CHARSET=utf8mb4 ;
insert into t11(a,b,c) values (1,1,1),(1,2,2),(1,2,1),(2,2,2),(2,1,2),(2,3,3),
(2,4,4),(3,3,3),(4,4,4),(5,5,5),(6,6,6),(7,7,7),(8,8,8),(1,2,3),(1,2,4); /* 写入一些数据 */

3.2 联合索引使用分析

在上面我们知道了联合索引的原理，下面我们一起整理下联合索引的使用场景，理清这些，相信我们会更准确、高效的使用联合索引。

3.2.1 可以完整用到联合索引的情况

这里补充一下 key_len 相关知识点：

explain 中的 key_len 列用于表示这次查询中，所选择的索引长度有多少字节，常用于判断联合索引有多少列被选择了。下表总结了常用字段类型的 key_len：

表一 常用字段类型的 key_len

下面我们列出几种可以完整用到联合索引的情况，并查看其执行计划，然后进行简短的分析：

select * from t11 where a=1 and b=1 and c=1; /* sql1 */

因为 a、b、c 三个字段都是可以为 NULL 的 int 型。根据表1，可以知道三个字段的 key_len 都是 5，所以如果完整使用索引 idx_a_b_c，则 key_len 对应的值为 15。再回到上面 sql1 的执行计划中：key_len 显示是 15，而 key 列对应的是 idx_a_b_c，所以 sql1 完整用到了联合索引 idx_a_b_c。

select * from t11 where c=1 and b=1 and a=1;  /* sql2 */

跟 sql1 的执行计划一样，因此联合索引各字段都做为条件时，各字段的位置不会影响联合索引的使用。

select * from t11 where a=2 and b in (1,2) and c=2;  /* sql3 */

当联合索引前面的字段使用了范围查询，后面的字段做为条件时仍然可以使用完整的联合索引。

联合索引直接就能根据具体的值找到数据

select * from t11 where a=1 and b=2 order by c;  /* sql4 */

联合索引前面的字段做为条件时，对后面的字段做排序可以使用完整的联合索引。

联合索引能够根据a、b条件查找到数据范围时，a,b下的c一定是有序的，根本就不用排序。

select * from t11 where a=1 order by b,c;  /* sql5 */

与 sql4 相似，对联合索引第一个字段做条件筛选时，对后面两个字段做排序可以使用完整的联合索引。

和上面sql一样的，联合索引能够根据a条件查找到数据范围时，a下的b一定是有序的，b下面的c也一定是有序的，你根本就不用排序。

select a,b,c from t11 order by a,b,c;  /* sql6 */

对联合索引的字段同时做排序时（但是排序的三个字段顺序要跟联合索引中三个字段的顺序一致），可以完整用到联合索引。

a、b、c有联合索引，一定是有序的，直接返回数据就行。

3.2.2 只能使用部分联合索引的情况

不符合最左匹配原则

3.2.3 最左匹配原则

不管哪一个，都必须是左边的第一个走了索引后面的才有可能继续使用索引

1）where

假设联合索引是index(a, b, c)，来看几个最左匹配原则的案例：

• WHERE a, b, c ✔️ （=c,b,a也行）
• WHERE a, b ✔️（只能匹配a,b）
• WHERE a, c ✔️（只能匹配a）
• WHERE b, c（❌）

2）order by

对于index(name, age)的索引树， 最底层的数据本身就是先按name，再按age排序的。当ORDER BY的条件刚好是ORDER BY name, age时，直接查询即可，无需排序，因为数据在插入时就按索引顺序排好了。

如果没有利用索引排序，或者无法利用索引排序时，会发生什么呢？

filesort！

所谓filesort是EXPLAIN命令中extra一列的某个指标，当extra出现filesort这个指标时，说明我们的SQL没有走索引排序，而是利用内存或磁盘自己重新排序。

那么，什么情况下会导致ORDER BY无法利用索引排序呢？

以联合索引index(name, age)为例，以下情况无法利用索引排序：

• ORDER BY age, name（字段顺序不一致）
• ORDER BY name DESC, age ASC（字段排序方式不同步，DESC和ASC混着来）

但以下情况仍可以利用索引排序：

• ORDER BY name DESC, age DESC（字段顺序和索引顺序一致即可，全部DESC或ASC都没关系）

总之，如果想利用索引排序，那么ORDER BY的顺序必须符合最左前缀原则，顺序完全一致，且DESC和ASC不能混用。

3）group by

GROUP BY其实可以看成两步：先排序，后归并。

一般对于GROUP BY的优化，就是尽可能让它也走索引排序。当它和联合索引顺序一致时，GROUP BY会跳过排序，直接归并，从而达到优化的目的。

四、哪些情况需要添加索引？

1 数据检索

建议数据检索时，在条件字段添加索引

2 聚合函数

有索引的字段 a 的最大值：

select max(a) from t9_1;

执行时间为 0.00 秒，表示执行时间不超过 10 毫秒。
索引能提升 max() 函数的效率，同理也能提升 min() 函数的效率。

原因是：InnoDB 二级索引树的叶子节点上存放的是主键，而主键索引树的叶子节点上存放的是整行数据，所以二级索引树比主键索引树小。因此优化器基于成本的考虑，优先选择的是二级索引。

因此索引对聚合函数 count(*) 也有优化作用。

3 排序

• 如果对单个字段排序，则可以在这个排序字段上添加索引来优化排序语句；
• 如果是多个字段排序，可以在多个排序字段上添加联合索引来优化排序语句；
• 如果是先等值查询再排序，可以通过在条件字段和排序字段添加联合索引来优化排序语句。

  4 避免回表

因为联合索引中包含了这两个字段的值。像这种索引就已经覆盖了我们的查询需求的场景，我们称为：覆盖索引。比如下面这条 SQL：

select b,c from t9_1 where b=90000;

可直接通过联合索引 idx_b_c 找到 b、c 的值

通过添加覆盖索引让 SQL 不需要回表，从而减少树的搜索次数，让查询更快地返回结果。

5 关联查询

在第 6 节中，我们讲到了关联查询的一些优化技巧，其中一个优化方式就是：通过在关联字段添加索引，让 BNL变成 NLJ 或者 BKA。

6 总结

本节讲解了常见需要添加索引的场景：

• 数据检索时在条件字段添加索引
• 聚合函数对聚合字段添加索引
• 对排序字段添加索引
• 为了防止回表添加索引
• 关联查询在关联字段添加索引

五、 普通索引和唯一索引有哪些区别？

对于普通索引和唯一索引的区别：有普通索引的字段可以写入重复的值，而有唯一索引的字段不可以写入重复的值。其实对于 MySQL 来说，不止这一种区别。

在讨论两者的区别前，我们首先学习一下 Insert Buffer 和 Change Buffer。

1 Insert Buffer

对于非聚集索引的插入时，先判断插入的非聚集索引页是否在缓冲池中。如果在，则直接插入；如果不在，则先放入 Insert Buffer 中，然后再以一定频率和情况进行 Insert Buffer 和辅助索引页子节点的 merge 操作。这时通常能将多个插入合并到一个操作中（因为在一个索引页中），就大大提高了非聚集索引的插入性能。

为什么要增加 Insert Buffer？
增加 Insert Buffer 有两个好处：

• 减少磁盘的离散读取
• 将多次插入合并为一次操作

但是得注意的是，使用 Insert Buffer 得满足两个条件：

• 索引是辅助索引
• 索引不是唯一

  2 Change Buffer

InnoDB 从 1.0.x 版本开始引入了 Change Buffer，可以算是对 Insert Buffer 的升级。从这个版本开始，InnoDB 存储引擎可以对 insert、delete、update 都进行缓存。

影响参数有两个：

• innodb_change_buffering：确定哪些场景使用 Change Buffer，它的值包含：none、inserts、deletes、changes、purges、all。默认为 all，表示启用所有。
• innodb_change_buffer_max_size：控制 Change Buffer 最大使用内存占总 buffer pool 的百分比。默认25，表示最多可以使用 buffer pool 的 25%，最大值50。

为什么唯一索引的更新不使用 Change Buffer ?
原因：唯一索引必须要将数据页读入内存才能判断是否违反唯一性约束。如果都已经读入到内存了，那直接更新内存会更快，就没必要使用 Change Buffer 了。

3 普通索引和唯一索引的区别

通过上面对 Insert Buffer 和 Change Buffer 的了解，也许你已经知道了普通索引和唯一索引的另外一种区别：如果对数据有修改操作，则普通索引可以用 Change Buffer，而唯一索引不行。

在上面讲解 Change Buffer 时，也提到了修改唯一索引必须判断是否违反唯一性约束，其实在 RR 隔离级别下，可能会出现一个比较严重的问题：死锁。

那么查询过程两者的区别呢？
对于普通索引，查找到满足条件的第一个记录，还需要查找下一个记录，直到不满足条件。
对于唯一索引来说，查找到第一个记录返回结果就结束了。

但是 InnoDB 是按页从磁盘读取的，所以很大可能根据该普通索引查询的数据都在一个数据页里，因此如果通过普通索引查找到第一条满足条件所在的数据页，再查找后面的记录很大概率都在之前的数据页里，也就是多了几次内存扫描，实际这种消耗可以忽略不计。

这里总结一下普通索引和唯一索引的隐藏区别：

• 数据修改时，普通索引可以用 Change Buffer，而唯一索引不行。
• 数据修改时，唯一索引在 RR 隔离级别下，更容易出现死锁。
• 查询数据是，普通索引查到满足条件的第一条记录还需要继续查找下一个记录，而唯一索引查找到第一个记录就可以直接返回结果了，但是普通索引多出的查找次数所消耗的资源多数情况可以忽略不计。

4 普通索引和唯一索引如何选择

上面说了普通索引和唯一索引的区别，那么两者应该如何选择呢？
如果业务要求某个字段唯一，但是代码不能完全保证写入唯一值，则添加唯一索引，让这个字段唯一，该字段新增重复数据时，将报类似如下的错：

ERROR 1062 (23000): Duplicate entry '1' for key 'f1'

如果代码确定某个字段不会有重复的数据写入，则可以选择添加普通索引。 因为普通索引可以使用 Change Buffer，并且出现死锁的概率比唯一索引低。

5 总结

本节在讲普通索引和唯一索引的区别时，首先提到了 Insert Buffer，其目的是将多次插入合并。InnoDB 从 1.0.x 版本开始，开始支持增删改操作，统一称为 Change Buffer。

最后再总结下普通索引和唯一索引的区别：

• 有普通索引的字段可以写入重复的值，而有唯一索引的字段不可以写入重复的值。
• 数据修改时，普通索引优于唯一索引，因为普通索引可以用 Change Buffer，并且 RR 隔离级别下，出现死锁的概率比唯一索引低。
• 查询数据时，两者性能差别不大。

六、为什么MySQL会选错索引？

1、show index 的使用

show index from t13;

PRIMARY KEY (id)、KEYidx_a_b(a,b)、KEYidx_create_time(create_time)

对上面几个重要的字段做一下解释：

• Non_unique：如果是唯一索引，则值为 0，如果可以有重复值，则值为 1
• Key_name：索引名字
• Seq_in_index：索引中的列序号，比如联合索引 idx_a_b_c (a,b) ，那么三个字段分别对应 1,2
• Column_name：字段名
• Collation：字段在索引中的排序方式，A 表示升序，NULL 表示未排序
• Cardinality：索引中不重复记录数量的预估值，该值等会儿会详细讲解
• Sub_part：如果是前缀索引，则会显示索引字符的数量；如果是对整列进行索引，则该字段值为 NULL
• Null：如果列可能包含空值，则该字段为 YES；如果不包含空值，则该字段值为 ’ ’
• Index_type：索引类型，包括 BTREE、FULLTEXT、HASH、RTREE 等

show index 各字段的详细描述可以参考官方文档：https://dev.mysql.com/doc/refman/5.7/en/show-index.html。

2、Cardinality 取值

Cardinality 表示该索引不重复记录数量的预估值。
如果该值比较小，那就应该考虑是否还有必要创建这个索引。比如性别这种类型的字段，即使加了索引，Cardinality 值比较小，使用性别做条件查询数据时，可能根本用不到已经添加的索引。

那么 Cardinality 值的统计频率是怎样的呢？

考虑到如果每次索引在发生操作时，都重新统计字段不重复记录数赋给 Cardinality，将会对数据库带来很大的负担。因此 Cardinality 不是每次操作都重新统计的，而是通过采样的方法来完成的。
Cardinality 统计信息的更新发生在两个操作中：INSERT 和 UPDATE。当然也不是每次 INSERT 或 UPDATE 就更新的，其更新时机为：

• 表中 1/16 的数据已经发生过变化
• 表中数据发生变化次数超过 2000000000

Cardinality 值是怎样统计和更新的呢？

InnoDB 表取出 B+ 树索引中叶子节点的数量，记为 a；随机取出 B+ 树索引中的 8 个（这个数量有参数 innodb_stats_transient_sample_pages 控制，默认为 8）叶子节点，统计每个页中不同记录的个数（假设为 b1，b2，b3，…，b8）。则 Cardinality 的预估值为：
（b1 + b2 + b3 + … b8）* a/8

所以 Cardinality 的值是对 8 个叶子节点进行采样获取的，显然这个值并不准确，只供参考。

下面我们来看下统计 Cardinality 涉及到的几个参数：

• innodb_stats_transient_sample_pages：设置统计 Cardinality 值时每次采样页的数量，默认值为 8。
• innodb_stats_method：用来判断如果对待索引中出现的 NULL 值记录，默认为 nulls_equal，表示将 NULL 值记录视为相等的记录。另外还有 nulls_unequal 和 nulls_ignored。nulls_unequal 表示将 NULL 视为不同的记录，nulls_ignored 表示忽略 NULL 值记录。
• innodb_stats_persistent：是否将 Cardinality 持久化到磁盘。好处是：比如数据库重启，不需要再计算 Cardinality 的值。
• innodb_stats_on_metadata：当通过命令 show table status、show index 及访问 information_chema 库下的 tables 表和 statistics 表时，是否需要重新计算索引的 Cardinality。目的是考虑有些表数据量大，并且辅助索引多时，执行这些操作可能会比较慢，而使用者可能并不需要更新 Cardinality。

3、统计信息不准确导致选错索引

在 MySQL 中，优化器控制着索引的选择。一般情况下，优化器会考虑扫描行数、是否使用临时表、是否排序等因素，然后选择一个最优方案去执行 SQL 语句。

而 MySQL 中扫描行数并不会每次执行语句都去计算一次，因为每次都去计算，数据库压力太大了。实际情况是通过统计信息来预估扫描行数。这个统计信息就可以看成 show index 中的 Cardinality。

而从上面说到 Cardinality 的更新原理可以看出，它的值不一定准确的，因此有时可能就是因为它的值不精准导致选错了索引。这种情况可以使用下面的命令重新统计信息：

analyze table t13;

总结

本节介绍了 show index 的各个字段的含义，并重点说明了 Cardinality 的取值原理。

通过学习了 Cardinality 的取值原理，我们知道了它的值只是一个估值，因此当我们遇到它的值与实际值相差很大时，可以考虑使用：analyze table xxx; 重新获取统计信息。

另外举例说明了单次选取的数据量过大也有可能导致优化器选错索引，这种时候，可以尝试使用 force index 让 sql 强制走某个索引。

select a from t13 force index(idx_a) where a>70000 limit 1000;