Mysql中索引相关问题

什么是聚簇索引(主键索引)和辅助索引(二级索引)
InnoDB引擎下有两大类索引，
聚簇索引(clustered index)
普通索引(secondary index)

innoDB中的聚簇索引的所有叶子节点存储了一个表的所有行记录，因此， InnoDB引擎下，每个表必须要有且只有一个聚簇索引。（要查任意一行完整的数据都最终需要到聚簇索引下的叶子节点去查。

1 聚簇索引（主键索引）：
聚簇索引的结构：
聚簇索引就是按照一张表的所有主键值构造的一颗B+树（非叶结点，非叶子节点中的数据都是主键值+对应的孩子节点的指针组成的整体，每个主键索引值+对应的孩子节点的指针组成的整体是一个节点中的一个元素，每个节点中都有多个元素），同时所有叶子节点中存放的数据即为整张表的记录数据（是一个链表结构）。
聚簇索引的叶子节点称为数据页，聚簇索引的这个特性决定了索引组织表中的数据也是索引的一部分。

结构图如下（每个页，就是一个节点）
图片: https://uploader.shimo.im/f/OkRISmWnk6fCRnxR.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
(1) 非叶节点：其中，最上层的节点称为根节点，其他节点中，发起指针的节点称为父节点，指针指向的节点称为孩子节点，它们都是非叶节点。
该节点包含多个<主键id，page_no指针>元组组成的记录，同时，它自身也有个页号（节点号），其中page_no是一个指针，指向了下面的一个非叶节点或叶子节点
多个元素之间通过一个单向链表指针相连，每个非叶节点之间通过两个双向链表指针相连。
如上图，根节点页1包含两条元组记录<1, 2>和<5, 3>，自身页号为1，第一个元组记录中的page_no元素2指向页2这个节点，第二个元组记录中的page_no元素3指向页3这个节点。

如上图，页2节点包含两条元组记录<1, 4>和<3, 5>，第一个元组记录中的page_no元素4指向页4这个节点，第二个元组记录中的page_no元素5指向页5这个节点，两个元组之间通过单向指针连接，组成一个单向链表。

页2和页3节点通过两个个双向链表指针相连

(2) 叶子节点（B+树最下层的所有节点）：该节点包含多个<主键id，所有非主键字段值>元素组成的记录，同时，它自身也有个页号（节点号），多个元素之间通过一个单向链表指针相连，每个叶子节点之间通过两个双向链表指针相连（方便区间查询）。
（注意：多个元素之间通过一个单向链表指针相连，相连是连在索引列上，而不是在普通的列上（所以普通列是无法在叶子节点上进行顺序遍历的，普通列可以二分查找，但是无法进行顺序查找)。，所以根据索引列查询时，效率会更高，尤其是范围查询）

 如上图，图中，非主键字段值我只列了两个字段：user_id和user_name，其他用......省略了，省略字段参见本章《导读》部分创建用户表的SQL，以页7节点为例，该节点包含两条元组记录<7，10007，Mike，I'm Mike，1，17，2006-07-01>和<8，10008，Henry，I'm Henry，1，16，2007-06-07>，这两个元组通过一个单向链表指针相连。

页6和页7两个节点通过两个双向链表指针相连。

聚簇索引的特点：
所有节点内的记录按照主键id升序排列。

2 辅助索引（二级索引）：
单列二级索引的结构：
单列二级索引就是按照每张表的单列普通索引值构建一个B+树（非叶结点，非叶子节点中的数据都是索引值+对应的孩子节点的指针组成的整体，（每个索引值+对应的孩子节点的指针组成的整体是一个节点中的一个元素，每个节点中都有多个元素），同时所有叶子结点中存放的数据，并没有完整的数据，仅包含了元素的索引值本身和对应的主键id，要获取完整的一行数据，必须去反查一次聚簇索引。

      非主键索引，叶子节点=键值+书签。Innodb存储引擎的书签就是相应行数据的主键索引值。

二级索引的特点：
所有节点内的记录（元素）按照索引列值升序排列。

组合索引（复合索引）的二级索引结构（详解1）
参考文献
https://blog.csdn.net/ibigboy/article/details/104571930?depth_1-

组合索引（复合索引）的二级索引树只有一个，而不是多个。

图片: https://uploader.shimo.im/f/zBwjK3JsnZ52Nrsy.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
表T1有字段a,b,c,d,e，其中a是主键，除e为varchar其余为int类型，并创建了一个联合索引idx_t1_bcd(b,c,d)，然后b、c、d三列作为联合索引，联合索引的所有索引列都出现在这个二级索引树上，如下图是联合索引的二级索引树（1竖列是一个节点中的一个元素）（组合索引中，一行数据所有索引列的值，共同组成一个元素）（一个节点中会有多个元素）

（每个元素中，拥有联合索引中每一列的索引值，按最左原则排序）

图片: https://uploader.shimo.im/f/Y5ZGZctJu9QNKdy4.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

联合索引的查找方式
图片: https://uploader.shimo.im/f/7eJ2b7q8yiH1qM5E.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

比如 select * from T1 where b = 12 and c = 14 and d = 3; 也就是T1表中a列为4的这条记录。存储引擎首先从根节点（一般常驻内存）开始查找，第一个索引节点的第一个索引列为1,12大于1，第二个索引节点的第一个索引列为56,12小于56，于是从这俩索引的中间读到下一个节点的磁盘文件地址，从磁盘上Load这个节点，通常伴随一次磁盘IO，然后在内存里去查找。当Load叶子节点的第二个节点时又是一次磁盘IO，比较第一个元素，b=12,c=14,d=3完全符合，于是找到该索引节点下的data元素即主键ID值，再从主键索引树上找到最终数据。

最左匹配原则与联合索引索引结构的关系
之所以会有最左前缀匹配原则和联合索引的索引构建方式及存储结构是有关系的。

首先我们创建的idx_t1_bcd(b,c,d)索引，相当于创建了(b)、（b、c）（b、c、d）三个索引，看完下面你就知道为什么相当于创建了三个索引。

联合索引是优先使用多列索引的第一列构建的索引树，用上面idx_t1_bcd(b,c,d)的例子就是优先使用b列构建，当b列值相等时再以c列排序，若c列的值也相等则以d列排序。我们可以取出索引树的叶子节点看一下，如下图。
图片: https://uploader.shimo.im/f/pULoIYhX846RDhQN.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
我们看索引树节点的排序是按联合索引的第一列也就是b列可以说是从左到右单调递增的，但我们看c列和d列并没有这个特性，它们只能在b列值相等的情况下这个小范围内递增，如第一叶子节点的第1、2个元素和第二个叶子节点的后三个元素。

