MySQL是如何在特定索引页（page）内定位目标键值的？

我们通常讨论的MySQL索引页内查找逻辑，默认指的是其最常用的InnoDB存储引擎的实现，具体逻辑如下：

核心结论 #

InnoDB不会对页内全量键值做线性扫描，也没有在页内实现额外的局部树结构，而是采用「页目录二分查找 + 小范围线性遍历」的组合方案，兼顾了查找效率和页的读写性能。

查找逻辑依赖的页结构设计 #

InnoDB默认的索引页大小为16KB，和查找相关的核心结构分为两部分：

• 用户记录区：所有索引键值+数据/子页指针的记录，按索引键升序逻辑串联为单向链表，逻辑上有序但物理存储不需要连续，插入、删除记录时不需要挪动大量数据。
• 页目录区：将用户记录按每4~8条为一组拆分，每组对应一个「槽（Slot）」，槽中存储该组最大索引键对应记录在页内的偏移地址。所有槽是按索引键升序排列的紧凑数组。

单页内的完整查找步骤 #

定位到目标索引页后，查找目标键K的流程为：

1. 对页目录的槽数组执行二分查找，快速定位到K值所属的分组：找到第一个键值大于等于K的槽，K一定落在前一个槽对应的记录组范围内
2. 从该分组的第一条记录开始线性遍历，最多遍历8条记录就能找到目标键，或者判断键值不存在。

补充说明 #

对于高频访问的热点数据页，InnoDB如果开启了自适应哈希索引（默认开启），会自动对高频查询的键值建立内存哈希映射，查询时可以直接跳过B+树遍历和页内查找步骤，直接定位到记录位置，进一步提升查询性能。

内容的提问来源于stack exchange，提问作者mind_religion