InnoDB B-TREE 索引怎么定位一条记录？

对于 SQL 语句的执行来说，定位 B-TREE 索引中的一条记录，是个举足轻重的能力。

InnoDB 是基于索引组织数据的，更新、删除操作都需要先去索引中找到具体的记录。

插入操作也需要先找到记录要插入到索引的哪个位置。

查询语句的 WHERE 条件能够命中索引时，也需要先找到 WHERE
条件对应的扫描区间的第一条记录，然后从这条记录开始沿着索引页内记录之间的单向链表、索引页之间的双向链表依次读取后续的记录。

通过以上简短的介绍，定位 B-TREE 索引中的记录的重要性就显而易见了。

本文是 MySQL 8 的第一篇文章，也是查询优化器的开篇。希望通过本文的介绍，能为大家理解后续文章打下一些基础。

本文内容基于 MySQL 8.0.29 源码。

正文

1、 概述

更新、删除、查询操作定位索引中的一条记录，插入操作找到要插入的位置，过程基本上是一样的，源码中也是在同一个方法中实现。

本文以 WHERE 条件能够命中索引为前提，介绍查询操作定位 WHERE 条件扫描区间的第一条记录。

定位记录过程中进行的二分法查找、顺序查找，会涉及到索引页的部分结构。

接下来会先用 2 个小节分别介绍扫描区间、以及和定位记录过程相关的索引页的部分结构。

2、什么是扫描区间?

扫描区间就是 WHERE
条件中，由字段、关系运算符(