（重点知识）
由于联合索引是上述那样的索引构建方式及存储结构（索引树节点的排序是按联合索引的第一列也就是b列可以说是从左到右单调递增的），所以联合索引只能从多列索引的第一列开始查找，且是顺序查找，除第一例外必须有上一列。所以如果你的查找条件不包含（第一例）b列如（c,d）、(c）、(d)是无法应用缓存的，以及跨列也是无法完全用到索引如(b,d)，只会用到b列索引。

为啥联合索引会有最佳左前缀原则？

这是由于联合索引的索引树节点的排序是按联合索引的第一列的索引值排序的，可以说是从左到右单调递增的，当第一列相等时，再按第二列递增排序，不能跨列排序，所以一旦我们直接抛弃联合索引第一列或者跨列去查找，那么联合索引久会失效，就要全表扫描.因为第二列或者后续列的索引值的整体顺序不是完全的递增排序，是打乱的。

组合索引（复合索引）的二级索引结构（详解2）

图片: https://uploader.shimo.im/f/IiiPN4VxxGKsq9Bq.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
ALTER TABLE user ADD INDEX index_age_birth (age, birthday);

上图是索引index_age_birthday这个复合索引的结构

(1) 非叶节点：其中，最上层的节点称为根节点，其他节点中，发起指针的节点称为父节点，指针指向的节点称为孩子节点，它们都是非叶节点。
该节点包含多个<组合索引中所有索引值，page_no指针>元素组成的记录，同时，它自身也有个页号（节点号），其中page_no是一个指针，指向了下面的一个非叶节点或叶子节点
多个元素之间通过一个单向链表指针相连，每个非叶节点之间通过两个双向链表指针相连。
因此，上图B+Tree非叶节点中的元组结构为<age，birthday，page_no>。

如上图，根节点页1中包含两条元素记录<15, 2008-02-03, 2>和<17, 2006-03-03, 3>，自身页号为1，第一个元组记录中的page_no元素2指向页2节点，第二个元组记录中的page_no元素3指向页3节点。

如上图，页2节点包含两条元素记录<15, 2008-02-03, 4>和<16, 2007-06-06, 5>，第一个元组记录中的page_no元素4指向页4节点，第二个元组记录中的page_no元素5指向页5节点，两个元组之间通过单向指针连接。

页2节点和页3节点通过两个双向链表指针相连。

(2) 叶子节点（B+树最下层的所有节点）：
该节点包含多个<<组合索引中所有索引值，主键ID>元素组成的记录，同时，它自身也有个页号（节点号），多个元素之间通过一个单向链表指针相连，每个叶子节点之间通过两个双向链表指针相连。

（注意：多个元素之间通过一个单向链表指针相连，相连是连在索引列上，而不是在普通的列上（所以普通列是无法进行顺序遍历的），所以根据索引列查询时，效率会更高，尤其是范围查询）

如上图，页7节点包含两条元素记录<18，2005-03-05，4>和<25，1998-01-02，1>，这两个元素通过一个单向链表指针相连。页6和页7两个节点通过两个双向链表指针相连。

辅助索引有个特点：所有节点内的记录按照索引列值升序排列。比如：index_age_birth索引，首先，记录按照age升序排列，如果age相同，再按照birthday升序排列。

两者的共同点与区别：
共同点
都是B+Tree结构。

两者的区别：

同时，基于B+Tree结构，得出了两种提升查询索引结构性能的算法：二分查找和线性查找。

Mysql的查找算法，查询过程（为什么MySQL能够支撑千万数据规模的快速查询？）

什么是二分查找？
索引数据最好能按顺序排列，这样可以使用「二分查找法」高效定位数据。
假设我们现在用数组来存储索引，比如下面有一个排序的数组，如果要从中找出数字 3，最简单办法就是从头依次遍历查询，这种方法的时间复杂度是 O(n)，查询效率并不高。因为该数组是有序的，所以我们可以采用二分查找法，比如下面这张采用二分法的查询过程图：
图片: https://uploader.shimo.im/f/86PEZMMIBDl71DOD.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

可以看到，二分查找法每次都把查询的范围减半，这样时间复杂度就降到了 O(logn)，但是每次查找都需要不断计算中间位置。

参考文献 https://juejin.cn/post/6959928477638197256#heading-2
讲完InnoDB的索引结构，我们通过上面的结构，大概可以推断出为什么MySQL查询一条或多条记录那么快了。

Innodb中的二分查找
无论是聚簇索引，还是辅助索引，都是一颗B+Tree，所以，通过二分查找，我们可以快速定位到所要查询的记录。

主键查询：根据主键id二分搜索聚簇索引树，可以快速定位到叶子节点上的记录。这部分内容网上资料很多，我就不详细举例讲解了。

辅助索引列查询：我以查找age=25的记录为例，见下图红色箭头，看下辅助索引树的搜索过程：图片: https://uploader.shimo.im/f/JRxYFAoHVQmAHYHO.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

页1（节点1） -> 页3（节点3）：遍历页1（节点1）中的元组（元素）记录，由于页1内第二条记录的age元素为17，查询条件age=25，25 > 17，走右分支，所以，沿着页1指向页3的指针，定位到页3（节点3）节点。

页3 -> 页7：遍历页3中的元组记录，由于页3内第二条记录的age元素为18，查询条件age=25，25 > 18，走右分支，所以，沿着页3指向页7的指针，定位到叶子节点页7。

在页7节点中，遍历页7中的元组记录，第二条元组记录中的age元素值为25，满足age=25的查询条件，所以，定位到记录<25，1998-01-02，1>为辅助索引中所要查找的记录。

最后，拿主键id=1到聚簇索引叶子节点遍历查找，定位到叶子节点上主键id=1的完整记录。

Innodb中的线性顺序查找

由于辅助索引B+Tree上的叶节点内部的记录升序排列，记录与记录之间组成单向链表，节点之间组成双向链表，所以，我可以通过线性查找(即按列值顺序查找)，在叶子节点快速完成一个范围查询。比如，我现在要执行下面这条SQL：

SELECT * FROM user WHERE age >= 15

见上图绿色箭头：

页1 -> 页2：遍历页1中的元组记录，由于页1节点中第一个元组记录的age元素为15，查询条件age>=15，15 >= 15，所以，沿着页1指向页2的指针，定位到页2节点。
页2 -> 页4：遍历页2中的元组记录，由于页2节点中第一个元组记录的age元素为15，查询条件age>=15，同样15 >= 15，所以，沿着页2指向页4的指针，定位到页4节点。
页4 -> 页5 -> 页6 -> 页7：页4、页5、页6和页7节点之间通过双向指针(正向和逆向)连接组成双向链表，每个节点内部所有记录通过一个单向指针(正向)连接组成单向链表，且所有记录按照索引index_age_birth内列值升序排列，即页4 ~ 页7节点内所有记录的age元素一定都大于等于15且升序排列，所以，我们只需从页4内的第一条满足条件的记录开始遍历其指针连接的所有后续记录，找到这些age >= 15的记录的主键id，即2、5、6、8、3、7、4、1，最后，根据这些主键id去聚簇索引查找相应记录就行了，同样，查找方法我会在《InnoDB是顺序查找B-Tree叶子节点的吗？》中详细讲解。

Innodb查找数据过程的精简概述（重要）

对于范围查询
先利用二分查找定位满足条件的第一条记录在哪个叶子结点中，之后从定位到的叶节点内第一条记录开始，向右顺序线性遍历该节点内所有记录即可定位到满足条件的第一条记录，然后，遍历该记录后继所有记录，即可得到满足条件的所有记录。

当然这个顺序遍历不是那么简单的
为了提高顺序遍历效率，引入了槽的概率。具体是先对槽进行二分查找定位满足条件的第一条记录在哪个槽内，然后在该槽所指记录所在的分组内部进行顺序查找即可找到满足条件的第一条记录

根据主键索引的范围查询
接上述步骤，得到满足条件的所有记录后，无需回查直接返回。

根据二级索引的范围查询
接上述步骤，得到满足条件的所有记录后，由于只是所有满足条件的主键值，还要根据主键值去一次一次的回查聚簇索引才能得到需要的完整数据（每个主键值都要回查一次）

对于等值查询
先利用二分查找定位满足条件的记录在哪个叶子结点中，之后从定位到的叶节点内第一条记录开始，向右顺序线性遍历该节点内所有记录即可定位到满足条件的第一条记录，然后继续遍历该记录后继的记录，直到遍历到某条记录不满足等值条件时，停止扫描。如age=10

当然这个顺序遍历不是那么简单的
为了提高顺序遍历效率，引入了槽的概率。具体是先对槽进行二分查找定位满足条件的记录在哪个槽内，然后在该槽所指记录所在的分组内部进行顺序查找即可找到满足条件记录

根据主键索引的范围查询
接上述步骤，得到满足条件的所有记录后，无需回查直接返回。

根据二级索引的范围查询
接上述步骤，得到满足条件的所有记录后，由于二级索引上这些记录只是满足条件的主键值，还要根据主键值去依次回查一次聚簇索引才能得到需要的完整数据

InnoDB具体是如何顺序查找B-Tree叶子节点的
参考文献：https://juejin.cn/post/6960164995548053540

背景与问题的产生
利用二分查找可以快速定位满足条件的第一条记录在哪个叶子结点中
但是如果这个叶子节点内的记录太多，而满足条件的第一条记录又不在定位到的叶节点的头部位置，那么，顺序遍历查找的性能是很差的（O(n)级别），所以Mysql中肯定不是简单的直接去顺序查找叶子结点的

如上图假设每个叶子结点内部有2W个数据（元素），我们通过二分查找能够定位到满足条件的第一条记录在节点4（页4内），但是页4内有2W条数据，我们要一个一个遍历才能找到满足条件的第一条记录（最大可能是O(n)遍历2W下），那么这样顺序遍历查找的性能是很差的

它如何解决这个问题呢？
是的，由于叶子节点的记录是升序排列的，我们完全可以用二分查找，快速定位到叶节点中满足条件的第一条记录在哪里。这样就大大提高了顺序查找的效率。（但是实际真是这样吗）（实际不是这样）

那么，InnoDB具体是怎么做的呢？

引入了槽这个概念

我以用户表索引index_age_birth为例，先来看一下该索引叶子节点的结构：

图片: https://uploader.shimo.im/f/9ktAVFM7NrshIFQd.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
见上图，跟之前我讲的辅助索引B+Tree的叶子节点是不是不一样？是的，之前我讲的比较粗，现在我把它细化了，为了详细讲解一个查询是如何在B+Tree的叶子节点中定位一条记录的。

来仔细看下上面这张图，相比之前的叶子节点，这张图多出来三个元素：

infimum：叶子节点中的虚拟记录，该记录的下一条记录即为叶子节点中的最小记录。比如：图中元组记录<15, 2007-06-06, 6>为页4这个叶子节点中的最小记录。

supremum：叶子节点中的虚拟记录，该记录的上一条记录为叶子节点中的最大记录。比如：图中元组记录<18, 2007-06-10, 12>为页4这个叶子节点中的最大记录。

槽：InnoDB将一个叶子节点内的记录分成几组，每一组叫做slot，也就是槽，这个slot指向分组内最大的一条记录。
这个槽有以下几个特点：

槽内存储的是一个偏移量，这个偏移量是从叶子节点0字节开始计算的。比如：

图中的99，表示从叶子节点0字节开始第99字节的位置为槽0。
图中的252，表示从叶子节点0字节开始第252字节的位置为槽1。
图中的112，表示从叶子节点0字节开始第112字节的位置为槽2。

一个槽指向一个分组中的最大记录。比如，图中，浅黄色框代表分组，所以，槽1指向第二个分组的最大记录<17, 2007-06-10, 11>。

槽与槽之间组成一个无序数组，但槽的下标是有序的。比如，图中，99、252、112这3个偏移量是无序的，但是，槽的下标0、1、2是有序的。

这时，你可能会有个疑问：为什么第一个分组只有1条记录，第二个分组有4条记录，而最后一个分组有2条记录？

因为InnoDB引擎规定：对于infimum记录所在的分组只能有 1 条记录，supremum记录所在的分组拥有的记录条数只能在 1 ~ 8 条之间，剩下的分组中记录的条数范围只能在4 ~ 8条之间。

具体的查找过程
InnoDB查找叶子节点的过程采用的是先对槽进行二分查找定位满足条件的第一条记录在哪个槽内，然后在该槽所指记录所在的分组内部进行顺序查找即可找到满足条件的第一条记录。至于为什么槽内不用二分查找，是因为槽指向的记录所在分组记录总数不会超过8条，所以，没必要使用二分查找来提升查找性能。所以实际上针对记录还是使用的是顺序查找。

以本章《导读》中的SQL为例，详细讲解InnoDB在叶子节点中如何查找第一条满足查询条件的记录。

SELECT * FROM user WHERE age >= 15
复制代码

见下面5张图，该图为索引index_age_birth这个B+Tree的叶子节点：

图片: https://uploader.shimo.im/f/u83bCnCZ66LjoWMN.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
图片: https://uploader.shimo.im/f/fkskJ4gfamAwxpjk.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
1 定位最小下标的槽为low，即图(1)中的槽0，定位最大下标的槽为high，即图(1)中的槽2。

2 (low + high) / 2进行二分查找，即(0 + 2) / 2 = 1，所以，定位槽1，见图(2)，找到槽1指向的记录<17, 2007-06-10, 11>。

3 该记录age = 17，查询条件age的值为15，17 > 15，说明目标记录在该记录左边，所以，见图(2)，high指向槽1，由于low指向槽0，high - low = 1，所以，查找记录在槽0和槽1之间。

4 见图3，将low_rec指向槽0指向的infimum记录，high_rec指向槽1指向的<17, 2007-06-10, 11>记录，从槽0指向的记录infimum开始向右遍历记录。ps：图(3)、(4)、(5)为了更清晰地描述槽指向记录所在的分组内部的查找过程，将槽移除了。

5 遍历到第二条记录<15, 2007-06-06, 6>，见图(4)，该记录age = 15，查询条件age的值为15，15 = 15，所以，该记录为满足查询条件的第一条记录，low_rec指向该记录。

6 遍历到第三条记录<16, 2007-06-08, 8>，见图(5)，该记录age = 16，查询条件age的值为15，16 > 15，所以，high_rec指向该记录。

7 high_rec和low_rec间隔1，说明查找结束，最终，定位满足查询条件age>=15的第一条记录为<15, 2007-06-06, 6>。

在这个查找过程中，你可能有个疑问，我都已经在第5步找到了满足条件的第一条记录，为什么还要进行第6步？

因为这个查找过程是一个通用算法，假设我们要查找age = 16的记录，那么，页4中包含两条满足条件的记录，结合上面的查找算法，是不是要执行到第6、7步才能找到所有匹配的记录？所以，InnoDB采用了该通用查找算法，覆盖age >= 15和age = 16两种情况。

InnoDB直接对叶子节点记录进行二分查找不香吗？为什么要引入槽的概念查找索引树叶子节点，即对槽二分查找，槽指向记录所在的分组内顺序查找？

直接对叶子节点记录进行二分法查找更适合对单条记录的搜索，而对槽二分法更适合进行范围查找，范围查找应该是使用场景更多的更普遍的，并且兼容了单条记录的查找，且如果查找的记录都集中在叶子节点的最左边，那么，使用二分查找可能比顺序查找更慢了，是不是？
这也是为什么设计槽的时候，一个槽里面的记录数不会很多的原因

为什么设计槽的时候，一个槽里面的记录数最大为8

slot方式明显为了提高索引查询速度，每一个slot分配1到8个行记录。如果等值查询，先通过slot二分查找，找到对应的slot，然后在slot内部顺序查询。如果是范围查询，查询效率提升的更明显。但是，如果如果一个叶子节点内行不是很多，使用slot的方式并没有太多优势甚至是更慢，且如果我们要查找的记录都集中在叶子节点的最左边，那么，使用二分查找可能比顺序查找更慢了。

在MySQL内部统一使用slot二分查找，slot内部顺序查找来完成记录的定位，MySQL正是因为考虑到了一个页内记录不多和记录集中在一边的的情况，才限制了一个slot里最多8条记录，这样就可以兼顾一个页内少量记录和大量记录的查找效率

小结

总结一下本章讲解的内容：

槽：将一个叶子节点中的数据进行分组，槽指向每组中最大的一条记录，槽中存储的是其指向的记录在叶子节点内的偏移量，该偏移量是相对叶子节点0字节计算得到的。

InnoDB查找索引树叶子节点的过程：先对槽进行二分查找，然后对槽指向的记录所在的分组内顺序查找。

总结
综上所述，我们得出了为什么MySQL查询一条或多条记录那么快的原因：

二分查找：
排除了搜索过程中无需遍历的节点。（每次最多能过滤一半的节点）
可以快速定位满足条件的记录在哪个叶节点中

线性顺序查找+对槽的二分查找：
无需反复从根节点搜索满足条件的节点记录，而是先从二分查找定位到的叶子节点中，找到满足条件的第一条记录，然后遍历该记录后继所有记录，即可得到满足条件的所有记录（这是由于无论是聚簇索引，还是二级索引它们叶子结点中的数据都是按索引值升序排序的。

并且由于叶子结点中的元素数（记录数）可能比较多，导致顺序查找效率低，Mysql还引入了槽的概念，槽：将一个叶子节点中的数据进行分组，槽指向每组中最大的一条记录，槽中存储的是其指向的记录在叶子节点内的偏移量，该偏移量是相对叶子节点0字节计算得到的。

实际具体的查找过程是先对槽进行二分查找定位满足条件的第一条记录在哪个槽内，然后在该槽所指记录所在的分组内部进行顺序查找即可找到满足条件的第一条记录

当然这个顺序遍历不是那么简单的

对于范围查询是先对槽进行二分查找定位满足条件的第一条记录在哪个槽内，然后在该槽所指记录所在的分组内部进行顺序查找即可找到满足条件的第一条记录

对于等值查询是是先对槽进行二分查找定位满足条件的记录在哪个槽内，然后在该槽所指记录所在的分组内部进行顺序查找即可找到满足条件记录

注意
（注意：多个元素之间通过一个单向链表指针相连，相连是连在索引列上，而不是在普通的列上（所以普通列是无法进行顺序遍历的），所以根据索引列查询时，效率会更高，尤其是范围查询）

什么是回表（回表查询）（回查）
概念：
当所要需要的字段不在当前非主键索引树上时，需要通过叶子节点的主键值去主键索引上获取对应的行数据，这样就可以获取所需要的字段进行下一步的操作，这个过程称为回表操作。

示例 1 （组合索引范围查询）
在这里有张用户表 user，记录着用户的姓名，性别，身高，年龄等信息。表中 id 是自增主键，(name,sex) 是联合索引，现在需要查找所有姓王的男性信息。
图片: https://uploader.shimo.im/f/qXyuoKcFrFIoRsrQ.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

它的实现原理是什么呢？
根据联合索引最左前缀原则，先在联合索引（非主键索引）的二级索引树上找到所有name索引值是王XX的节点，之后二级索引树上每个满足条件的索引值对应的叶子节点中的主键值都要再回到聚簇索引树上查找到对应的行数据，再对比是否为当前所要查找的性别，是则取出则行数据。(其实明明联合索引树上每个节点就有性别索引列的值，还跑到聚簇索引树上去查一遍完整的行数据不是多次一举，浪费性能吗）

原理图如下
图片: https://uploader.shimo.im/f/E9saag0lnQr1zz03.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

示例 2 （深度分页）
select * from t_record where age > 10 limit 10000 10
limit m n :
必须先找到前面m-1条数据，之后從第m條开始取n条数据，因为要保证m到m+n条数据与前m-1条数据不同（保证m到m+n条数据不是前m-1行数据）。
（我们必须先找到前面1W条数据，因为我们不知道第1W到第1W+10条记录从聚簇索引叶子结点的什么位置上开始去取，取前面可能就不是第1W+10条记录，取后面可能就是大于第1W+10条记录，所以我们直接找到第1W条记录的位置，在它的位置后取10条即可）

原理：Mysql会先从二级索引中找到索引值为10的起始点，之后找到所有索引值大于10的节点以及它们对应的叶子节点上的主键ID（肯定大于1W个），然后根据主键ID去回查聚簇索引中的数据（会持续1W次），找到第1W条数据后，开始取10条数据，这个过程也是回查，所以一共回查1W+10次才找到满足要求的10条记录。

回表的过程：
（1）先通过普通索引定位到主键值id；
（2）再根据主键值到聚集索引中查询完整的数据(然后根据主键值去聚簇索引中的 B+ 树中检索到对应的叶子节点，然后获取整行数据)；

这就是所谓的回表查询，先定位主键值，再定位行记录，它的性能较扫一遍索引树更低。也是深度分页导致性能下降的最主要的原因

如何解决回表
1 使用覆盖索引
2 使用Mysql5.6及之后的版本的索引下推功能。

覆盖索引
覆盖索引: 要查询出的数据只包含索引列（主键索引列或者普通索引列）
（要查询出来的字段，都是索引字段，这样就不用去回查，不管是主键索引，还是普通索引即可）

如要查询的字段是普通索引，二级索引中的非叶结点和非叶子结点都是索引值，直接返回即可无需回查，如要查询的字段是主键索引，直接在聚簇索引中查更加不会回表）

索引下推

概念：
索引下推主要是减少了不必要的回表操作（可以有效的减少回表次数，但减少到0了）。对于索引树中查找出来的数据，先过滤掉不符合条件的，其余的再去主键索引树上查找。

5.6版本后加入的新特性，即大名鼎鼎的索引下推，是MySQL关于减少回表次数的重大优化。

示例与过程
假设又有一个需求，要求匹配姓名第一个字为陈，年龄为20岁的用户、
联合索引（name，age）
SELECT * from user where name like ‘陈%’ and age=20

Mysql5.6之前的版本（没有使用索引下推的）
5.6之前的版本是没有索引下推这个优化的，因此执行的过程如下图：

图片: https://uploader.shimo.im/f/XhPJKWcA3n9N5Hcy.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

根据最左匹配原则会先忽略age这个字段，直接通过name进行查询，在(name，age)这课联合二级索引树上查找到了两个结果对应的叶结点的主键id分别为2,1，然后拿着取到的id值一次次的回表查询，因此这个过程需要回表两次。

Mysql5.6及之后版本（使用到索引下推）
5.6版本添加了索引下推这个优化，执行的过程如下图：

图片: https://uploader.shimo.im/f/joQGWvzhT2XdM6CO.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

InnoDB并没有忽略age这个字段，，直接通过name进行查询，在(name,age)这课二级索引树上查找到了两个结果对应的叶结点的主键id分别为2,1，然后Mysql在name字段的二级索树引内部就判断了age是否等于20，对于不等于20的记录直接跳过，因此在(name,age)这棵索引树中只匹配到了一个记录，此时拿着这个id去主键索引树中回表查询全部数据，这个过程只需要回表一次。

有效的减少了回表的次数

解析了上述的语句，如下图：
图片: https://uploader.shimo.im/f/2hMnaDTIfYdrOszI.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
根据explain解析结果可以看出Extra的值为Using index condition，表示已经使用了索引下推。

适用场景
索引下推一般可用于所求查询字段（select列）不全是联合索引的字段，查询条件为多条件查询且查询条件子句（where/order by）字段全是联合索引。对于深度分页不是很适合

建立索引的建议
建索引时，除了主键索引外，建其他普通索引时，如果有多个索引列时，最好建成组合索引并且把辨识度高的字段放在前面，不然会浪费很多空间，因为每个单列的索引都为自己构建一个b+树，且如果有多个单列索引，当有多个单列索引同时做查询条件时，容易导致索引下推失效。
带来的是性能和空间的问题。

此外我们要注意的是，一个字段可以同时出现在多个索引中。
比如一个字段即是单独的一个索引，也是组合索引中的部分

为什么Innodb索引结构要用 B+ 树，为什么不用普通二叉树或平衡二叉树？
怎样的索引的数据结构是好的（如何设计一个适合 MySQL 索引的数据结构）
可以从几个维度去看这个问题，查询是否够快，效率是否稳定，存储数据多少，以及查找磁盘次数，为什么不是普通二叉树，为什么不是平衡二叉树，为什么不是B树，而偏偏是 B+ 树呢？
能在尽可能少的磁盘的 I/O 操作中完成查询工作；
要能高效地查询某一个记录，也要能高效地执行范围查找；

可以看到，二分查找法每次都把查询的范围减半，这样时间复杂度就降到了 O(logn)，但是每次查找都需要不断计算中间位置。

什么是二分查找树？
用数组来实现线性排序的数据虽然简单好用，但是插入新元素的时候性能太低。
因为插入一个元素，需要将这个元素之后的所有元素后移一位，如果这个操作发生在磁盘中呢？这必然是灾难性的。因为磁盘的速度比内存慢几十万倍，所以我们不能用一种线性结构将磁盘排序。
其次，有序的数组在使用二分查找的时候，每次查找都要不断计算中间的位置。
那我们能不能设计一个非线形且天然适合二分查找的数据结构呢？
有的，请看下图这个神奇的操作，找到所有二分查找中用到的所有中间节点，把他们用指针连起来，并将最中间的节点作为根节点。
图片: https://uploader.shimo.im/f/2IWSyh4x0vimLWMR.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

怎么样？是不是变成了二叉树，不过它不是普通的二叉树，它是一个二叉查找树。
二叉查找树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点，这样我们在查询数据时，不需要计算中间节点的位置了，只需将查找的数据与节点的数据进行比较。
假设，我们查找索引值为 key 的节点：
如果 key 大于根节点，则在右子树中进行查找；
如果 key 小于根节点，则在左子树中进行查找；
如果 key 等于根节点，也就是找到了这个节点，返回根节点即可。
二叉查找树查找某个节点的动图演示如下，比如要查找节点 3 ：
图片: https://uploader.shimo.im/f/FgS8wquOsjH161GG.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

另外，二叉查找树解决了插入新节点的问题，因为二叉查找树是一个跳跃结构，不必连续排列。这样在插入的时候，新节点可以放在任何位置，不会像线性结构那样插入一个元素，所有元素都需要向后排列。
下面是二叉查找树插入某个节点的动图演示：

图片: https://uploader.shimo.im/f/6PVg82HcQIrKomLI.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

因此，二叉查找树解决了连续结构插入新元素开销很大的问题，同时又保持着天然的二分结构。

那是不是二叉查找树就可以作为索引的数据结构了呢？
不行不行，二叉查找树存在一个极端情况，会导致它变成一个瘸子！
当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)，如下动图演示：
图片: https://uploader.shimo.im/f/O4VSdnnvl49AT7Gf.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

由于树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作（假设一个节点的大小「小于」操作系统的最小读写单位块的大小），也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以树的高度越高，就会影响查询性能。
二叉查找树由于存在退化成链表的可能性，会使得查询操作的时间复杂度从 O(logn)降低为 O(n)。
而且会随着插入的元素越多，树的高度也变高，意味着需要磁盘 IO 操作的次数就越多，这样导致查询性能严重下降，再加上不能范围查询，所以不适合作为数据库的索引结构。

什么是自平衡二叉树？
为了解决二叉查找树会在极端情况下退化成链表的问题，后面就有人提出平衡二叉查找树（AVL 树）。
主要是在二叉查找树的基础上增加了一些条件约束：每个节点的左子树和右子树的高度差不能超过 1。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn) 。平衡二叉树查找、插入和删除在平均和最坏的情况下都是O(logn)
下图是每次插入的元素都是平衡二叉查找树中最大的元素，可以看到，它会维持自平衡：
图片: https://uploader.shimo.im/f/HoGiSM3dnVp3cLrZ.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

除了平衡二叉查找树，还有很多自平衡的二叉树，比如红黑树，它也是通过一些约束条件来达到自平衡，不过红黑树的约束条件比较复杂，不是本篇的重点重点，大家可以看《数据结构》相关的书籍来了解红黑树的约束条件。
下面是红黑树插入节点的过程，这左旋右旋的操作，就是为了自平衡。
图片: https://uploader.shimo.im/f/r7s8w6C3CgYPtWmH.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这棵树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。

