面试题：MySQL InnoDB页目录中如何通过二分查找定位记录

Question

请阐述在MySQL InnoDB页目录里，使用二分查找来定位具体记录的步骤和原理。

Answer 1

1. 原理：
   • InnoDB 页目录中的槽（slot）按记录主键值顺序存放，类似一个有序数组，每个槽指向对应记录。
   • 二分查找基于有序数据结构，通过每次比较中间位置值与目标值，决定下一步搜索方向，逐步缩小查找范围，直到找到目标记录或确定记录不存在。
2. 步骤：
   • 初始化：
     • 设有页目录槽数组，其索引范围为(0)到(n - 1)（(n)为槽数量）。设两个指针，low = 0指向槽数组起始位置，high = n - 1指向槽数组末尾位置。
   • 循环查找：
     • 计算中间位置mid = (low + high) / 2 ，得到中间槽的索引。
     • 取出中间槽指向记录的主键值，与要查找记录的主键值比较：
       • 若相等：则找到目标记录，返回该记录。
       • 若中间记录主键值小于目标主键值：说明目标记录在中间槽右侧，更新low = mid + 1，缩小查找范围到右半部分。
       • 若中间记录主键值大于目标主键值：说明目标记录在中间槽左侧，更新high = mid - 1，缩小查找范围到左半部分。
   • 结束条件：
     • 当low > high时，说明在页目录中未找到目标记录，查找结束。