对于SQL语句的执行，在B-TREE索引中定位一条记录是一项重要的能力。InnoDB根据索引组织数据。更新和删除操作需要先在索引中找到特定的记录。插入操作也需要先找出记录要插入到索引中的什么位置。当查询语句的WHERE条件可以命中索引时，还需要找到WHERE条件对应的扫描区间内的第一条记录，然后从这条记录开始沿着该区间内记录之间的单向链表索引页和索引页之间的链接。双向链表顺序读取后续记录。从上面的简要介绍中，在B-TREE索引中定位记录的重要性就显而易见了。本文是MySQL8的第一篇文章，也是查询优化器的开篇。希望本文的介绍能够为大家理解后续文章打下一些基础。本文内容基于MySQL8.0.29源码。正文1.概述更新、删除和查询操作定位索引中的一条记录，插入操作定位要插入的位置。流程基本一样，源码也是用同样的方法实现的。本文基于WHERE条件可以命中索引的前提，介绍查询操作定位WHERE条件扫描区间内的第一条记录。查找记录过程中的二分查找和顺序查找都会涉及到索引页的部分结构。接下来分两小节介绍定位记录过程相关的扫描间隔和索引页的局部结构。2.什么是扫描间隔？扫描间隔即WHERE条件，由字段和关系运算符（>、>=、<、<=、=）组成，用于限定需要扫描的记录范围。一句话描述的太抽象了，我们来展开一下。扫描区间可按不同维度分类：按是否有界可分为有界区间和单边有界区间。按开闭可分为开区间、闭区间和半开半闭区间。特殊区间，单点区间。有界区间开区间，例如：WHEREa>100ANDa<200，则扫描区间为(100,200)。闭区间，例如：WHEREa>=100ANDa<=200，则扫描区间为[100,200]。左开右闭区间，例如：WHEREa>100ANDa<=200，则扫描区间为(100,200)。左闭右开区间，例如：WHEREa>=100ANDa<200，扫描间隔为[100,200)。单边有界区间有下界，左开区间，例如：WHEREa>100，扫描区间为(100,+∞)。存在下界，左闭区间，例如：WHEREa>=100，扫描区间为[100,+∞)。有上界和右开区间，例如：WHEREa<200，则扫描区间为(-∞,200)。有上界，右闭区间，例如：WHEREa<=200，扫描区间为(-∞,200)。单点区间只有一个取值区间，例如：WHEREa=100，扫描间隔为[100,100].3.索引页结构B-TREE索引的根节点、内节点、叶节点都是索引页，索引页的内部结构比较复杂，会有以后是专门介绍整个索引页结构的文章，接下来我们只介绍定位记录所需要的结构：伪记录、记录链表、槽（SLOT，也叫记录分组）。有一个记录链表索引页中每条记录的头部信息中的2字节空间，存放的是下一条记录在当前索引页中的偏移量。偏移量是记录数据的第一个字节的地址（不包括记录头信息），这是通过减去第一个字节的地址得到的索引页数。InnoDB索引页最大可以设置为64K，2个字节可以表示索引页中任意字节的偏移量。这个2字节的空间叫做next_record，索引页中的记录可以通过next_recordString存储在一起，形成一个单向链表。从任意一条记录开始，向后遍历，可以到达当前索引页的最后一条记录。Pseudo-record伪记录是指索引页，不是用户插入的，而是InnoDB偷偷插入的记录。不管索引页中是否有用户插入的记录（用户记录），每个索引页中都会有2条伪记录：infimum，索引页中的第一条记录。当indexpage中有用户记录时，infimum的next_record指向第一条用户记录。当indexpage没有用户记录时，infimum的next_record指向supremum记录。supremum，索引页中的最后一条记录。槽位（SLOT）索引页中的槽位分为3种：infimum槽位只包含一条记录，即infimum伪记录。supremumslot包含1到8条记录，最后一条为supremum伪记录，其余为用户记录。公共插槽包含4到8个用户记录。每个slot占用2个字节，存储slot对应的N条记录中当前索引页中最大记录的偏移量。最大记录是指按索引字段升序排列的槽中的最后一条记录。索引页中的槽存放在索引页的一个特殊区域，称为页目录（PageDirectory）。页目录区中的槽位倒序排列，并排存放。第一个槽位在末尾，第二个槽位在倒数第二个，依此类推，最后一个槽位在第一个。4.定位扫描区间的第一条记录(1)抽象过程描述B+树索引包括根节点、内部节点和叶子节点，在一棵3层B+树中定位扫描区间的第一条记录。大致过程是这样的：从根节点开始，确定记录在哪个内部节点。进入内部节点，确定记录在哪个叶子节点。进入叶子节点，确定记录的位置。随着B+树层次的增加或减少，上述步骤也会相应增加或减少。上述过程中的每一步，内部过程都是一样的，都需要先进行二分查找，再进行顺序查找。最后，如果是根节点和内部节点，则进行下一步；如果是叶子节点，就没有了。二分查找和顺序查找的过程如下：第一步，通过二分查找，确定记录属于哪个槽。每个索引页的头部信息中有一个2字节的区域，存放当前索引页的槽数。该区域的名称是PAGE_N_DIR_SLOTS。读取PAGE_N_DIR_SLOTS的值得到槽数，然后减去1计算出最大槽数：high=PAGE_N_DIR_SLOTS-1，这样，我们就得到了二分初始状态的上边界。初始状态的下边界是第一个槽（infimumslot）的序号，low=0。二分查找可能进行0~N轮（N>=1），在每一轮查找中，中间的position会通过mid=(low+high)/2来计算。然后判断要查找的记录是在低区间(low~mid)还是在高区间(mid~high)。最后根据判断结果，进入low区间或high区间，搜索范围会缩小一半，继续进行下一轮搜索，以此类推，直到low和high的值不满足以下条件high-low>1，二分查找完成。这里的二分法不仅要支持单点扫描间隔，还要支持范围扫描间隔大于、大于等于、小于、小于等于。如果找不到满足扫描区间的记录，会立即停止，而是等到low和high的值不满足循环条件时结束二分查找过程。二分查找结束时，要查找的记录始终属于highslot（上边界high对应的slot），lowslot始终是highslot的前一个slot。这对于第2步顺序搜索成功找到记录在槽中的位置至关重要。步骤2：确定记录所在的slot后，沿着每条记录的头信息中next_record的顺序查找，确定记录在slot中的位置。基于二分搜索结束时的状态，顺序搜索继续。从lowslot的最大记录开始，通过header信息中的next_record读取下一条记录。将下一条记录中的索引字段值与扫描区间中的字段值进行比较，判断下一条记录是否为扫描区间中的第一条记录。如果是，则顺序搜索过程结束。如果不是，继续读取下一条记录，判断是否是扫描区间的第一条记录，以此类推，直到下一条要读取的记录是高槽中最大的记录，查找过程结束。下面我们通过一个例子来具体化上述抽象过程。(2)准备一个主键索引的B+树，包括一个int类型的id字段，结构为B+树，包括2层：根节点和叶节点。索引结构如下图所示：我们以定位id>=700中查询条件对应的扫描区间[700,+∞)中的第一条记录为例，分析定位第一条记录的过程B+树索引中的扫描区间。(3)记录在哪个叶子节点？示例索引的B+树包括根节点和叶节点两层，从根节点开始定位扫描区间内的第一条记录。按照抽象过程描述的步骤，首先通过二分查找确定[700,+∞)扫描区间的第一条记录在哪个slot。示例索引的B+树在根节点中有8个槽。初始状态下，二分上下边界为：low=0，high=8-1=7。第一轮二分搜索，计算中间位置mid=(low+high)/2=(0+7)/2=3，得到低区间(low~mid=>0~3)，高区间(mid~high=>3~7)。中间位置对应slot3（序号为3的slot），其最大记录id=41，小于扫描间隔左端点值700，表示id>=700的第一条记录（下同）直接简称为第一条记录))位于高位区间。修改下边界值，low=mid=3，进入high区间。第二轮计算中间位置mid=（低+高）/2=（3+7）/2=5，得到低区间（3~5）和高区间（5~7）。中间位置对应slot5，其最大记录id=81，小于扫描区间左端点值700，说明第一条记录位于高区间。修改下边界值，low=mid=5，进入high区间。第三轮，计算中间位置mid=（低+高）/2=（5+7）/2=6，得到低区间（5~6）和高区间（6~7）。中间位置对应slot6，最大记录id=901，大于扫描区间左端点值700，说明第一条记录在低区间。修改上边界值，high=mid=6。则high-low=6-5=1，不满足循环条件high-low>1，二分查找结束。扫描间隔左端点值为700，大于slot5最大记录id值（81），小于slot6最大记录id值（901），说明第一个record属于slot6的管辖（此时slot6为highslot）。接下来，需要进入顺序查找的主域，找到槽中第一条记录的位置。顺序查找二分查找结束时，low=5（slot5），最大记录的id=81；high=6（slot6），最大记录的id=901。在二分查找过程中，已经确定扫描间隔700的左端点值在slot6，所以在顺序查找过程中，有不需要读取id=81的记录（slot5的最后一条记录），而是从这条记录的下一条记录，也就是slot6的第一条记录开始。第一轮读取下一条id=81的记录，得到id=101的记录，101小于扫描间隔700的左端点值，需要继续读取下一条记录进行比较。第二轮读取下一条id=101的记录，得到id=888的记录。888大于扫描间隔700的左端点值，锁定id>=700的第一条记录，即位于101和888之间，也就是id=888之前。但是id=888的记录是它所在的叶子节点的索引页上的第一条用户记录。id>=700的第一条记录不能和id=888的记录在同一个索引页，只能基于这个索引页的前一个索引页。在根节点中，id=101是id=888的上一条记录，id=101所在的叶节点索引页就是id=888所在的叶节点索引页的上一页。最后，id>=700的第一条记录也位于id=101的记录所在的叶节点索引页中。至此，经过两轮比较，确定了id>=700的第一条记录所在的叶节点索引页，顺次查找过程结束。接下来从记录id=101中读取对应叶节点索引页的页码，进入叶节点。(4)叶节点中的记录在哪里？在示例索引的B+树中，叶子节点中有10个槽位。在初始化状态下，二分查找的上下边界为：low=0，high=10-1=9。二分查找第一轮，计算中间位置mid=(low+high)/2=(0+9)/2=4，得到低区间(low~mid=>0~4)，高区间(mid~high=>4~9)。中间位置对应slot4，其最大记录id=404，小于扫描间隔左端点值700，说明id>=700的第一条记录（简称第一条记录）位于高区间。修改下边界值，low=mid=4，进入high区间。第二轮，计算中间位置mid=（低+高）/2=（4+9）/2=6，得到低区间（4~6），高区间（6~9）。中间位置对应slot6，其最大记录id=606，小于扫描区间左端点值700，说明第一条记录位于高区间。修改下边界值，low=mid=6，进入high区间。第三轮，计算中间位置mid=（低+高）/2=（6+9）/2=7，得到低区间（6~7）和高区间（7~9）。中间位置对应slot7，最大记录的id为707，大于扫描区间左端点值700，说明第一条记录在低区间。修改上边界值，up=mid=7，此时high-low=7-6=1，不满足循环条件up-low>1，循环结束。扫描间隔左端点值为700，大于slot6最大记录id（606），小于slot7最大记录id（707），说明第一条记录属于到7号槽的管辖（此时7号槽为高槽）。接下来，是时候找到槽中第一条记录的位置了。顺序查找二分查找结束时，low=6（slot6），最大记录的id=606；high=7(slot7)，最大记录的id=707。在二分查找过程中，已经确定第一条记录在slot7范围内，所以在顺序查找过程中，不需要读取id=606的记录（slot6的最后一条记录），而是从这条记录的下一条记录，也就是slot7的第一条记录开始。第一轮读取下一条id=606的记录，得到id=666的记录。666小于扫描间隔700的左端点值，需要读取下一条记录进行比较。第二轮读取下一条id=666的记录，得到id=688的记录，688小于扫描区间左端值700，继续读取下一条记录。第三轮，读取下一条id=688的记录，得到id=700的记录，等于扫描间隔700的左端点值，满足id>=700的条件。至此，经过3轮比较，id>=700对应的扫描区间[700,+∞)的第一条记录已经找到，叶节点的顺序查找过程结束，整个过程定位到第一个记录在扫描间隔也完成了。结束了。5.性能优化在前面的介绍中，二分查找位置槽，顺序查找位置记录的过程中，涉及到比较扫描间隔字段值和索引字段值，但是我们没有进一步介绍比较过程。如果只是常规比较，无非就是循环扫描区间内的字段，与索引中对应的字段一一进行比较，就不用多说了。但是，InnoDB优化了比较过程。对于已经比较过的字段和字段前面的内容，尽量避免重复比较，以提高二分查找和顺序查找过程的执行效率，从而提高性能。InnoDB对叶子节点的优化比根节点和内部节点更进了一步。我们将分两节介绍根节点&内部节点和叶节点的二分查找和顺序查找的优化。.(1)根节点和内部节点优化以上图中索引页中slots的样本数据为例，以查询条件i1>=160andi2>=44为例，分析定位的左端点scaninterval160,44(using这表示扫描区间的第一条记录在哪个slot的进程。初始状态下，二分查找的上下边界为：low=0,high=13。二分查找第一轮，计算中间位置mid=(low+high)/2=(0+13)/2=6，得到低区间(low~mid=>0~6)，高区间(mid~high)=>6~13).中间位置对应slot6，其最大记录i1=160,i2=33.比较扫描区间左端点与中最大记录的i1、i2字段值slot6一个一个判断扫描区间左端点是在低区间还是高区间，先比较i1字段值，i1扫描区间左端的字段值和索引中的i1字段值都等于160，然后比较i2字段的值。扫描区间左端i2字段（44）的值大于索引记录中i2字段（33）的值，说明扫描区间左端值为160，44为位于高区间（插槽6至13）。修改下边界值，low=mid=6，进入high区间。第二轮计算中间位置mid=（低+高）/2=（6+13）/2=9，得到低区间（6~9）和高区间（9~13）。中间位置对应slot9，其最大记录i1=160，i2=66。将扫描区间的左端点与slot9最大记录的i1、i2字段值一一比较确定扫描区间的左端点是在低区间还是高区间。先比较i1字段值，扫描区间左端的i1字段值和索引记录中的i1字段值都等于160。然后比较i2字段的值。扫描区间左端的i2字段值（44）小于索引记录中的i2字段值（66），说明扫描区间左端点值为160，44位于低间隔（插槽6至9）。修改上界值，high=mid=9，进入低位区间。第三轮，计算中间位置mid=（低+高）/2=（6+9）/2=7，得到低区间（6~7）和高区间（7~9）。中间位置对应slot7，其最大记录i1=160，i2=44。按照第一轮和第二轮的套路，是时候比较左端点的i1和i2字段值了扫描间隔和槽位7中的最大记录一一对应。但是……重点来了。第一轮比较后，确定扫描区间左端点值为160，44位于6到13槽之间；第二轮比较后，确定扫描区间左端点值为160，44位于6和9之间的槽位。取交点：扫描区间左端点值为160，44为位于插槽6-9之间。从前面的示意图可以看出，在slot6和slot9之间，每个slot中最大记录的i1字段值为160，扫描间隔左端的i1字段值也是160。在这个范围内，无论接下来要进行多少轮比较，都可以确定该记录的i1字段的值等于扫描区间左端的i1字段的值。由于比较前可以确定比较结果相等，所以不需要比较i1字段的值。二分查找完成后，后面的顺序查找过程也在这个范围内，就不用再去比较i1字段的值了。那么，本节我们要讲的就是InnoDB对定位过程的优化。目标已经实现。对于上面的例子，剩下的二分查找和顺序查找过程就不再分析了。(2)叶节点优化如果在二分查找过程中能够锁定一个范围，则叶节点的二分查找和顺序查找过程不仅可以跳过前面N个已经比较过且相等的字段，而且可以走得更远，跳过第N+1个字段中已比较且相等的前M个字节。但是跳过已经比较过的字节有一些限制，只能应用于以下字段：tinyint,int,smallint,mediumint,bigint,tinyblob,blob,mediumblob,longblob,binary,varbinary类型的字段。InnoDBB-TREE根节点，内节点记录中指向子节点索引页的页码。InnoDBB-TREE叶节点记录中的DB_ROW_ID、DB_TRX_ID、DB_ROLL_PTR字段。对于以上几类字段，在二分查找和顺序查找的过程中，源码需要循环字段内容，逐字节比较。我们还是用一个具体的例子来说明：有一个B-TREE索引，它包含2个字段，i1是int类型，b1是blob类型，如下图：假设左端i1字段的值扫描间隔的值为160，b1字段的值前1000字节值为0x0010x002…0x9990x1000。再假设经过前两轮比较后，扫描区间的左端点已经锁定在slot6和slot9之间，这个区间内所有记录的i1字段值为160，b1字段的前1000字节所有记录中的0x0010x002…0x9990x1000。如果在第三轮及之后的二分查找和顺序查找时只跳过已经比较过的i1字段，对于b1字段，每次都要从第一个字节开始比较，前1000字节byte-by重复进行字节比较。根据我们前面介绍的场景，在锁定范围内（slot6~9），扫描区间左端的i1字段等于所有记录的i1字段值；b1字段前1000个字节也相等，不用比较，yes可以跳过。那么，在后续二分查找的比较和顺序查找过程中，只需要从b1字段的第1001个字节开始比较，就可以避免更多重复的比较操作。6.小结在正式进入本文主题之前，第2节和第3节首先介绍了扫描区间的定义，并对每种扫描区间进行了说明；然后介绍一下索引页中与本文比较相关的结构：记录链表、伪记录、槽（SLOT）。第4节首先描述了通过二分法搜索位置槽和顺序搜索位置槽中的记录的抽象过程。然后以一个2层的B-TREE索引为例，详细分析了如何通过二分法查找位置槽和顺序查找位置槽。每一步都记录在.第5节介绍，InnoDB为了减少二分查找locationslots过程中的比较次数，顺序查找locationslots中的记录，锁定一个范围后，对于根节点和内部节点，可以跳过已经比较并确认为相等的字段；对于叶子节点，除了跳过字段外，还可以跳过已经比较并确认相等的字段中前面的部分字节。本文转载自微信公众号“一树一溪”，可通过以下二维码关注。转载本文请联系艺书艺熙公众号。