但由于旋转的耗时，AVL树在删除数据时效率很低。在删除操作较多时，维护平衡所需的消耗可能高于其带来的好处，因此AVL实际应用并不广泛。

此外不管平衡二叉查找树还是红黑树，都会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。

比如，下面这个平衡二叉查找树的高度为 5，那么在访问最底部的节点时，就需要磁盘 5 次 I/O 操作。
图片: https://uploader.shimo.im/f/sqizi9DrKXjteGNJ.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

根本原因是因为它们都是二叉树，也就是每个节点只能保存 2 个子节点，如果我们把二叉树改成 M 叉树（M>2）呢？
比如，当 M=3 时，在同样的节点个数情况下，三叉树比二叉树的树高要矮。
图片: https://uploader.shimo.im/f/uwfA65jaN2rcl8aa.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

因此，当树的节点越多的时候，并且树的分叉数 M 越大的时候，M 叉树的高度会远小于二叉树的高度。

什么是 B 树（一种多叉树）
自平衡二叉树虽然能保持查询操作的时间复杂度在O(logn)，但是因为它本质上是一个二叉树，每个节点只能有 2 个子节点，那么当节点个数越多的时候，树的高度也会相应变高，这样就会增加磁盘的 I/O 次数，从而影响数据查询的效率。
为了解决降低树的高度的问题，后面就出来了 B 树和B+树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。
B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。
假设 M = 3，那么就是一棵 3 阶的 B 树，特点就是每个节点最多有 2 个（M-1个）数据和最多有 3 个（M个）子节点，超过这些要求的话，就会分裂节点，比如下面的的动图：
图片: https://uploader.shimo.im/f/ImUPMB5E2zRgP9ss.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

我们来看看一棵 3 阶的 B 树的查询过程是怎样的？
图片: https://uploader.shimo.im/f/FTaoUDaprLom1dxL.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

假设我们在上图一棵 3 阶的 B 树中要查找的索引值是 9 的记录那么步骤可以分为以下几步：
与根节点的索引(4，8）进行比较，9 大于 8，那么往右边的子节点走；
然后该子节点的索引为（10，12），因为 9 小于 10，所以会往该节点的左边子节点走；
走到索引为9的节点，然后我们找到了索引值 9 的节点。
可以看到，一棵 3 阶的 B 树在查询叶子节点中的数据时，由于树的高度是 3 ，所以在查询过程中会发生 3 次磁盘 I/O 操作。
而如果同样的节点数量在平衡二叉树的场景下，树的高度就会很高，意味着磁盘 I/O 操作会更多。所以，B 树在数据查询中比平衡二叉树效率要高。

但是 B 树的每个节点都包含数据（索引+记录），而用户的记录数据的大小很有可能远远超过了索引数据，在页空间不变的情况下，就需要有更多的节点，更多的节点就意味着树的高度的增加，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。

而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，「非 A 记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非 A 记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。

另外，如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降。

什么是 B+ 树（也是一种多叉树）
B+ 树就是对 B 树做了一个升级，MySQL 中索引的数据结构就是采用了 B+ 树，B+ 树结构如下图：

图片: https://uploader.shimo.im/f/VJMUaJXBP0sZ4sFi.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

B+ 树与 B 树差异的点，主要是以下这几点（以聚簇索引的B+树为例子）：
叶子节点（最底部的节点）才会存放实际数据（主键索引值+每条记录所有字段的数据），非叶子节点只会存放主键索引值；

所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；

非叶子节点的主键索引值也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。

非叶子节点中有多少个子节点，这个非叶子节点中就有多少个主键索引值；

下面通过三个方面，比较下 B+ 和 B 树的性能区别。

1、单点查询
B 树进行单个索引查询时，最快可以在 O(1) 的时间代价内就查到，而从平均时间代价来看，会比 B+ 树稍快一些。
但是 B 树的查询波动会比较大，因为每个节点即存索引又存记录，所以有时候访问到了非叶子节点就可以找到索引，而有时需要访问到叶子节点才能找到索引。

B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少。且B树的查询效率不稳定，B+树的查询效率较稳定（因为B+树的每次查询过程中，都需要遍历从根节点到叶子节点的某条路径。所有索引值的查询路径长度相同，导致每一次查询的效率相当。）

2、插入和删除效率
B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快，
比如下面这个动图是删除 B+ 树某个叶子节点节点的过程：

图片: https://uploader.shimo.im/f/alv1L81b37MdhzOv.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

注意，：B+ 树对于非叶子节点的子节点和索引的个数，定义方式可能会有不同，有的是说非叶子节点的子节点的个数为 M 阶，而索引的个数为 M-1（这个是维基百科里的定义），因此我本文关于 B+ 树的动图都是基于这个。但是我在前面介绍 B+ 树与 B+ 树的差异时，说的是「非叶子节点中有多少个子节点，就有多少个索引」，主要是 MySQL 用到的 B+ 树就是这个特性。

甚至，B+ 树在删除根节点的时候，由于存在冗余的节点，所以不会发生复杂的树的变形，比如下面这个动图是删除 B+ 树根节点的过程：
图片: https://uploader.shimo.im/f/rCE2qG14QVzrZIAP.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

B+ 树的插入也是一样，有冗余节点，插入可能存在节点的分裂（如果节点饱和），但是最多只涉及树的一条路径。而且 B+ 树会自动平衡，不需要像更多复杂的算法，类似红黑树的旋转操作等。
因此，B+ 树的插入和删除效率更高。

3、范围查询
B 树和 B+ 树等值查询原理基本一致，先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点查找。
因为 B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助，比如说我们想知道 12 月 1 日和 12 月 12 日之间的订单，这个时候可以先查找到 12 月 1 日所在的叶子节点，然后利用链表向右遍历，直到找到 12 月12 日的节点，这样就不需要从根节点查询了，进一步节省查询需要的时间。
而 B 树没有将所有叶子节点用链表串联起来的结构，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。
因此，存在大量范围检索的场景，适合使用 B+树，比如数据库。而对于大量的单个索引查询的场景，可以考虑 B 树，比如 nosql 的MongoDB。

MySQL 中的 B+ 树（对传统的B+树进行了一些加强））
MySQL 的存储方式根据存储引擎的不同而不同，我们最常用的就是 Innodb 存储引擎，它就是采用了 B+ 树作为了索引的数据结构。
下图就是 Innodb 里的 B+ 树：
图片: https://uploader.shimo.im/f/gy6dSqmV2UOxCFKH.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

但是 Innodb 使用的 B+ 树有一些特别的点，比如：（它对B+树进行了一些加强）
B+ 树的叶子节点之间是用「双向链表」进行连接，这样的好处是既能向右遍历，也能向左遍历。
B+ 树点节点内容是数据页，数据页里存放了用户的记录以及各种信息，每个数据页默认大小是 16 KB。（数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页（默认是16k)，这样每个节点只需要一次I/O就可以完全载入内存。）

Innodb 根据索引类型不同，分为聚集和二级索引。他们区别在于，聚集索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚集索引的叶子节点，而二级索引的叶子节点存放的是主键值，而不是实际数据。
因为表的数据都是存放在聚集索引的叶子节点里，所以 InnoDB 存储引擎一定会为表创建一个聚集索引，且由于数据在物理上只会保存一份，所以聚簇索引只能有一个，而二级索引可以创建多个。
更多关于 Innodb 的 B+ 树，可以看我之前写的这篇：从数据页的角度看 B+ 树。

1）为什么不是普通二叉树？

如果采用二叉查找树作为索引，并且把id作为主键索引且id自增，那么二叉查找树就变成了一个单支树，相当于链表查询查询效率低。
图片: https://uploader.shimo.im/f/l8EL2P1LlTORJWIV.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

普通二叉树，很容易两边不平衡，导致查询效率不稳定。

2）为什么不是平衡二叉树（AVL）呢？

为了解决上述二叉搜索树的问题，引入了平衡得到二叉树。

AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏的情况下都是O(logn).

但由于旋转的耗时，AVL树在删除数据时效率很低。在删除操作较多时，维护平衡所需的消耗可能高于其带来的好处，因此AVL实际应用并不广泛。

此外不管平衡二叉查找树还是红黑树它们都是二叉树（也就是每个节点只能保存 2 个子节点），都会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。所以就有了B树和B+树这种多叉树的出现，多叉树的话每个节点可以保存多个子节点，那么树的高度就会降低，IO操作次数就会减少。

3 为什么不是红黑树
红黑树也是一种自平衡的树

问题与AVL树相似，是一种二叉树也就是每个节点只能保存 2 个子节点），都会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率，树的高度随着数据量增加而增加，IO代价非常高。所以就有了B树和B+树这种多叉树的出现，多叉树的话每个节点可以保存多个子节点，那么树的高度就会降低，IO操作次数就会减少。

4 为什么不是Hash：
虽然可以快速定位，但是没有顺序，IO复杂度高；
基于Hash表实现，只有Memory存储引擎显式支持哈希索引；
适合等值查询，如=、in()、<=>，不支持范围查询；
因为不是按照索引值顺序存储的，就不能像B+Tree索引一样利用索引完成排序；
Hash索引在查询等值时非常快；
因为Hash索引始终索引的所有列的全部内容，所以不支持部分索引列的匹配查找；
如果有大量重复键值得情况下，哈希索引的效率会很低，因为存在哈希碰撞问题。

5 为什么不是 B 树而是 B+ 树呢？（重点）

原因1，相对于B树，空间利用率更好，IO次数少，查询效率高

磁盘存取原理
上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。
图6是磁盘的整体结构示意图。
图片: https://uploader.shimo.im/f/QiBozlsbQKW5jgKz.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
图6
一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。
图7是磁盘结构的示意图。
图片: https://uploader.shimo.im/f/9jpwyPtBMVfyOBB5.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
图7
盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。
当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

首先介绍一下磁盘预读与局部性原理
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费（需要有寻道时间和旋转时间），磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页（默认是16k)，这样每个节点只需要一次I/O就可以完全载入内存。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了获取一个节点的数据时只需一次I/O。

innodb中页的默认大小是16KB，即每个节点的大小是16KB（那么每次就可以预读16K的整数倍的数据到内存中去）

示例
对于B树的结点中每个元素里面要存储的是键值，指针，和完整的数据，假设我们有1600KB数据，每个节点的大小是16kb,每个数据的大小是4Kb，键值（索引值）（1Kb）+指针(3kb)的大小是4kb,那么每个元素（索引值+指针+数据共同组成一个元素）的大小就是8Kb,意味着每个节点只能存储两个元素，这样1600KB数据需要400个Key(元素)每个。那么就需要200个节点，

而对于B+树,键值（索引值）（1Kb）+指针的大小是4KB，即每个元素的大小是4kb,意味着，每个节点可以存储4个元素。那么只需要100节点就可以存储下400个Key(元素)，节点越多意味着树的高度的增加，B-树/B+树的特点就是每层节点数目非常多，层数少，目的就是为了减少磁盘的IO次数，（每次检索的最大IO次数，最多就是树的高度），同样大小的数据情况下，B树的每个元素的大小要更大，由于每个节点的大小是有限制的，所以B树需要的节点数量要大的多，则它树的高度要更大，意味着每次检索的最大IO次数也要更大，这样查询速度（效率）就会下降，IO开销变大

原因2 DML时效率更高
因为B+树的叶子节点包含所有元素（索引值）和对应的数据，并以有序的链表结构存储（有顺序访问指针），这样可很好提高增删效率。

主要是删除和插入操作效率更高。

B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快，
比如下面这个动图是删除 B+ 树某个叶子节点节点的过程：

B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂，比如删除根节点中的数据，可能涉及复杂的树的变形，比如下面这个动图是删除 B 树根节点的过程：
图片: https://uploader.shimo.im/f/ayoGLYJihpHPUxMQ.gif?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
B+ 树的插入也是一样，有冗余节点，插入可能存在节点的分裂（如果节点饱和），但是最多只涉及树的一条路径。而且 B+ 树会自动平衡，不需要像更多复杂的算法，类似红黑树的旋转操作等。
因此，B+ 树的插入和删除效率更高。

原因3 B+树的查询效率更加稳定，
因为B+树的每次查询过程中，都需要遍历从根节点到叶子节点的某条路径。所有索引值的查询路径长度相同，导致每一次查询的效率相当。

原因4 区间查找访问的效率更高

Mysql使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针，使查找，排序查找，分组查找以及去重查找变得异常简单，增加了区间查找访问的效率

Mysql使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针
图片: https://uploader.shimo.im/f/ucHxOkP11vrOszFv.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，而且数据是按照顺序排列的，链表连着的。那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

MySQL前缀索引（如何解决索引字段值过长的问题）

有时需要在很长的字符列（如BLOB、TEXT或很长的VARCHAR类型的列）上创建索引，这会造成索引特别大且慢。如邮箱啊，电话号码啊等场景（索引字段中值越长，索引的效率就越低，占用的空间也越多，DML操作效率也是越低）

