299 字
1 分钟
MySQL B+ 树查询全过程：从根节点到页目录
一次 B+ 树查询可以拆成两段：先从根节点向下定位叶子页，再在叶子页内部找到具体记录。
从根节点定位叶子页
从根节点开始，将查询键与节点中的索引值比较，用二分法确定子指针，继续向下查找，直到叶子节点。一棵三层 B+ 树通常最多经历三次页级磁盘 I/O 才能定位到叶子页。
在叶子页内定位记录
InnoDB 的叶子节点是约 16KB 的数据页。页目录把记录分成若干组，每个槽指向一组的最大记录。查询先在页目录中二分定位，再沿组内单向链表遍历，找到目标记录。
根节点 → 中间节点 → 叶子节点 → 页目录二分 → 组内链表遍历叶子页的内部结构
页头记录页号、页类型以及前后页指针；用户记录区保存实际数据；页目录负责加速页内查询；文件尾保存校验信息。叶子页之间通过双向链表连接，因此范围查询可以顺着叶子链表继续读取。
MySQL B+ 树查询全过程：从根节点到页目录
https://blog.xqcherry.top/posts/interview/mysql/b-plus-tree-query/ 目录