示例
CREATE TABLE author (
id INT(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT ‘主键’,
name VARCHAR(32) NOT NULL COMMENT ‘姓名’,
gender TINYINT(1) NOT NULL COMMENT ‘性别，0-男，1-女’,
age TINYINT(3) NOT NULL DEFAULT ‘0’ COMMENT ‘年龄’,
email VARCHAR(32) NOT NULL DEFAULT ‘’ COMMENT ‘邮箱’,
homepage VARCHAR(128) NOT NULL DEFAULT ‘’ COMMENT ‘主页’,
add_time TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT ‘添加时间’,
update_time TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT ‘修改时间’,
PRIMARY KEY (id)
) ENGINE=INNODB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

// email列创建前缀索引
CREATE INDEX idx_author_email ON author(email(3));

解决方案
为了避免产生大且慢的索引，一种策略是使用MySQL索引类型中提到过的模拟哈希索引，另一种策略就是使用前缀索引。（索引字段中值越长，索引的效率就越低，DML操作效率也是越低）

优缺点
优点：
前缀索引就是选择索引列的最左n个字符来建立索引。这样就大大节约了索引空间，进而提高索引效率。

缺点就是：
MySQL无法使用前缀索引做ORDER BY 、GROUP BY 和覆盖扫描。（当然我们一般不会用字符型去做排序，一般都是主键汇总时间字段，用这种字段去做分组的情况也是比较少的）

索引跳跃扫描（8.0.13才支持）
介绍与示例
mysql 8.0.13开始支持 index skip scan 也即索引跳跃扫描。该优化方式支持某些sql在不符合组合索引最左前缀的原则的情况，优化器依然能组使用组合索引。解决了部分根据组合索引中的非最左字段的单独的查询导致索引失效的问题，这样就能更加高效的利用组合索引了。

SELECT a,b FROM t1 WHERE b>40
因为SELECT查询的字段全部都是索引的组成部分。MySQL通过索引全扫描获取所有的行记录，然后通过b > 40这个条件过滤，最终筛选出结果集返回给客户端。

众所周知，索引范围扫描的效率肯定是要高于索引全扫描的，在这个示例中，虽然查询条件是b> 40，属于范围查询，但是WHERE条件中不包含a字段的的条件，所以无法使用索引范围扫描的方式过滤数据。在MySQL-8.0.13版本增加的跳跃范围扫描特性，就是针对类似的场景的优化，跳跃范围扫描在这个示例中实际是针对每一个a字段的值，进行了范围扫描，即进行了多次范围扫描。

针对这个示例，具体的跳跃范围扫描过程如下：

1 获取联合索引中第一个字段a的第一个值：a = 1
2 将获取到的值和WHERE条件中的b的条件组合：a = 1 AND b > 40
3 执行这个范围扫描查询
4 获取联合索引中第一个字段a的第二个值：a= 2
5 将获取到的值和WHERE条件中的b的条件组合：a = 2 AND b > 40
6 执行这个范围扫描查询将两次范围扫描查询的结果合并返回给客户端

跳跃范围扫描实际就是将一些全扫描的场景拆分成多个范围扫描，利用范围扫描的效率高于全扫描的效率，最终实现提高SQL效率。

对于使用了跳跃范围扫描特性的SQL，使用EXPLAIN查看其执行计划，可以看到：
在执行计划输出的Extra一栏中有：Using index for skip scan在执行计划输出的possible_keys一栏中会显示可以使用到的索引

使用限制以及场景
下面来说说跳跃范围扫描使用一些限制以及场景：
1 表上至少存在一个联合索引([A_1,A_2…A_k],B_1,B_2…B_m,C,[,D_1,…,D_n])，其中A部

2 分以及D部分可以为空，但是B和C部分不能为空。A_1,A_2…等代表字段值

3 只针对单表查询

4 查询中不包含GROUP BY或者DISTINCT

5 SELECT查询的字段全部被包含在索引组成部分，即符合覆盖索引规范前缀

6 A_1,A_2…A_k部分必须是可以被相等的常量

7字段C上必须是一个范围条件，大于或大于等于，小于或小于等于

8 允许在D字段上有过滤条件，但是必须和C上的范围条件一起使用

总结
跳跃范围扫描是对使用MySQL联合索引查询的SQL意义重大，能在使SQL查询效率更高，但是并不是使用到跳跃范围扫描就能代表SQL执行效率更高。在MySQL一些开发规范中，一般要求建立联合索引时将重复值少的字段放在联合索引前面，将重复值多的字段放在联合索引后面，方便SQL在使用联合索引时通过前面的字段快速过滤结果。但是在跳跃范围扫描特性中，是遍历前面字段的值，与后续字段的范围查询条件组合，进行范围扫描查询，那对于重复值少的字段会被拆分成多个范围扫描查询，如果数据量巨大那么可能会形成巨大数量的范围查询次数，故在实际使用过程中并不一定会比索引全扫描效率更高。
所以个人觉得跳跃范围扫描适用于联合索引中前导列distinct值较少，后续字段选择过滤性又比较好的场景，能更好的发挥跳跃范围扫描的作用。

Mysq排序的过程及调优

参考文献
https://juejin.cn/post/6957281846593847309#heading-3
https://juejin.cn/post/6957296963968565284#heading-11

背景
作为一个交友平台，我们还是以它的核心功能，即搜索用户来开启今天的分享。
假设我们要搜索年龄在18到24之间的女生，同时要求按年龄排序，如果平台注册用户达到千万级，那么，我们一般会对这个搜索结果分页，避免结果页加载很慢，所以，为了实现这个功能，基于用户表，我们会写这样一条SQL：

SELECT * FROM user WHERE age >= 18 AND age <= 24 AND sex = 0 ORDER BY age LIMIT 0, 50

对索引实践有较多经验的同学应该已经想到了，如果我要在用户规模达到千万级时，还要保证这条SQL的查询效率，我们肯定会加一个组合索引index_age_sex(age,sex)，保证查询大规模用户时，性能杠杠滴！

index_age_sex索引树的叶子节点包含排序字段age，保证了age自身已排序。

所以，MySQL只需要2步就可以查找到满足条件的有序结果：

遍历index_age_sex索引树中的叶子节点，找到满足条件的记录主键id
通过上面的主键id到聚簇索引的叶子节点查找对应的记录
如果排序字段是索引字段那么就会在二级索引树叶子节点有序，减少了不必要的排序过程，所以，大大提升了SQL查询的效率。

如果此时，通过上面的用户搜索，我找到了喜欢的女生，然后关注了她，彼此通过平台的聊天功能聊得也很好。但是，之后有一段时间工作忙，没有及时再跟对方有更多的沟通，忙完之后，你想再找她聊天，由于你只是模糊记得她的账号中的一部分，同时，记得她的昵称前半部分字母比较小，于是，你试图通过在自己关注列表中搜索昵称关键字来快速查找她，此时的查询SQL变成：

SELECT * FROM user WHERE user_name LIKE “%am%” AND age >= 18 AND age <= 24 AND sex = 0 ORDER BY age, user_name LIMIT 0, 50

假设现在我们的用户表user中已经添加了索引index_un_age_sex(user_name,age,sex)，表示给字段user_name、age和sex添加了一个联合索引index_un_age_sex，但，我们发现上面这条SQL，由于查询条件中user_name为字符串两端模糊匹配，所以，无法通过索引index_un_age_sex查找用户，即无法命中索引index_un_age_sex，这在大规模用户的场景下，势必影响查询性能。那么，此时，我们有什么办法解决这个问题呢？

我们先用explain语句来分析上面这条SQL，我们看到explain结果中出现了Using index condition; Using where; Using filesort，像下面这样：
图片: https://uploader.shimo.im/f/Sj0InhsordNsXR2x.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

Filesort
Filesort表示MySQL使用了临时文件对where条件过滤的中间结果进行排序，Mysql中把这种在内存中或磁盘上进行排序的方式统称为临时文件排序。临时文件排序非常慢，但如果order子句用到了索引列，就有可能省去文件排序的步骤（按主键索引和唯一索引一定可以省去文件排序）

我们就以上面使用Filesort的SQL为例，看一下
具体的Filesort排序过程：

命中索引index_age_sex(字段age和sex的联合索引)，在索引树index_age_sex中查找age >= 18 AND age <= 24 AND sex = 0的用户记录，详细查找过程，可以顺序阅读《为什么MySQL能够支撑千万数据规模的快速查询？》和《InnoDB是顺序查找B-Tree叶子节点的吗？》两篇文章。

顺序遍历上一步中的查找结果，查找满足user_name LIKE "%am%”的记录。

顺序遍历上一步中的查找结果并排序，这里MySQL使用了快速排序，MySQL给每个线程分配一块内存用于排序，这块内存区域叫做sort_buffer。关于快速排序，很多同学在大学里已经学过了，我就不详细讲解这个过程了，只说一下两种情况：

(1) 当SELECT中的字段 + 排序字段的值长度小于等于参数max_length_for_sort_data，在sort_buffer中写入全字段，然后，对排序字段排序。
假如本文中SQL的SELECT中的字段 + 排序字段的值大小小于等于参数max_length_for_sort_data，即表全部字段大小总和小于等于参数max_length_for_sort_data，MySQL将user表中满足查询条件的记录的所有字段写入sort_buffer，然后，依次对字段age和username排序，最终得到排序后的完整结果。

(2) 当SELECT中的字段 + 排序字段的值大小大于参数max_length_for_sort_data，在sort_buffer中写入排序字段+主键ID，然后，对排序字段排序，最后，根据主键ID到聚簇索引取出对应记录。（还需要回查一次）
假如本文中SQL的SELECT中的字段 + 排序字段的值大小大于参数max_length_for_sort_data，即表全部字段大小总和大于参数max_length_for_sort_data，MySQL将user表中满足查询条件的记录age、username和id写入sort_buffer，然后，依次对字段age和username排序，排序后，根据主键id到聚簇索引获取对应记录。

对比上面两种排序的过程，我们发现采用方案2进行排序，会多一次回表(聚簇索引查找)的过程，如果聚簇索引在磁盘上，那么就会产生磁盘IO，影响性能。

所以，我们可以采用下面两个手段避免回表查询：

SQL中的SELECT部分中的字段尽量不要用*，而是指定字段，确保SELECT中的字段 + 排序字段的值大小小于等于参数max_length_for_sort_data，这样MySQL就会采用上面的(1)方案排序
如果一定要使用*，那么，务必保证表中字段的总长度不超过max_length_for_sort_data，这样MySQL也会采用上面的(1)方案排序

那么，是不是只要保证SELECT中的字段 + 排序字段的值大小小于等于参数max_length_for_sort_data，排序性能一定是最好的呢？
其实还有排序字段的大小有关

假如本章《覆盖索引》中的排序字段username，我们设计它的长度为32字节和200字节，同时保证了SELECT中的字段 + 排序字段的值大小小于等于参数max_length_for_sort_data，那么，两种字段长度的设计对排序性能有什么不同的影响呢？
这时，我就不得不提一下这个排序比较的过程，通过这个过程的讲解，我来揭开上面这个问题的答案！

排序字段的大小与排序性能的关系

MySQL对排序字段进行排序对比时使用了C函数库的memcmp，因为memcmap充分利用了64位CPU的特性，所以，性能非常高！为什么呢？

这里我就以64位CPU为例，看一下memcmp的比较过程，memcmp函数转化为汇编指令后，主要包含了下面这些过程：

通过MOV指令，从内存中读取用于比较的两个入参地址，并将地址分别写入两个rax寄存器
通过NOP指令，对上面的rax寄存器中的地址做内存对齐
通过CMP指令，对没有对齐的部分，单字节(byte)比较
通过CMP指令，针对对齐的部分，以32个字节为单位，通过冗余指令，做4次8字节(qword)比较，为什么以32字节单位，拆分4次比较两个入参地址？下面我会讲到。
通过CMP指令，针对步骤4中不足32个字节的部分，以8个字节为单位，做8字节(qword)比较
通过CMP指令，针对步骤5中最后剩余不足8个字节的部分，做单字节(byte)比较

我先以上面的第一步的MOV指令为例，看下指令在CPU中的处理过程。

下图是Intel的Nehalem处理器的内核架构，我们从上到下看一下MOV指令的处理过程：图片: https://uploader.shimo.im/f/aImRZgbMp6LANAnQ.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

指令提取单元(IFU)从ITLB读取指令MOV在CPU L1 Cache中的位置
指令提取单元(IFU)从分支预测单元(BPU)读取if…then中分支then中的起始指令，由于MOV指令操作不涉及if条件，所以，该读取结果为空
指令提取单元(IFU)根据步骤1得到的位置到CPU L1 Cache中的Instruction Cache中找到指令MOV，并提取MOV
指令提取单元(IFU)将MOV指令传递给解码器(ILD)
解码器(ILD)对指令MOV进行预解码，校验指令长度等，如果超过指定长度，会做其他处理，ps：这个将来我会在其他文章中详细讲解。
解码器(ILD)将MOV指令传递给指令队列(Instruction Queue)进行缓冲，ps：当指令非常多时，指令队列可以收集一批指令后，在一个时钟周期批量将这批指令下传，一批4条指令
指令队列将MOV指令传递给指令解码器(Instruction Decoders)进行解码，指令解码器包含4个解码器：1个复杂解码器(Complex Deocder)和3个简单解码器(Simple Decoder)，前者用于解析复杂的一条指令，将其解析为1 ~ 4条微指令(不包含1)，后者将一条简单指令解析为一条微指令，微指令一般缩写为uop。上面memcmp函数中的MOV指令含义是从内存中读取用于比较的两个入参地址，并将地址分别写入两个rax寄存器，属于复杂指令，所以，这条MOV指令被解析为两条微指令uops：从内存中读取入参地址uop1和将地址写入rax寄存器uop2

指令解析器将分解的两个uops传递给指令解码队列(IDQ)，进行指令去重

(1) 指令解码队列(IDQ)依次将两个uops传递给循环检测器(LSD)，循环检测器检查uop是否存在类似while这样的循环语句，如果存在，对循环中重复的uop去重。由于uop1和uop2均不存在循环，所以，循环检测器直接返回uop1和uop2给指令解码队列(IDQ)
(2) 微指令序列号生成器给uop1和uop2生成两个序列号，将序列号传递给指令解码队列，分配给uop1和uop2
指令解码队列将uop1和uop2传递给MicroOps Fusion，做微指令聚合。对于有些指令相同的，在这里就聚合为一条微指令 + 指令个数。uop1和uop2不相同，所以，不做聚合。

至此，CPU完成了指令MOV的执行前工作，这个过程一般称作Front End。接着，Fusion将uop1和uop2传递给分配器Allocator，进行微指令执行单元分配

(1) Dispatcher分别将微指令uop1和uop2写入重排序缓冲区(ROB)，等待指令执行结果。

(2) Dispatcher同时将微指令写入中继器(RS)，对于uop1和uop2，这个写入是有区别的：

a. uop1是一个内存读取操作，所以，写入重排序缓冲区的uop1是完整微指令：uop1 ADDR1，ADDR1为读取的内存地址。又因为uop1无依赖前置数据，所以，Dispatcher将uop1完整指令同时写入中继器(RS)，待执行。
b. uop2是一个写寄存器操作，写入源数据当前不存在，所以，Dispatcher不会将uop2的完整指令写入中继器(RS)
中继器分析哪些微指令有依赖关系，哪些没有依赖关系，有依赖关系的串行执行，无依赖的并行执行。由于，当前中继器中只包含uop1，所以，只给uop1分配执行单元，即通过port2端口，将uop1完整指令传递给AGU Load执行单元，执行uop1，即该执行单元从内存排序缓冲区(MOB)中读取地址为ADDR1，如果不存在，再从CPU L1 Data Cache中读取，L1 Data Cache中没有，继续从L2 Cache读取，L2 Cache没有，就从L3 Data Cache中读取，CPU三级缓存中都没有，那只能通过地址总线从内存中读取ADDR1
当AGU Load执行单元成功读取到ADDR1后，发送完成状态COMPLETE和ADDR1到重排序缓冲区(ROB)
重排序缓冲区将uop1执行结果(状态)和ADDR1写入回退寄存器文件(RRF)
重排序缓冲区移除微指令uop1
此时，重排序缓冲区中有了ADDR1和步骤10写入的uop2，于是，重排序缓冲区将uop2和ADDR1传递给Dispatcher，Dispatcher从寄存器别名表中命名一个rax寄存器，构造完整的uop2指令，即uop2 rax, ADDR1，表示将ADDR1写入rax寄存器，然后，将完整指令写入中继器(RS)，准备执行uop2。
中继器通过port 3端口分配AGU Store Address执行单元执行uop2，将ADDR1写入rax寄存器
执行单元执行成功后，将结果状态COMPLETE写入重排序缓冲区
重排序缓冲区将uop2执行结果(uop2,rax)写入回退寄存器文件(RRF)，记录下rax寄存器中的值ADDR1
重排序缓冲区移除微指令uop2

通过上面的步骤，你应该了解一条指令在CPU中的处理过程，那么，回到上面的一个问题：为什么memcmp函数，要以32字节单位，拆分4次比较两个入参地址呢？

从上图可以发现，右侧L2 Data Cache和底部L1 Data Cache连接在一起，用来传输数据，而这个传输的带宽为256bit，即一次最多可以传输32个字节的数据，所以，将入参地址以32字节为单位执行uop1微指令，可以充分利用L2 Data Cache和L1 Data Cache之间的带宽。
结合上面的步骤11，由于CPU每个时钟周期可以同时从中继器(RS)中挑选可并发执行的4条微指令并发执行，所以，将相同的比较指令CMP拆分4次，同时对比较的入参地址的4个部分并发比较，最后将比较结果汇总。这样，原来串行执行4次的比较任务变成的并行的一次执行，性能将大大提升。

结合上面memcmp函数中MOV指令在CPU中的处理过程，我们知道如果用于比较的排序字段长度超过32字节，而此时该字段值不在CPU L1 Cache中，那么，CPU不得不分多次将字段值写入L1 Cache，影响了性能，所以，建议排序字段的大小不要超过32字节。

如果排序字段值的大小不超过sort_buffer_size，同时，SQL中包含limit，MySQL会使用优先级队列对字段进行排序，避免了无效记录的排序，提升了排序的效率

优先级队列排序（堆排序）
SELECT * FROM user WHERE user_name LIKE “%am%” AND age >= 18 AND age <= 24 AND sex = 0 ORDER BY age, user_name LIMIT 0, 50

这条SQL使用了快速排序对age,username排序，有没有更好的办法，提升排序的性能？

你可能已经发现，这条SQL其实只需要取前50个排好序的用户，但是，上面的执行过程确对表中的1000条记录（所有满足查询条件的记录）都进行了排序，如果我只对50记录进行排序，并保证这50条记录就是查询出的前50条记录呢，从排序算法来看，是不是代价就小很多了呢？

那么，我们怎么做到只对50记录进行排序，同时，这50条记录又刚好是查询出来的前50条呢？

学过排序算法的同学可能已经猜到了，堆排序！是的，MySQL5.6开始引入了一个新的排序算法，叫做优先级队列排序，该队列使用的就是堆排序，保证只对有限数量n条的记录排序，同时，排序后的结果就是前n条记录。

如果查询出来的所有排序字段值的大小不超过sort_buffer_size，同时，SQL中包含limit，MySQL会使用优先级队列对字段进行排序，避免了无效记录的排序，提升了排序的效率。

归并排序
如果sort Buffer中无法放下所有的排序内容，那么则将分批次将排好序的内容放入临时文件，然后将多个临时文件进行排序。这样会有IO消耗，故建议放大sort Buffer的大小

Mysql排序涉及到的算法
图片: https://uploader.shimo.im/f/irG1nSBcpo2mjBIO.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

排序优化小结

通过本章内容的讲解，我们知道了一些排序优化的方法：

将排序字段加入索引，并保证有序性，避免文件临时排序

SQL中SELECT字段 + 排序字段的值长度小于等于参数max_length_for_sort_data，可以避免回表查询，提升性能

排序字段大小尽量不要超过32字节，充分利用64位CPU的特性，提升排序性能

4 如果查询出来的所有排序字段值的大小不超过sort_buffer_size，同时，SQL中包含limit，MySQL会使用优先级队列对字段进行排序，避免了无效记录的排序，提升了排序的效率。

5 如果sort Buffer中无法放下所有的排序内容，那么则将分批次将排好序的内容放入临时文件，然后将多个临时文件进行排序。这样会有IO消耗，故建议放大sort Buffer的大小

Mysql分组（groupBy）的过程及调优
参考文献：
https://juejin.cn/post/6957696820621344775#heading-3
背景
当我们交友平台在线上运行一段时间后，为了给平台用户在搜索好友时，在搜索结果中推荐并置顶他感兴趣的好友，这时候，我们会对用户的行为做数据分析，根据分析结果给他推荐其感兴趣的好友。

这里，我采用最简单的SQL分析法：对用户过去查看好友的性别和年龄进行统计，按照年龄进行分组得到统计结果。依据该结果，给用户推荐计数最高的某个性别及年龄的好友。

那么，假设我们现在有一张用户浏览好友记录的明细表t_user_view，该表的表结构如下：

CREATE TABLE t_user_view (
id bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT ‘自增id’,
user_id bigint(20) DEFAULT NULL COMMENT ‘用户id’,
viewed_user_id bigint(20) DEFAULT NULL COMMENT ‘被查看用户id’,
viewed_user_sex tinyint(1) DEFAULT NULL COMMENT ‘被查看用户性别’,
viewed_user_age int(5) DEFAULT NULL COMMENT ‘被查看用户年龄’,
create_time datetime(3) DEFAULT CURRENT_TIMESTAMP(3),
update_time datetime(3) DEFAULT CURRENT_TIMESTAMP(3) ON UPDATE CURRENT_TIMESTAMP(3),
PRIMARY KEY (id),
UNIQUE KEY idx_user_viewed_user (user_id,viewed_user_id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
复制代码

为了方便使用SQL统计，见上面的表结构，我冗余了被查看用户的性别和年龄字段。

我们再来看看这张表里的记录：

图片: https://uploader.shimo.im/f/G61Uv1fxK64Lcyc9.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

现在结合上面的表结构和表记录，我以user_id=1的用户为例，分组统计该用户查看的年龄在18 ~ 22之间的女性用户的数量：

SELECT viewed_user_age as age, count(*) as num FROM t_user_view WHERE user_id = 1 AND viewed_user_age BETWEEN 18 AND 22 AND viewed_user_sex = 1 GROUP BY viewed_user_age

得到统计结果如下：

图片: https://uploader.shimo.im/f/7LptgB7xGmDKQiNP.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

可见：

该用户查看年龄为18的女性用户数为2
该用户查看年龄为19的女性用户数为1
该用户查看年龄为20的女性用户数为3

所以，user_id=1的用户对年龄为20的女性用户更感兴趣，可以更多推荐20岁的女性用户给他。

如果此时，t_user_view这张表的记录数达到千万规模，想必这条SQL的查询效率会直线下降，为什么呢？有什么办法优化呢？

想要知道原因，不得不先看一下这条SQL执行的过程是怎样的？

Explain分析

我们先用explain看一下这条SQL：

EXPLAIN SELECT viewed_user_age as age, count(*) as num FROM t_user_view WHERE user_id = 1 AND viewed_user_age BETWEEN 18 AND 22 AND viewed_user_sex = 1 GROUP BY viewed_user_age
复制代码

执行完上面的explain语句，我们得到如下结果：

图片: https://uploader.shimo.im/f/o2SoXRIMxTOBIYju.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

在Extra这一列中出现了三个Using，这3个Using代表了《导读》中的groupBy语句分别经历了3个执行阶段：

Using where：通过搜索可能的idx_user_viewed_user索引树定位到满足部分条件的viewed_user_id，然后，回表继续查找满足其他条件的记录
Using temporary：使用临时表暂存待groupBy分组及统计字段信息
Using filesort：使用sort_buffer对分组字段进行排序

这3个阶段中出现了一个名词：临时表。这个名词我在《MySQL分表时机：100w？300w？500w？都对也都不对！》一文中有讲到，这是MySQL连接线程可以独立访问和处理的内存区域，那么，这个临时表长什么样呢？

下面我就先讲讲这张MySQL的临时表，然后，结合上面提到的3个阶段，详细讲解《导读》中SQL的执行过程。

临时表

我们还是先看看《导读》中的这条包含groupBy语句的SQL，其中包含一个分组字段viewed_user_age和一个统计字段count(*)，这两个字段是这条SQL中统计所需的部分，如果我们要做这样一个统计和分组，并把结果固化下来，肯定是需要一个内存或磁盘区域落下第一次统计的结果，然后，以这个结果做下一次的统计，因此，像这种存储中间结果，并以此结果做进一步处理的区域，MySQL叫它临时表。

（临时表对分组字段的值的数量进行了统计）

刚刚提到既可以将中间结果落在内存，也可以将这个结果落在磁盘，因此，在MySQL中就出现了两种临时表：内存临时表和磁盘临时表。

内存临时表
什么是内存临时表？在早期数据量不是很大的时候，以存储分组及统计字段为例，那么，基本上内存就可以完全存放下分组及统计字段对应的所有值，这个存放大小由tmp_table_size参数决定（可以适当的调整变大）。这时候，这个存放值的内存区域，MySQL就叫它内存临时表。
此时，或许你已经觉得MySQL将中间结果存放在内存临时表，性能已经有了保障，但是，在《MySQL分表时机：100w？300w？500w？都对也都不对！》中，我提到过内存频繁的存取会产生碎片，为此，MySQL设计了一套新的内存分配和释放机制，可以减少甚至避免临时表内存碎片，提升内存临时表的利用率。

此时，你可能会想，在《为什么我调大了sort_buffer_size，并发量一大，查询排序慢成狗？》一文中，我讲了用户态的内存分配器：ptmalloc和tcmalloc，无论是哪个分配器，它的作用就是避免用户进程频繁向Linux内核申请内存空间，造成CPU在用户态和内核态之间频繁切换，从而影响内存存取的效率。用它们就可以解决内存利用率的问题，为什么MySQL还要自己搞一套？

或许MySQL的作者觉得无论哪个内存分配器，它的实现都过于复杂，这些复杂性会影响MySQL对于内存处理的性能，因此，MySQL自身又实现了一套内存分配机制：MEM_ROOT。它的内存处理机制相对比较简单，内存临时表的分配就是采用这样一种方式。

下面，我就以《导读》中的SQL为例，详细讲解一下分组统计是如何使用MEM_ROOT内存分配和释放机制的？

MEM_ROOT（过于深度，目前不是重点）

我们先看看MEM_ROOT的结构，MEM_ROOT设计比较简单，主要包含这几部分，如下图：

图片: https://uploader.shimo.im/f/6SZ6BIZwwGOsvgNc.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

free：一个单向链表，链表中每一个单元叫block，block中存放的是空闲的内存区，每个block包含3个元素：

left：block中剩余的内存大小
size：block对应内存的大小
next：指向下一个block的指针

如上图，free所在的行就是一个free链表，链表中每个箭头相连的部分就是block，block中有left和 size，每个block之间的箭头就是next指针

used：一个单向链表，链表中每一个单元叫block，block中存放已使用的内存区，同样，每个block包含上面3 个元素

min_malloc：控制一个 block 剩余空间还有多少的时候从free链表移除，加入到used链表中

block_size：block对应内存的大小

block_num：MEM_ROOT 管理的block数量

first_block_usage：free链表中第一个block不满足申请空间大小的次数

pre_alloc：当释放整个MEM_ROOT的时候可以通过参数控制，选择保留pre_alloc指向的block

下面我就以《导读》中的分组统计SQL为例，看一下MEM_ROOT是如何分配内存的？

分配

图片: https://uploader.shimo.im/f/uToGeWvIHROd528b.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

初始化MEM_ROOT，见上图：

min_malloc = 32block_num = 4first_block_usage = 0pre_alloc = 0block_size = 1000err_handler = 0free = 0used = 0

申请内存，见上图：
由于初始化MEM_ROOT时，free = 0，说明free链表不存在，故向Linux内核申请4个大小为1000/4=250的block，构造一个free链表，如上图，链表中包含4个block ，结合前面free链表结构的说明，每个block中size为250，left也为250

分配内存，见上图：

(1) 遍历free链表，从free链表头部取出第一个block，如上图向下的箭头

(2) 从取出的block中划分220大小的内存区，如上图向右的箭头上面-220，block中的left从250变成30

(3) 将划分的220大小的内存区分配给SQL中的groupby字段viewed_user_age和统计字段count(*)，用于后面的统计分组数据收集到该内存区
(4) 由于第(2)步中，分配后的block中的left变成30，30 < 32，即小于第(1)步中初始化的min_malloc，所以，结合上面min_malloc的含义的讲解，该block将插入used链表尾部，如上图底部，由于used链表在第(1)步初始化时为0，所以，该block插入used链表的尾部，即插入头部

释放

下面还是以《导读》中的分组统计为例，我们再来看一下MEM_ROOT是如何释放内存的？

图片: https://uploader.shimo.im/f/1eh6UKK0heIHHkMA.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

如上图，MEM_ROOT释放内存的过程如下：

遍历used链表中，找到需要释放的block，如上图，block(30,250)为之前已分配给分组统计用的block
将block(30,250)中的left + 220，即30 + 220 = 250，释放该block已使用的220大小的内存区，得到释放后的block(250,250)
将block(250,250)插入free链表尾部，如上图曲线箭头部分
通过MEM_ROOT内存分配和释放的讲解，我们发现MEM_ROOT的内存管理方式是在每个Block上连续分配，内部碎片基本在每个Block的尾部，由min_malloc成员变量控制，但是min_malloc的值是在代码中写死的，有点不够灵活。所以，对一个block来说，当left小于min_malloc，从其申请的内存越大，那么block中的left值越小，那么，该block的内存利用率越高，碎片越少，反之，碎片越多。这个写死是MySQL的内存分配的一个缺陷。

磁盘临时表

当分组及统计字段对应的所有值大小超过tmp_table_size决定的值，那么，MySQL将使用磁盘来存储这些值。这个存放值的磁盘区域，MySQL叫它磁盘临时表。
我们都知道磁盘存取的性能一定比内存存取的性能差很多，因为会产生磁盘IO，所以，一旦分组及统计字段的数据不得不写入磁盘，那性能相对是很差的，所以，我们尽量调大参数tmp_table_size，使得组及统计字段可以在内存临时表中处理。

执行过程（重点）
无论是使用内存临时表，还是磁盘临时表，临时表对组及统计字段的处理的方式与过程都是一样的。《导读》中我提到想要优化《导读》中的那条SQL，就需要知道SQL执行的原理，所以，下面我就结合上面讲解的临时表的概念，详细讲讲这条SQL的执行过程，见下图：
图片: https://uploader.shimo.im/f/6wZcitINRE2Tvsz1.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

1 创建临时表temporary，表里有两个字段viewed_user_age和count()，主键是viewed_user_age，如上图，倒数第二个框temporary表示临时表，框中包含两个字段viewed_user_age和count()，框内就是这两个字段对应的值，其中viewed_user_age就是这张临时表的主键

2 扫描表辅助索引树idx_user_viewed_user，依次取出叶子节点上所有满足条件的id值，即从索引树叶子节点中取到表的主键id。如上图中的idx_user_viewed_user框就是索引树，框右侧的箭头表示取到表的主键id

3 根据主键id到聚簇索引cluster_index的叶子节点中查找记录，即扫描cluster_index叶子节点（回查）：

4 依次遍历上面步骤3取出的所有记录，然后取出viewed_user_age字段值放入临时表
(1) 得到一条记录，然后取到记录中的viewed_user_age字段值。如上图，cluster_index框，框中最右边的一列就是viewed_user_age字段的值

  (2) 如果临时表（temporary）中没有主键为viewed_user_age的行，就插入一条记录 (viewed_user_age, 1)。如上图的temporary框，其左侧箭头表示将cluster_index框中的viewed_user_age字段值写入temporary临时表(3) 如果临时表中有主键为viewed_user_age的行，就将viewed_user_age这一行的count(*)值（统计值）加 1。如上图的temporary框

5（重复上面的三个步骤，直到取出辅助索引树叶子结点中所有满足条件的id值，并把对应数据放入临时表后），再根据字段viewed_user_age在sort_buffer中做排序，得到结果集返回给客户端。如上图中的最右边的箭头，表示将temporary框中的viewed_user_age和count(*)的值写入sort_buffer，然后，在sort_buffer中按viewed_user_age字段进行排序

我们发现该过程主要经历了4个部分：
1 创建临时表
2 从二级索引树中去获取满足条件的ID值
3 去聚簇索引树叶子结点中回查完整的数据，并把需要的viewed_user_age字段值放入到临时表中
4 在sort_buffer中按viewed_user_age字段进行排序

idx_user_viewed_user、cluster_index、temporary和sort_buffer，对比上面explain的结果，其中前2个就对应结果中的Using where，temporary对应的是Using temporary，sort_buffer对应的是Using filesort。

优化方案（重点）
此时，我们有什么办法优化这条SQL呢？
既然这条SQL执行需要经历4个部分，那么，我们可不可以去掉最后两部分呢，即去掉Using Using temporary和sort_buffer（Using filesort）？

原SQL
SELECT viewed_user_age as age, count(*) as num FROM t_user_view WHERE user_id = 1 AND viewed_user_age BETWEEN 18 AND 22 AND viewed_user_sex = 1 GROUP BY viewed_user_age

答案是可以的，我们只要给SQL中的表t_user_view添加如下索引：

ALTER TABLE t_user_view ADD INDEX idx_user_age_sex (user_id, viewed_user_age, viewed_user_sex);
这样就符合最左匹配原则，可以使用索引，新增索引，避免临时表对分组字段值的进行统计，及sort_buffer对分组和统计字段排序。

索引是一个b+树，根据二级索引树叶子节点的特点（按索引值升序排序）然后可以就可以在树的叶节点对其排好序无需到sort_buffer中进行排序，此外count统计是可以在查找索引树的时候完成的（查找索引树叶子节点满足条件的元素就记录下来+1）
（比如说，先搜索age是20的，每在树叶子节点搜一个符合条件的记录就+1）这样就无需使用到索引表和sort buffer，性能大幅提高。

当然，如果实在无法避免使用临时表，那么，尽量调大tmp_table_size（临时表的最大大小），避免使用磁盘临时表统计分组字段。

Mysql join查询的过程及调优

参考文献：
https://juejin.cn/post/6962943587625467918#heading-5

如何判断连表查询时的驱动表
一般情况下使用外连接时，会非常大的影响查询优化器，对驱动表的选择，如果能用inner join的地方，尽量少用left join，因为外连接会很大程度上的干扰查询优化器对成本的评估，Mysql自己对成本的评估绝对是效果比我们干扰后的要好。

外连接时
left join（左外连接）：
在不指定查询条件或者查询条件是双方都有或者查询条件是左表独有的情况下，谁在左谁是驱动表。

例子1 这里有两个表t1，t2进行连表查询，不指定连接条件。
explain select * from t1 left join t2 on t1.a=t2.a;
那么这时 t1是驱动表，t2是被驱动表

例子2 这里有两个表t1，t2进行连表查询，指定连接条件,且连接条件字段是双方都有的。
explain select * from t1 left join t2 on t1.a=t2.a where t2.a=1;
那么这时 t1是驱动表，t2是被驱动表

例子3 这里有两个表t1，t2进行连表查询，指定连接条件,且连接条件字段不是双方都有的，而是左表拥有的。(注意)
explain select * from t1 left join t2 on t1.a=t2.a where t1.b=“haha”;
那么这时 t1是驱动表，t2是被驱动表

例子4 这里有两个表t1，t2进行连表查询，指定连接条件,且连接条件字段不是双方都有的，而是右表拥有的。(注意这里不再是左表是驱动表了)

explain select * from t1 left join t2 on t1.a=t2.a where t2.c=“ccc”;
那么这时 t2是驱动表，t1是被驱动表

right join（右外连接）：

在不指定查询条件或者查询条件是双方都有的情况下，谁在右谁是驱动表
同左外连接的例子一样

内连接时（inner join）
如果两张表使用inner join关联，mysql会自动选择两张表中的小表，去驱动大表

总结
要特别注意的是在用left join关联查询时，左边要用小表，右边可以用大表。如果能用inner join的地方，尽量少用left join，因为外连接会很大程度上的干扰查询优化器对成本的评估。Mysql自己对成本的评估绝对是效果比我们干扰后的要好。

背景

一个用户交友平台，随着用户量的快速增长，会有一些用户提出这样的需求：想知道自己的主页有多少用户访问，男生有多少，女生有多少？进而针对性地在平台上展示自己的特点。这是一个简单的数据统计展示，通常我们可以使用MySQL的联表查询得到相应的结果。

已知我们现在数据库中有两张表：用户主表user和t_user_view用户访客表，这两张表的表结构如下：

user表

CREATE TABLE user (
id int(11) NOT NULL,
user_id int(8) DEFAULT NULL COMMENT ‘用户id’,
user_name varchar(29) DEFAULT NULL COMMENT ‘用户名’,
user_introduction varchar(498) DEFAULT NULL COMMENT ‘用户介绍’,
sex tinyint(1) DEFAULT NULL COMMENT ‘性别’,
age int(3) DEFAULT NULL COMMENT ‘年龄’,
birthday date DEFAULT NULL COMMENT ‘生日’,
PRIMARY KEY (id),
UNIQUE KEY index_user_id (user_id),
KEY index_un_age_sex (user_name,age,sex),
KEY index_age_sex (age,sex)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
复制代码

t_user_view表

CREATE TABLE t_user_view (
id bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT ‘自增id’,
user_id bigint(20) DEFAULT NULL COMMENT ‘用户id’,
viewed_user_id bigint(20) DEFAULT NULL COMMENT ‘被查看用户id’,
create_time datetime(3) DEFAULT CURRENT_TIMESTAMP(3),
update_time datetime(3) DEFAULT CURRENT_TIMESTAMP(3) ON UPDATE CURRENT_TIMESTAMP(3),
PRIMARY KEY (id),
KEY index_viewed_user_user (viewed_user_id,user_id)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8;
复制代码

其中，user表的数据如下：
图片: https://uploader.shimo.im/f/85785xu1DOx8sAT5.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
t_user_view表的数9据如下：
图片: https://uploader.shimo.im/f/KJdPrSkxp5RaOcYX.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
已知我的用户id为10008，那么，结合上面的表结构和数据，我们就可以通过下面这条SQL得到访问我的女性用户(sex = 0)和男性(sex = 1)用户数：

SELECT u.sex, COUNT(*) FROM user u LEFT JOIN t_user_view tuv ON u.user_id = tuv.user_id WHERE tuv.viewed_user_id = 10008 GROUP BY u.sex
复制代码

执行SQL后，得到访问我的用户性别分布如下：

在上面这条SQL中，我们使用了left join，这时，你可能担心，当我们的user表的数据规模达到千万级时，这样的联表查询是否会很慢，如果很慢，我们有什么办法去优化它呢？

为了回答这个问题，我们就以上面这条SQL为例，先来详细看看MySQL处理left join的过程。

Explain分析

我们先通过explain命令初步看一下这条SQL的执行过程：

EXPLAIN SELECT u.sex, COUNT(*) FROM user u LEFT JOIN t_user_view tuv ON u.user_id = tuv.user_id WHERE tuv.viewed_user_id = 10008 GROUP BY u.sex
复制代码

得到结果如下：

图片: https://uploader.shimo.im/f/uae1t3CqnrxpphmT.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

通过上图，我们发现这条SQL中的驱动表是t_user_view(图中的tuv)，被驱动表是user(图中的u)，其中，t_user_view表使用了索引index_viewed_user_user，user表使用了索引index_user_id，因此，MySQL会使用Index Nested-Loop Join方式执行该SQL。什么是Index Nested-Loop Join？

Index Nested-Loop Join

Index Nested-Loop Join，指的就是MySQL在联表查询时，对关联表使用了索引查询。

那么，以上面这条SQL为例，结合我在《为什么MySQL能够支撑千万数据规模的快速查询？》中讲解的索引查找过程，我们看下Index Nested-Loop Join执行过程：

根据tuv.viewed_user_id = 10008这个条件，查找t_user_view表的索引树index_viewed_user_user，得到满足条件的第一个叶子节点记录<10008, 10001, 1>
提取记录<10008, 10001, 1>中的10001，组装条件u.user_id = 10001
根据条件u.user_id = 10001，查找user表索引树index_user_id，得到满足条件的记录<10001, 1>
根据记录<10001, 1>中的主键1，查找user表聚簇索引(回表)，得到主键id =1 的记录<1, 10001, …, 1998-01-02>
从第1步得到的记录<10008, 10001, 1>开始顺序扫描其后继记录，重复2 ~ 4步，最终得到4条记录<4, 10003, Bruce, …, 2006-03-03, 10008, 10003, 2>、<2, 10002, Nancy, …, 2008-02-03, 10008, 10002, 3>、…、<5, 10005, Amy, …, 2008-02-06, 10008, 10005, 5>，加上第4步得到的一条记录，至此，我们就得到了所有满足SQL查询条件的5条记录

6 依次遍历上面得到的5条记录，取出记录中的sex字段值，将该字段值依次写入内存临时表

  (1) 遍历第一条记录<1, 10001, ..., 1998-01-02>，取出记录中的sex字段值(2) 如果临时表中没有sex 字段值，用sex字段值初始化临时表记录<1, 1>，里面包含两个元素，其中前面的1代表性别，后面的1代表该性别出现的次数(3) 否则，相应的sex字段值所在临时表记录的第二个元素+1(4) 重复步骤(1)~(3)

7 最后，得到内存临时表的记录分别为<1, 2>和<0, 3>
8 对临时表中的两条记录按sex字段排序，得到最终的结果为<0, 3>和<1, 2>

其中，步骤7 ~ 9，我在《告诉面试官，我能优化groupBy，而且知道得很深！》一文中详细讲解过，其实就是groupBy的执行过程。

但有时候，我们并不能保证表联接语句都可以命中索引，所以，这时候，MySQL不得不采用新的方式执行表联接语句：Block Nested-Loop Join。那么，什么又是Block Nested-Loop Join？

Block Nested-Loop Join

Block Nested-Loop Join，指的是使用一个内存块（join buffer）做表联接查询。我还是以上面这条SQL为例：

SELECT u.sex, COUNT(*) FROM user u LEFT JOIN t_user_view tuv ON u.user_id = tuv.user_id WHERE tuv.viewed_user_id = 10008 GROUP BY u.sex
复制代码

现在，我把user表的索引index_user_id删掉，来说明一下Block Nested-Loop Join的执行过程。

我们先explain一下，得到如下结果：

图片: https://uploader.shimo.im/f/nApE9Q0dPLlyvMxs.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

可以看到user表的extra中显示Using join buffer(Block Nested Loop)，说明这条联表SQL使用了Block Nested-Loop Join方式执行。详细过程如下：

根据tuv.viewed_user_id = 10008这个条件，查找t_user_view表的索引树index_viewed_user_user，得到满足条件的第一个叶子节点记录<10008, 10001, 1>
提取记录<10008, 10001, 1>中的10001，组装条件u.user_id = 10001

3 根据条件u.user_id = 10001，扫描user表（聚簇索引的所有叶子节点），把满足条件的记录写入join buffer：
(1) 发现第一条记录<1, 10001, Jack, …, 1998-01-02>满足条件，将记录<1, 10001, Jack, …, 1998-01-02>写入join buffer，直到找出所有满足条件u.user_id = 10001的记录，并将它们写入join buffer

4 从第1步得到的记录<10008, 10001, 1>开始顺序扫描其后继记录，重复2 ~ 3步，最终，join buffer中写入5条记录：<1, 10001, Jack, …, 1998-01-02>、…、<5, 10005, Amy, …, 2008-02-06>

依次遍历join buffer中的5条记录，取出记录中的sex字段值，将该字段值依次写入内存临时表

(1) 遍历第一条记录<1, 10001, …, 1998-01-02>，取出记录中的sex字段值

(2) 如果临时表中没有sex 字段值，用sex字段值初始化临时表记录<1, 1>，里面包含两个元素，其中前面的1代表性别，后面的1代表该性别出现的次数

(3) 否则，相应的sex字段值所在临时表记录的第二个元素+1
(4) 重复步骤(1)~(3)

6 最后，得到内存临时表的记录分别为<1, 2>和<0, 3>
7 对临时表中的两条记录按sex字段排序，得到最终的结果为<0, 3>和<1, 2>

讲完Block Nested-Loop Join算法后，我突然在想，上面的过程中，我把user表中满足查询条件的记录全部放进了一个join buffer，那如果一个join buffer放不下这些记录，会发什么情况呢？
如果一个join buffer放不下这些记录，会发什么情况呢？

还是以上面的SQL为例，我们来看一下语句执行的过程：

根据tuv.viewed_user_id = 10008这个条件，查找t_user_view表的索引树index_viewed_user_user，得到满足条件的第一个叶子节点记录<10008, 10001, 1>

提取记录<10008, 10001, 1>中的10001，组装条件u.user_id = 10001

3 根据条件u.user_id = 10001，扫描user表（聚簇索引所有叶子节点），依次遍历表中所有记录，把满足条件的记录写入join buffer：
(1) 发现第一条记录<1, 10001, Jack, …, 1998-01-02>满足条件，将记录<1, 10001, Jack, …, 1998-01-02>写入join buffer，直到找出所有满足条件u.user_id = 10001的记录，并将它们写入join buffer

4 从第1步得到的记录<10008, 10001, 1>开始顺序扫描其后继记录，重复2 ~ 3步，在写入第3条记录<2, 10002, Nancy, …, 2008-02-03>后，join buffer满了，此时，MySQL终止后续记录的扫描，进入步骤5

5 依次遍历join buffer中的3条记录，取出记录中的sex字段值，将该字段值依次写入内存临时表

(1) 遍历第一条记录<1, 10001, …, 1998-01-02>，取出记录中的sex字段值

(2) 如果临时表中没有sex 字段值，用sex 字段值初始化临时表记录<1, 1>，里面包含两个元素，其中前面的1代表性别，后面的1代表该性别出现的次数(3) 否则，相应的sex字段值所在临时表记录的第二个元素+1(4) 重复步骤(1)~(3)

6 最后，得到内存临时表的记录分别为<1, 2>和<0, 1>

7 清空join buffer

8 从记录索引树index_viewed_user_user叶子节点记录<10008, 10002, 3>开始顺序扫描其后继记录，重复步骤4 ~ 6，最终，得到内存临时表中的记录为<1, 2>和<0, 3>

9 对临时表中的两条记录按sex字段排序，得到最终的结果为<0, 3>和<1, 2>

通过使用一次join buffer和使用两次join buffer的执行过程来看，后者会两次全表扫描user表，前者只会扫描一次，所以，多次扫表的性能更差，我们应该尽量保证join buffer足够大，可以容纳被驱动表的记录，减少扫表的次数。在MySQL中可以通过参数join_buffer_size调整！

参数调整
我们可以在MySQL的配置文件my.cnf中设置join_buffer_size的大小：

join_buffer_size = 2M

很多同学看到这里，可能没有更多优化的办法了。现在我们来看一个场景：
假设我们的系统内存总共4G，join_buffer我们配置了2G，此时，我们的联表语句已经写满了2G的join_buffer，而此刻整个内存也写满了，有优先级更高的进程需要分配内存（比如，系统级的进程），这时，为了给优先级更高的进程分配内存，Linux会交换join_buffer的内存到硬盘上，产生IO操作，这势必影响联表查询的性能。（就要牺牲join_buffer中的内存）

那我们该怎么解决这个问题呢？

缺页异常

还记得我在《MySQL分表时机：100w？300w？500w？都对也都不对！》一文中讲到了Linux系统缺页异常的处理机制吗？我们一起回顾一下这个过程：
图片: https://uploader.shimo.im/f/inuY2gJWCsVnqaFH.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
处理器生成一个虚拟地址，并把它传送给 MMU
MMU 根据虚拟地址生成 VPN(虚拟页号，因为CPU与内存交互以页为单位)，然后请求内存，获取 PTE 的数据。
内存向 MMU 返回 PTE 的数据
由于判断出 PTE 的有效位是 0，即内存中没有虚拟页号对应的物理页，所以 CPU 将出发一次异常中断，将控制权转移给内核中的缺页异常处理程序。
缺页异常处理程序确定出物理内存中的牺牲页，如果这个页面被修改过了（D 标志位为 1），那么将牺牲页换出到磁盘。
缺页处理程序从磁盘中调入新的页面到内存中，并且更新 PTE
缺页处理程序将控制权返回给原来的进程，再次执行导致缺页的指令。再次执行后，就会产生页命中时的情况了。

在上面的过程中，我们重点关注一下5和6两步，在第5步中我讲到将牺牲页换出到磁盘，这里的换出，在Linux内核中就叫做swap out，在第6步中我讲到从磁盘中调入新的页面到内存中，这里的调入，在Linux内核中就叫做swap in。

因此，结合上面的缺页异常处理过程，我们发现，上面联表查询产生的IO操作其实就是swap out。所以，在这种情况下，我们有必要想办法减少Linux系统进行swap，那么，该如何减少呢？我们就从swap的原理出发，找一找减少的办法。

Linux内核swap的对象是什么？是内存。也就是上面的图中的memory，即物理内存。所以，我们先来看看物理内存在Linux系统中长什么样？

Linux内核将物理内存从逻辑上划分为一个一个page，每个page叫做page frame(页框)。这个页框又被分为两类：page cache和anonymous page(匿名页)。

所以，要看物理内存在Linux系统中的样子，其实就是看看这两种内存。

Page Cache（页框）

我们先来看看Page Cache。
图片: https://uploader.shimo.im/f/hqePivCR38ji8RNn.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
page cache：如上图，它是一个tree结构，tree中的每个节点就是一个页框，比如，P1、P2分别表示Page Cache中的两个页框，它们通过mmap方式创建。

分配条件：我在《MySQL分表时机：100w？300w？500w？都对也都不对！》中提到过：申请内存大小大于MMAP_THRESHOLD这个内核参数配置的大小(默认128K)时，Linux使用mmap分配内存。

特点：内存不足时系统立刻回收。

匿名页anonymous page

我们再来看看匿名页。
图片: https://uploader.shimo.im/f/mxeiDIsguXG66ttD.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
匿名页：如上图中的A和B两个页框，它们是离散在物理内存中的，通过brk()方式创建。

分配条件：我在《MySQL分表时机：100w？300w？500w？都对也都不对！》中提到过：申请内存大小小于MMAP_THRESHOLD这个内核参数配置的大小(默认128K)时，Linux使用brk分配内存。

特点：内存不足时，系统先标记待回收，待下次访问时，回收页框。

知道了Linux系统将物理内存分为Page Cache和匿名页，那么，我们开始进入正题：Page Cache和匿名页，两者swap的机制到底是什么样的呢？了解了这个机制，我们就能找到减少swap的办法！

Swap

Page Cache（页框的）的Swap Out

以MySQL查询使用了join_buffer为例，我们结合上面的缺页异常中的第5步，先来看下Page Cache页swap out的机制。见下图，我们关注红线：

图片: https://uploader.shimo.im/f/SiTZjIuHzbamD6Uj.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

根据MySQL进程对应的task_struct中mm属性，找到进程使用的内存结构mm_struct
假设MySQL进程的join_buffer使用了物理内存页P1，那么，图中的page指的就是P1。缺页异常处理程序根据P1对应的page中的mapping找到address_space
根据address_space中的i_mmap属性，找到vm_area_struct优先级红黑树的根节点vm_area_struct。ps：在Page Cache中vm_area_struct结构组成一个优先级红黑树。
缺页异常处理程序根据第1步得到的mm_struct，到vm_area_struct优先级红黑树寻找vm_mm等于前面mm_struct的vm_area_struct节点，如上图，找到左边的那个vm_area_struct节点
缺页异常处理程序取到第2步中page中的index属性，即得到P1的物理地址index。如上图，page->index为P1对应page中的index
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_file，得到P1对应的映射文件File
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_pgoff，通过page->index - vm_pgoff，得到P1在映射文件File中对应的虚拟地址偏移量
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_start，通过vm_start + 第6步得到的偏移量，得到P1在内存中的虚拟地址
缺页异常处理程序根据第1步中的mm_struct中的pgd，即页全局目录，通过P1的虚拟地址到pgd找对应的pte，即页表项，更新页表项的标记为1，表示需要将该页swap out到磁盘
缺页异常处理程序根据第7步得到的P1虚拟地址偏移量，和第6步得到的映射文件，将P1换出到磁盘的映射文件中

Page Cache（页框的）的Swap In

同样，以MySQL查询使用了join_buffer为例，结合上面的缺页异常中的第6步，我们再来看下Page Cache页swap in的过程，见下图绿线部分：

图片: https://uploader.shimo.im/f/MyVNltxfZPVWR16O.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

根据MySQL进程对应的task_struct中mm属性，找到进程使用的内存结构mm_struct
假设MySQL进程的join_buffer使用了物理内存页P1，那么，图中的page指的就是P1。缺页异常处理程序根据P1对应的page中的mapping找到address_space
根据address_space中的i_mmap属性，找到vm_area_struct优先级红黑树的根节点vm_area_struct。ps：在Page Cache中vm_area_struct结构组成一个优先级红黑树。
缺页异常处理程序根据第1步得到的mm_struct，到vm_area_struct优先级红黑树寻找vm_mm等于前面mm_struct的vm_area_struct节点，如上图，找到左边的那个vm_area_struct节点
缺页异常处理程序取到第2步中page中的index属性，即得到P1的物理地址index。如上图，page->index为P1对应page中的index
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_file，得到P1对应的映射文件File
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_pgoff，通过page->index - vm_pgoff，得到P1在映射文件File中对应的虚拟地址偏移量
缺页异常处理程序根据第4步得到的vm_area_struct中的vm_start，通过vm_start + 第6步得到的偏移量，得到P1在内存中的虚拟地址
缺页异常处理程序根据第1步中的mm_struct中的pgd，即页全局目录，通过P1的虚拟地址到pgd找对应的pte，即页表项，更新页表项的标记为0
缺页异常处理程序根据第7步得到的P1虚拟地址偏移量，和第6步得到的映射文件，将P1从磁盘的映射文件换入到内存中

匿名页

讲完Page Cache页的swap机制，我们再来看下匿名页的swap。

匿名页的Swap out

同样，以MySQL查询使用了join_buffer为例，结合上面的缺页异常中的第5步，我们先来看下匿名页的swap out的过程，见下图红线部分：

图片: https://uploader.shimo.im/f/xgYkig2K2I6Cyf0H.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

假设MySQL进程的join_buffer使用了物理内存页P1，那么，图中的page指的就是P1。缺页异常处理程序根据P1对应的page中的mapping找到anno_vma。ps：其中一个进程使用page中的mapping对应一个anno_vma。
根据上一步找到的anno_vma中的rb_root，找到对应anno_vma_chain
根据上一步找到的anno_vma_chain中的vma，找到相应的vm_area_struct
缺页异常处理程序取到1步中page中的index属性，即得到P1的在内存中的物理地址index。如上图，page->index为P1对应page中的index
缺页异常处理程序根据第3步得到的vm_area_struct中的vm_file，得到P1对应的映射文件File
缺页异常处理程序根据第3步得到的vm_area_struct中的vm_pgoff，通过page->index - vm_pgoff，得到P1在映射文件File中对应的虚拟地址偏移量
缺页异常处理程序根据第3步得到的vm_area_struct中的vm_start，通过vm_start + 第6步得到的偏移量，得到P1在内存中的虚拟地址
根据MySQL进程对应的task_struct中mm属性，找到进程使用的内存结构mm_struct
根据mm_struct中的pgd，即页全局目录，通过P1的虚拟地址到pgd找对应的pte，即页表项，更新页表项的标记为1，表示需要将该页swap out到磁盘

至此，匿名页的swap out机制完成了90%。什么？！为啥只完成90%，还有10%是什么？？？

别着急，在上面匿名页的介绍中，我提到：匿名页的特点是内存不足时，不会立即回收，待下次访问该页时再触发回收。所以，剩下的10%就是触发回收的过程，这部分我在后续的文章中详细分解，同时，这个回收过程和匿名页的swap in还息息相关，敬请期待！

JOIN查询总结参数优化

关于join_buffer的swap机制，讲了呢么多，最终，还是为了优化Join查询的性能。下面我们就看看优化的办法！

在Linux内核中有个参数swappiness，这个参数用来控制内核优先回收(swap out)的页框类型，数字越小，优先回收Page Cache中的页框，反之，优先回收(swap out)匿名区的页框。

因此，针对频繁使用join_buffer和sort_buffer的场景，建议优化方案：

1 考虑通过brk()分配的内存，在内存不足时不会立即回收，方便后续进程可以直接利用未回收的内存，减少IO，提升性能。所以，参考上面匿名页的介绍：申请内存大小小于MMAP_THRESHOLD这个内核参数配置的大小(默认128K)，Linux使用brk分配内存。建议调大MMAP_THRESHOLD参数，保证联表查询可以更多地使用匿名页去申请分配内存。

2 设置swappiness=0，减少回收匿名页的频率。ps：swappiness=0不是不回收匿名页，只是在内存中只有匿名页占满内存时，触发回收匿名页，只要内存中有page cache页，优先回收page cache页。

3 通过使用一次join buffer和使用两次join buffer的执行过程来看，后者会两次全表扫描user表，前者只会扫描一次，所以，多次扫表的性能更差，我们应该尽量保证join buffer足够大，可以容纳被驱动表的记录，减少扫表的次数。在MySQL中可以通过参数join_buffer_size调整！

4 小表驱动大表。
尽量让小表做驱动表，可以更好的提高执行效率
否则大表做驱动表是遍历多次的（要多次从驱动表中去一行数据，然后去被驱动表中取所有匹配的数据，这样明显增加了遍历次数效率不高，如大表中有1W条数据，而小表只有50条记录，假设小表每条记录对应200条大表数据，那么需要按大表去驱动时，要遍历1W次大表，而这1W次，大部分都没有小表数据去匹配，故这样效率会低很多。而对于小表作为驱动表来遍历只要50次，每次都有200条大表数据去对应，效率大大提高）

Mysql DDL都过程（加索引的过程）以及调优
参考文献
https://juejin.cn/post/6958330669617381412#heading-2

背景

以社交平台的用户表为例，随着业务的快速增长，用户表user单表数据量越来越大，此时，如果我们想给user表添加索引，数据规模对添加过程的影响势必要考虑在内，但是，单表数据规模对添加索引会产生什么样的影响呢，我们在什么样的数据库请求状态下给大表添加索引比较好呢？

DDL语句（加索引）的问题
单表数据规模对添加索引会产生什么样的业务影响？

在什么样的数据库请求状态下给大表添加索引比较好？

我们先来看下第一个问题，当我们回答了第一个问题，那么，第二个问题的答案也就浮出水面了。

Row Log

我们先来看一个结构，它叫Row Log，用于在DDL过程中记录DML操作的日志文件。（DDL与DML是可以并发执行的）（MySQL将DML日志写到Row Log只是为了在执行DDL期间，可以并行执行DML）

图片: https://uploader.shimo.im/f/3Fv9KYP4jRz7oFPF.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

我以user表为例，讲解一下Row Log。

它有如下特点：

每个索引对应一个Row Log，如上图为user表的索引index_age_birth对应的Row Log。

Row Log在逻辑上由多个Block组成，每个Block可以存储多个DML操作、一个DML操作可以落在多个Block中。如上图中的Log代表DML操作：

最前面两个Log存在第二个Block中
第3个Log和第4个Log的前半部分存在第三个Block中
第4个Log的后半部分和第5个Log存在最后一个Block中

在物理存储上Row Log分为两部分：

内存日志：内存中会存放一个总大小等于inndob_sort_buffer_size的Block，用于写入DML操作

文件日志（Row Log）：当内存中的Block写满，也就是大小大于innodb_sort_buffer_size，且小于innodb_online_alter_log_max_size时，写满的Block会刷到磁盘上，空出内存中的Block给后续的Log写入，日志文件中，所有Block总大小如果超过innodb_online_alter_log_max_size，写入就会报错。（故我们可以调大innodb_sort_buffer_size 从而减少磁盘IO提高性能）

Row Log的核心结构如下：

Log：表示DML操作日志，它的结构为操作flag + 事务id + 操作记录，其中，操作flag包含两种：INSERT和DELETE，UPDATE看作是先DELETE，再INSERT。比如，上图第一个Log中包含一条记录<0x61 + 1234 + <25, 1998-01-02, 1>>，其中，0x61代表这是一个插入操作，1234表示这个操作的事务id，<25, 1998-01-02, 1>表示操作的记录。

head：这是用于将Block中的Log回放到索引树时，用来扫描Block中Log的指针，扫完一个Log，head指针向后移到下一个Log。如上图，因为从Block的头部开始扫描，head指针在回放前处在Block的第一个Log的位置。

tail：这是用于将DML操作写入一个Block时，用来定位Block中Log插入位置的指针，插入完一个Log，tail指针向后移动到新插入的Log。如上图，因为从Block的头部开始插入Log，所以，tail指针在插入前处在Block的第一个Log的位置。

blocks：无论是head还是tail指针，都包含一个blocks字段，表示Row Log日志文件中包含的Block数量

Row Log追加

下面我们再来看下Log是如何追加到Row Log的？我以user表的index_age_birth索引的Row Log为例来说明：

图片: https://uploader.shimo.im/f/o8QKqiWrgZr2fDza.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

见上图，从上到下，我们来看下这个追加的过程：

如果内存中没有Block，创建一个innodb_sort_buffer_size大小的Block，tail指针指向Block中的第一个Log，如果有Block，tail指针指向Block中最后一个Log。如上图，内存中有Block，tail指向Block中最后一个Log，也就是虚线框前面那个Log

2 根据即将插入的DML操作日志大小，得到Block中下一个Log相对最后一个Log的偏移量。如上图中的offset，这里分两种情况：

(1) 如果DML操作日志大小 >= innodb_sort_buffer_size - 当前Block中已有Log的总大小，则偏移量为innodb_sort_buffer_size - 当前Block中已有Log的总大小
(2) 如果DML操作日志大小 < innodb_sort_buffer_size - 当前Block中已有Log的总大小，则偏移量为DML操作日志大小

3 根据tail指针和偏移量，将插入的DML操作日志拷贝到内存的Block。这里同样分两种情况：

(1) 全拷贝

如果DML操作日志大小 < innodb_sort_buffer_size - 当前Block中已有Log的总大小，将DML操作日志全部拷贝到Block中末尾Log。如上图，全拷贝最右侧，将DML日志<0x61 + 3355 + <25, 1998-01-02, 1>>完整拷贝到末尾Log，然后，将tail移到被拷贝的Log上

(2) 半拷贝(需要拷贝到Row log文件中去)

如果DML操作日志大小 >= innodb_sort_buffer_size - 当前Block中已有Log的总大小，拷贝DML操作日志的前面部分到tail后面偏移量大小的空间。如上图半拷贝里的上半部分，将DML日志<0x61 + 3355 + <25, 1998-01-02, 1>>的前半部分拷贝到末尾Log，然后，将tail移到被拷贝的Log上
将内存中整个Block写入Row Log日志文件。如上图，半拷贝里上半部分大括号包含了整个Block，同时将该Block通过箭头，写入row_log_file
重新将tail移到内存空Block的头部，将DML操作的后半部分拷贝到tail后面偏移量大小的空间。如上图半拷贝里的下半部分，将DML日志<0x61 + 3355 + <25, 1998-01-02, 1>>的后半部分拷贝到Block的头部
如上图，tail.blocks + 1，代表Row Log日志文件中新增了一个Block。

Row Log回放

MySQL将DML日志写到Row Log只是为了在执行DDL期间，可以并行执行DML，最后，这些DML日志还是要更新(回放)到索引树上的，所以，同样以索引index_age_birth为例，我们再来看下Row Log中的日志是如何更新到索引树的？

图片: https://uploader.shimo.im/f/y7cAlnnsVrx9W4YJ.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

从上到下，我们来看上面这张图：

1 MySQL先扫描磁盘上的Row Log文件，遍历文件中的Block，如上图，文件扫描部分为一个Block的遍历：

(1) head指针指向Block的头部Log，从该Log开始，将头部Log写入索引树。如上图，文件扫描中的最上面部分，将DML日志0x61 + 3355 + <25, 1998-01-02, 1>>中的记录写入索引树index_age_birth的第一个叶子节点。

 (2) 头部Log清空，将head指针移到后面一个Log。如上图，文件扫描中的第二块长方框。(3) 重复(1)和(2)两步，直到head指针移到Block中最后一个Log，然后，将该Log中的记录写入索引树index_age_birth。如上图，文件扫描中的第三个长方框及方框中最后一个Log中的记录写入索引树index_age_birth的第二个叶子节点。

2 重复步骤1，将Row Log文件中所有Block内的Log全部写入索引树index_age_birth，至此，Row Log文件清空。如上图，文件扫描中最后一个虚线长方框，表示Row Log文件清空。

3 由于DML日志写Row Log和DDL同时进行，结合《Row Log追加》中的过程，我们会发现大部分Block写入了Row Log文件，但是，还会存在小部分DML日志留存在内存的Block中，所以，MySQL需要将这部分留存的Log再写入索引树中，具体过程如下：

(1) 对数据字典加排它锁，禁止新的DML操作，ps：如果不加锁，会导致内存中Block不断更新，无法判断DML操作何时结束。(2) 执行步骤1，将内存Block中的Log全部写入索引树index_age_birth，如上图，内存扫描部分。

Bulk Load

在讲解添加索引的过程之前，还有一个概念再讲解一下，这就是Bulk Load，在添加索引的过程中，会将已排序的记录批量插入索引树的叶子节点中，这个批量插入的过程就叫做Bulk Load，我以索引index_age_birth为例，讲解一下这个过程，见下图：

图片: https://uploader.shimo.im/f/rkppYmppJm5hCz4K.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

从已排序的记录集中分多批写入内存的bulk中。如上图，MySQL将最左边已排序的记录集拆分成两批写入2个bulk中，上面的bulk包含15, 2008-02-03, 2和15, 2008-02-06, 5两条记录，下面的bulk包含16, 2007-06-06, 6、17, 2006-03-03, 4和18, 2002-06-07, 3 三条记录。

以bulk为单位，将bulk中的记录集一次插入索引树中。如上图，上面的bulk记录集插入到索引树index_age_birth的第三个叶子节点，下面的bulk记录集插入到索引树index_age_birth的倒数第二个叶子节点。

添加索引（DDL）

Row Log的追加和回放，以及Bulk Load是添加索引过程中的核心步骤，讲完这三个步骤，下面我再来看一下InnoDB引擎中MySQL添加索引的过程就比较容易理解了，该过程主要分三个阶段，我以user表为例详细讲解一下：

Prepare阶段：

根据旧表user的表结构文件frm，创建一个副本表结构frm文件，将新索引添加到副本中
获得MDL排他锁，禁止读写数据字典及旧user表，关于MDL锁，我会在《MySQL锁全解析》详细讲解
根据alter类型，确定执行方式，一共两种执行方式：COPY、INPLACE
更新内存中的数据字典，标记user表所有索引online_status为ONLINE_INDEX_CREATION，表示该表索引都处在在线DDL状态。关于数据字典的结构，我在《什么？！我们竟然可以自己决定MySQL的查询计划！！！》中有讲解过。
根据旧表user的ibd文件，创建副本ibd文件

DDL执行阶段：

降级MDL锁为共享锁，允许读写数据字典及旧user表

2 扫描旧表user的聚集索引中叶子节点每一条记录

 (1) 申请一个sort_buffer，大小为innodb_sort_buffer_size/索引叶子节点中最小的记录的大小(2) 将每一条记录写入sort_buffer(3) sort_buffer写满后对里面的记录进行升序排序(4) sort_buffer写满了，如果临时文件不存在，就创建一个临时文件(5) 遍历sort_buffer记录，将sort_buffer中的记录写入文件中

a. 生成一个block，将记录添加到block
(6) 将block写入临时文件

3 遍历旧表聚簇索引的记录完成后，临时文件中就包含多个block，每个block包含已排序的记录
4 使用归并排序对临时文件中的block内记录进行排序和合并（故block越少越好）

5 遍历副本frm中的聚集索引和辅助索引

 (1) 搜索索引树，定位到树种最右边的叶子节点(2) 判断该节点是否可以有足够空间批量插入记录，如果没有就创建一个新的叶子节点，执行步骤(3)，否则，执行步骤(4)(3) 将新节点接到索引树的右下角，执行步骤(4)(4) 遍历临时文件中的记录，将记录通过bulk load方式写入叶子节点(5) 调整插入记录的叶子节点内记录的slot信息，关于slot，我在《InnoDB是顺序查找B-Tree叶子节点的吗？》中详细讲解过。

6 在这个阶段，与此同时，user表的所有DML操作日志写入Row Log，即《Row Log追加》中讲解的过程
7 重放该阶段产生的user表的Row Log日志到索引中，直到Row Log中的最后一个block，即《Row Log回放》中讲解的过程。

Commit阶段：

升级MDL锁为排它锁，禁止读写数据字典及旧user表
将Row Log中最后一个block，即内存中Block对应的DML日志插入索引树，过程参见DDL执行阶段中的步骤(7)
更新内存中的数据字典，关于数据字典的结构，我在《什么？！我们竟然可以自己决定MySQL的查询计划！！！》中有讲解过。
将DDL执行操作记录redo日志
rename副本ibd文件和frm文件为旧表名，即原user表的frm和ibd文件名

DDL操作（如加索引）影响业务DML操作的问题以及解决方案：

问题

循环遍历旧表聚簇索引叶子节点的所有记录，如果表记录非常多，非常消耗CPU，如果DDL长时间占用CPU资源，势必会影响MySQL的连接数，导致MySQL处理DML操作的并发请求数下

2 归并排序使用的磁盘临时文件做记录排序，如果文件中的已排序记录集非常多，那么，归并排序过程中产生大量的磁盘IO，在MySQL处理查询时，如果内存中没有查询的结果，此时，buffer pool又满了，触发刷脏行为，这时就会出现查询请求等待刷脏结束，查询响应变慢。

可能这时候你会问，Prepare阶段和Commit阶段都加了排它锁，为什么这两个环节不影响DML操作呢？因为虽然这两个阶段都加了排它锁，但是，加锁后的操作都是小数据规模的操作，所以，加锁时间很短，对DML的影响不大，所以，可以忽略不计。

解决方案
那么，我们看看上面两个问题怎么解决呢？

针对第一个问题，
由于表中的原有记录的数量是由业务发展决定的，业务发展快，记录数就会多，这点我们无法控制，所以，针对表数据量大导致扫描聚簇索引变慢，我们只能规避DDL带来的风险，规避方法如下：

评估表中的数据量
观察MySQL的CPU使用率

结合上面两个因素，如果数据量不大，那么，只要在非极端高峰期执行DDL，对DML的影响是不大的。如果数据量很大，建议找到MySQL的CPU使用率比较低的情况下做DDL，保证不影响DML操作.。

针对第二个问题，

我们可以通过调整参数innodb_sort_buffer_size，将其调大，使归并排序来源的临时文件中已排序的block数量尽可能少，减少大量block的合并，从而降低磁盘IO

DDL操作在主从模式下的问题

平时我们用的最多的MySQL架构就是主从模式，所以，我们来看一下在这种模式下，在线DDL的过程是怎么样的呢？

图片: https://uploader.shimo.im/f/4Ry0FUh8runeVygk.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

结合《添加索引》中的过程，我们知道DDL和DML并行阶段，DDL一边执行，DML一边写入Row Log。如上图，左边在master中，DDL和INSERT，以及UPDATE并行执行，DDL在执行的同时，INSERT和UPDATE并行写入Row Log
DDL和DML并行过程中，将DDL操作和并行的DML按序写入binlog。如上图，左边master将DDL和INSERT、UPDATE操作按序写入binlog，DDL第一、其次是INSERT，最后是UPDATE
DDL执行结束，将master的binlog同步到slave上。如上图，将左边master的binlog中的三条操作同步到slave上
在slave上依次回放DDL和DML。如上图，右边在slave中依次执行DDL、INSERT和UPDATE

通过上面这个过程，你应该已经想到，在DDL和DML并行的阶段，如果产生大量的DML操作，那么，在slave端回放这些DML操作会耗费大量的时间，会影响从库读的数据一致性。所以，这就是主从模式下，在线DDL的问题和风险。

DDL的优化方案

通过本章的讲解，我想你应该对MySQL的在线DDL的机制有了清晰的认识，同时，通过在线DDL机制的讲解，我们也发现了一些优化的方法：

数据量大的情况下，建议不做DDL，或者在低峰和CPU占用率比较低的情况下去执行

https://juejin.cn/post/6958330669617381412#heading-2

Mysql的非主键唯一索引与普通索引的比较

准备工作
假设我有如下表：
CREATE TABLE user (
id int(11) unsigned NOT NULL AUTO_INCREMENT,
username varchar(255) COLLATE utf8mb4_unicode_ci DEFAULT NULL,
address varchar(255) COLLATE utf8mb4_unicode_ci DEFAULT NULL,
age int(4) DEFAULT NULL,
PRIMARY KEY (id),
UNIQUE KEY username (username),
KEY address (address)
) ENGINE=InnoDB AUTO_INCREMENT=100001 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;
这表中有 10 万条模拟数据，
看表结构，有一个 username 索引，这个索引是一个唯一性索引；还有一个 address 索引，这是一个普通索引。
查询
2.1 普通索引查询
我们先来看看普通索引的查询。
我们来做一个简单的查询：
select * from user where address=‘1’;
它的执行步骤：

先利用二分查找定位满足条件的记录在哪个叶子结点中，之后从定位到的叶节点内第一条记录开始，向右顺序线性遍历该节点内所有记录即可定位到满足条件的第一条记录，然后继续遍历该记录后继的记录，直到遍历到某条记录不满足等值条件时，停止扫描

得到满足条件的所有记录后，由于二级索引上这些记录只是满足条件的主键值，还要根据主键值去依次回查一次聚簇索引才能得到需要的完整数据

它的执行计划
图片: https://uploader.shimo.im/f/u9SCRdFxtQcR41ER.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

2.2 非主键唯一性索引查询
我们再来看看唯一性索引查询。
先来看看一个 SQL：
select * from user where username=‘1’;
对于唯一性索引来说，username 这一列的值是唯一的，所以在查询的过程中，找到第一条 username=‘1’ 的记录后，就不需要再找了

它的执行步骤：

先利用二分查找定位满足条件的记录在哪个叶子结点中，之后从定位到的叶节点内第一条记录开始，向右顺序线性遍历该节点内所有记录即可定位到满足条件的第一条记录，之后就直接停止扫描，相比普通索引查询少了部分遍历叶子结点的次数和回查次数。（只用回查1次）

它的执行计划
图片: https://uploader.shimo.im/f/NB0PSElW3NtcCkc8.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs
和前面普通索引的查询计划相比，这里的查询计划 type 为 const，也侧面印证了我们的说法。

2.3 它们的比较 PK
那么从上面的描述中我们可以看出来，似乎唯一性索引在查询的时候表现更优秀？真是情况到底如何，我们再来分析下。
首先，理论上来说，唯一性索引在查询的时候确实更优秀一些，原因很简单：非主键唯一性索引找到满足条件的记录后就不需要再找了，且回查次数肯定只有1次；而普通索引找到满足条件的记录后，还需要继续向后查找，直到遇到不满足条件的记录（address 不为 1 的记录）才停止搜索，且可能要回查多次，这么看来，确实唯一性索引更胜一筹！那么这种差异很明显吗？老实说，这个优势有时候比较大，有时候可以忽略不计！

为什么呢？
对于普通索引而言，虽然找到第一条记录之后，还需要继续找后面的，但是因为满足条件的记录是连续的，索引只需要顺着记录之间的单向链表继续向后读就行了，速度快。

由于 InnoDB 引擎读数据的时候，不是一条一条的读，而是一页一页的读（默认每页 16KB，在什么是 MySQL 的“回表”？一文中，我有大致介绍 16KB 的问题），所以，即使继续向后读，也是内存操作，速度很快。

也不排除个别情况，例如满足条件的记录刚好是在当前页的最后一条，此时就需要加载新的一页数据，但是这种概率比较小，可以忽略之。

综上所述，当使用普通索引，且重复的值比较少时，那么遍历叶子结点数量，与回查次数都不会很大，如某个索引值没有重复时，用普通索引，那么它遍历叶子结点数量与非主键索引一致，且回查次数也是1.此时唯一性索引和普通索引对搜索效率的影响可以忽略不计。

当然当重复的值比较多时，用普通索引那么效率就会下降比较明显了，如使用普通索引，且某个索引值有2W条重复，那么遍历叶子结点数量要比使用非主键唯一索引要多2W-1次，且回表次数也是要多2W-1次此时效率相差的就比较明显了

3 插入/修改（DML操作）
3.1.1 buffer pool
有一个 buffer pool 需要大家了解。
小伙伴们知道，InnoDB 引擎存储数据的时候，是以页为单位的，每个数据页的大小默认是 16KB，我们可以通过如下命令来查看页的大小：
图片: https://uploader.shimo.im/f/NMiSVUfFLyj4rAJZ.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

16384/1024=16
刚好是 16KB。
计算机在存储数据的时候，最小存储单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如 XFS/EXT4）最小单元是块，一个块的大小是 4KB，也就是四个块组成一个 InnoDB 中的页。我们在 MySQL 中针对数据库的增删改查操作，都是操作数据页，说白了，就是操作磁盘。
但是大家想想，如果每一次操作都操作磁盘，那么就会产生海量的磁盘 IO 操作，如果是传统的机械硬盘，还会涉及到很多随机 IO 操作，效率低的令人发指。这严重影响了 MySQL 的性能。
为了解决这一问题，MySQL 引入了 buffer pool，也就是我们常说的缓冲池。
buffer pool 的主要作用就是缓存索引和表数据，以避免每一次操作都要进行磁盘 IO，通过 buffer pool 可以提高数据的访问速度。
通过如下命令可以查看 buffer pool 的默认大小：
图片: https://uploader.shimo.im/f/5NxNSw2QetIQ6Rms.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

134217728/1024/1024=128
默认大小是 128MB，因为松哥这里的 MySQL 是安装在 Docker 中，所以这个分配的小一些。一般来说，如果一个服务器只是运行了一个 MySQL 服务，我们可以设置 buffer pool 的大小为服务器内存大小的 75%～80%。

3.1.2 change buffer

Change Buffer是Buffer Pool中的一部分

如果每次写操作，数据库都直接更新磁盘中的数据，会很占磁盘IO。为了减少磁盘IO，InnoDB在Buffer Pool中开辟了一块内存，用来存储变更记录，为了防止异常宕机丢失缓存，当事务提交时会将变更记录持久化到磁盘（redo log），等待时机更新磁盘的数据文件（刷脏），用来缓存写操作的内存，就是Change Buffer。Change Buffer的主要操作，就是在flush链表

Change Buffer默认占Buffer Pool的25%，最大设置占用50%：
show variables like ‘%innodb_change_buffer_max_size%’

buffer pool 虽然提高了访问速度，但是增删改的效率并没有因此提升，当涉及到增删改的时候，还是需要磁盘 IO，那么效率一样低的令人发指。
为了解决这个问题，MySQL 中引入了 change buffer。change buffer 以前并不叫这个名字，以前叫 insert buffer，即只针对 insert 操作有效，现在改名叫 change buffer 了，不仅仅针对 insert 有效，对 delete 和 update 操作也是有效的，change buffer 主要是对非唯一的索引有效，如果字段是唯一性索引，那么更新的时候要去检查唯一性，依然无法避免磁盘 IO。

change buffer 就是说，当我们需要更改数据库中的数据的时候，我们把更改记录到内存中，等到将来数据被读取的时候，再将内存中的数据 merge 到 buffer pool，此时 buffer pool 中的数据和磁盘中的数据就会有差异，有差异的数据我们称之为脏页，在满足条件的时候（redo log 写满了、内存写满了、其他空闲时候），InnoDB 会把脏页刷新回磁盘。这种方式可以有效降低写操作的磁盘 IO，提升数据库的性能。

通过如下命令我们可以查看 change buffer 的大小以及哪些操作会涉及到 change buffer：
图片: https://uploader.shimo.im/f/zwlGV74yZb3dsToE.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

innodb_change_buffer_max_size：这个配置表示 change buffer 的大小占整个缓冲池的比例，默认值是 25%，最大值是 50%。
innodb_change_buffering：这个操作表示哪些写操作会用到 change buffer，默认的 all 表示所有写操作，我们也可以自己设置为 none/inserts/deletes/changes/purges 等。

3.2 它们的比较PK
看了上面 change buffer 的介绍，大家应该已经明白了：
对于非唯一性索引，插入或者修改时候直接将数据操作到 change buffer 中就行了，这是一个内存操作，很快。

对于唯一性索引，插入者修改的时候，必须要将数据页读入到内存中（这一步涉及到大量的随机 IO，效率低），检查没有冲突，然后插入。
所以，很明显，在插入的时候，非唯一性索引更有优势。

小结
那么对于一个需要全局唯一的字段，到底是用普通索引还是非主键唯一性索引呢？这个我觉得很难给大家一个放之四海而皆准的建议，因为数据库优化很多时候不是绝对的，要结合自己的实际业务来，所以，无论何时何地，先满足业务需求，在此基础上，再去讨论数据库优化。

如果你能从业务上确保该字段唯一，那么可以使用普通索引，这样可以提高插入/更新速度，且也不会损失什么查询性能。

Mysql索引相关面试题
图片: https://uploader.shimo.im/f/xE9xOnq4P7u1aTzx.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyMzk0NDYsImciOiJjVnZHREpXR3RqSnByUkRjIiwiaWF0IjoxNjQ0MjM5MTQ2LCJ1c2VySWQiOjM5MDU5ODgzfQ.7EqdwLtlXEbj70UFYy35Buv_WkBkGN4ma3CuEJehfNs

https://mp.weixin.qq.com/s?__biz=MzkyMTI3Mjc2MQ==&mid=2247485917&idx=1&sn=857948ad5e437a3a8d7487fea2e12449&chksm=c187610bf6f0e81dfd215f708d293b1c44cd61f9db3bb29f44e981294ce67673f35b73953b6c&mpshare=1&scene=1&srcid=0126gS4LU7ZoNQAhbNIN9teu&sharer_sharetime=1643169524650&sharer_shareid=1a9027e763704842dfdf7fbf506b7dd6&version=3.1.20.6008&platform=win#rd

查看全文
如若内容造成侵权/违法违规/事实不符，请联系编程学习网邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！

R语言并行计算RC~bray-curtis~距离
R语言并行计算RCbray-curtis距离群落构建分析是微生物生态学分析的重要组成部分，成为目前文章发表的热点技术。之前我们介绍了计算beta-NTI（beta nearest taxon index）来进行群落构建分析。|beta-NTI| >2说明决定性过程主导，其…...
2024/5/9 5:32:35
Vue.js 笔记 (1)
Vue.js 使用书籍：《Vue.js从入门到实践》作者：孙鑫 Vue 只关注视图层， 采用自底向上增量开发的设计。 MVVM 模式，顾名思义即 Model-View-ViewModel 模式 1. 第一个Vue程序{{ }} <div id"app">{{message}}</di…...
2024/5/9 5:50:53
2022 年不错的 SQL 注入 (SQLi) 检测工具
SQL 注入 (SQLi) 是一种可以访问敏感或私有数据的隐蔽攻击形式，它们最早是在上世纪末被发现的，尽管它们的年龄很大，但它们经常被用作黑客工具包中的一种有效技术。今天，给大家介绍一下顶级 SQLi 检测工具。顶级 SQLi 检测工具有…...
2024/5/9 5:45:15
计算机的总线
总线是链接各个部件的信息传输线，是各个部件共享的传输介质，英文是BUS(任一时刻，只有一对部件或者一对设备使用总线，其他想使用，需要等待释放) 总线的基本概念串行 --------- 通常传输距离远，一次传输…...
2024/5/9 5:47:01
java版商城源码之聚合支付Spring Cloud+Spring Boot+mybatis+security+uniapp+Redis+MQ+VR全景+b2b2c多商家入驻前后端分离
源码地址来源： https://minglisoft.cn/honghu/business.html package com.honghu.cloud.controller;import java.io.BufferedReader; import java.io.ByteArrayInputStream; import java.io.File; import java.io.IOException; import java.io.InputStream; import…...
2024/5/9 3:32:45
信息系统项目管理师2019年下半年下午案例分析题及答案
本系列文章将会对信息系统项目管理师考试中出现的各类案例分析题进行汇总解析，并给出分析过程，帮助考生备考复习。更多复习内容请在微信搜索小程序 “信息系统项目管理师高频考点”。 1、2019年3月某公司中标当地轨道交通的车载广播系统项目&#xff0…...
2024/5/8 18:49:45
JS笔记迭代器与生成器
文章目录五、迭代器与生成器5.1 迭代器1 理解迭代2 迭代器模式3 可迭代协议4 迭代器协议5 自定义迭代器6 提前终止迭代器5.2 生成器1 生成器基础2 通过yield中断执行3 生成器作为默认迭代器4 提前终止生成器5.3 总结五、迭代器与生成器 5.1 迭代器 1 理解迭代循环是迭代机制…...
2024/5/8 19:43:11
云计算技术 — 多云
目录文章目录目录多云多云的优势多云的用例灾难恢复（Disaster recovery）故障转移（Failover）成本优化（Cost optimization）避免供应商锁定（Avoiding vendor lock-in）数据主权（Data sovereignty）特定服务访问（Access to specialized services）低延迟多云的最佳实践部…...
2024/4/20 12:26:45
Hadoop生态圈
参考链接 1.为什么需要分布式计算系统？ 当前大数据的数据量已达PB级别（1PB1024TB），可以说是庞大无比。同时数据还有结构化（如数字、符号等）、非结构化（如文本、图像、声音、视频等&#xff09…...
2024/4/19 17:09:35
Docker 从入门到进阶三：构建自己的镜像并分享给大家用
文章目录什么是镜像？镜像分层与联合文件系统Docker镜像加载原理commit 构建镜像本地镜像发布到阿里云什么是镜像？ 是什么我想大家都知道了，不过我放一段比较专业的话：是一种轻量级、可执行的独立软件包，它包含运行某…...
2024/5/8 17:32:24
将文件夹中的文件按照最后修改时间进行降序排列，并将文件全路径存入List集合
package _06应用; import java.io.File; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.logging.Logger; //import org.apache.log4j.Logger;//java实现遍历文件目录，根据文件最后的…...
2024/5/8 21:02:06
Spring Security使用原理解读
目录1 集成SpringBoot1.1 Spring Boot 介绍1.2 创建maven工程1.3 spring 容器配置1.4 Servlet Context配置1.5 安全配置1.6 测试2 工作原理2.1 结构总览2.2 认证流程2.2.1 认证流程2.2.2.AuthenticationProvider2.2.3.UserDetailsService2.2.4.PasswordEncoder2.3.授权流程2.3.…...
2024/4/13 12:23:16
faiss-2: 快速入门
数据准备 faiss可以处理固定维度d的向量集合，该集合用二维数组表示。一般来说，需要两个数组： data：包含被索引的所有向量元素； query：索引向量，需要根据索引向量的值返回与向量集中的最近邻元…...
2024/4/25 1:10:50
JZ55二叉树的深度C++
链接 https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId13&tqId11191&rp1&ru/ta/coding-interviews&qru/ta/coding-interviews/question-ranking 描述： 示例： 代码： 方法一： class …...
2024/5/6 16:59:13
SDUT ACM OJ 实验二链表
A ：顺序建立链表 #include<stdio.h> #include<stdlib.h>struct node {int data;struct node *next; }*head,*tail,*p,*q;int main () {head(struct node *)malloc(sizeof(struct node));head->nextNULL;tailhead;int n,i;scanf("%d",&…...
2024/5/6 18:11:24
错题小结2
1. 问题：程序出错在什么阶段？ 答案：程序正常运行解析：main函数可以接受两个参数 int main(int argc,char *argv[])，argc arguments count表示参数个数，argv argument vector表示指针数组，同…...
2024/4/13 12:23:11
PAT1017
1017 A除以B (20 分) 本题要求计算 A/B，其中 A 是不超过 1000 位的正整数，B 是 1 位正整数。你需要输出商数 Q 和余数 R，使得 ABQR 成立。输入格式： 输入在一行中依次给出 A 和 B，中间以 1 空格分隔。输出格式&a…...
2024/4/13 12:23:36
YbtOJ-森林之和【dp】
正题题目大意一个节点的权值定义为它度数的平方，求所有nnn个点的有标号森林的所有节点权值和。 1≤n,T≤51031\leq n,T\leq 5\times 10^31≤n,T≤5103 解题思路首先因为所有节点本质相同，所以我们可以只考虑一个节点所有情况下的权值和。然后考虑…...
2024/5/6 18:40:57
浅谈selenium的webdriver（python自动化）
提前约定一些变量 from selenium import webdriver driver webdriver.Chrome() url"xxx" driver.get(url)定位方法通过元素id定位 driver.find_element(By.ID,id)通过元素name定位 driver.find_element(By.NAME,name)通过类名进行定位 driver.find_element(By…...
2024/4/13 12:23:16
MIT6.830 lab1 SimpleDb
MIT6.830 lab1 SimpleDb 整个实验一共有6个lab，通过每一个lab的代码去实现一个简单的数据库，主要有：数据库的组织架构(字段、元组、模式、buffer pool等)、CRUD的实现、查询优化、事务与并发控制、崩溃与故障恢复。 SimpleDB consists of: Cl…...
2024/4/13 12:23:36

Mysql中索引相关问题

相关文章

最新文章