B+ 树节点页内部是如何查找 key 的？为什么页内通常还要二分？
简化版
B+ 树先通过树层级定位到某个页，页内部还存着多个有序 key。进入页后需要在这些 key 中找到分支位置或记录位置，常见做法是页内二分查找；因为页已经在内存里，页内 CPU 比较成本远低于磁盘 I/O。
详细版
B+ 树节点不是只存一个 key，而是一个页里存很多 key 和指针。查找流程一般是：
- 从根页开始；
- 在当前页内部的 key 数组里查找目标 key 应该落在哪个槽位；
- 如果是内部页，沿对应子指针到下一层；
- 如果是叶子页，在页内定位具体记录或判断不存在。
页内 key 有序，可以线性扫，也可以二分。扇出较大时二分比较次数更少，例如 256 个 key 线性最坏 256 次，二分约 8 次。实际数据库页结构还涉及槽目录、变长记录、前缀压缩等，逻辑上仍是在页内有序定位。
完整版教学
一、B+ 树查找不是只在树层面发生
很多人理解 B+ 树时只画根、内部节点、叶子节点，却忽略每个节点实际是一个磁盘页或内存页。一个页里通常包含很多 key、指针或记录。树层面决定访问哪几个页，页内部还要决定落在哪个槽位。
因此一次查询有两层查找：页间从根到叶，页内在有序 key 中定位。B+ 树高度低，是因为每页扇出大；页内查找快，是因为页读进内存后 CPU 比较很便宜。
记忆钩子：B+ 树查找像进图书馆：先按楼层和书架找页，再在这一页目录里找具体位置。
二、页内为什么可以二分
内部页中的分隔 key 是有序的，叶子页中的索引项也按 key 有序。只要有序，就可以二分查找目标 key 的第一个大于等于位置，或找到应走的子指针区间。
例如页内 key：
[10, 20, 35, 50, 80]
查 42 -> 落在 35 和 50 之间，走对应 child
查 20 -> 命中分隔点或定位到对应范围若页内有 255 个 key，二分最多约 ceil(log2(255))=8 次比较。相对一次随机磁盘 I/O 的微秒到毫秒级成本，这点 CPU 成本很小。
三、内部页和叶子页查找有什么区别
内部页查找的目标是找到子指针，叶子页查找的目标是找到记录或记录范围起点。内部页的 key 常作为分隔符，不一定保存完整行；叶子页才保存索引项或数据行。
| 页类型 | 页内查找目标 | 找到后做什么 |
|---|---|---|
| 根页 | 子指针槽位 | 进入下一层 |
| 内部页 | 子指针槽位 | 继续向下 |
| 叶子页 | 记录或范围起点 | 返回、扫描或回表 |
这也是为什么范围查询定位到叶子页后，可以沿叶子链表继续扫，而不必反复回到父节点。
四、页内线性扫一定不好吗
不一定。虽然二分比较次数少，但数据库实现会考虑 CPU 缓存、分支预测、key 压缩、槽目录结构等因素。对于很小的页内数组，线性扫描可能因为顺序访问和代码简单而表现不错。对于较大的页内 key 集，二分或变体通常更合适。
这个问题的面试重点不是背某个数据库一定用二分，而是知道「B+ 树节点页内部还有有序查找」。不同系统可能在线性、二分、插值、SIMD 比较之间做工程取舍。
五、页目录和变长记录带来的复杂度
真实页里记录可能是变长的，不一定像数组那样紧密固定长度。数据库常用槽目录保存记录偏移，槽位有序，二分查的是槽目录，再根据偏移找到具体记录。这样即使记录物理位置因为插入删除产生碎片，逻辑顺序仍能维持。
Page
records area: 变长记录实际内容
slot directory: [offset(key10), offset(key20), offset(key35)]这说明「页内二分」是逻辑模型，落地实现会多一层页目录抽象。
六、页内查找和 B+ 树高度的关系
B+ 树把大量 key 放进一个页，换来高扇出和低高度。高度低减少 I/O 次数，页内查找增加 CPU 比较次数。这个交换非常划算，因为磁盘或缓存未命中的页访问远比内存内比较贵。
假设一棵三层 B+ 树，每层一次页访问，可能只需 3 次页读取定位到叶子。如果每个页内二分 8 次，合计 24 次比较。与减少一层树高带来的 I/O 节省相比，这些比较通常很便宜。
七、常见误区与追问
- 误区：B+ 树每个节点只有一个 key。 数据库里的节点通常是页，一个页有很多 key。
- 追问：页内为什么还能二分？ 页内 key 或槽目录按 key 有序，满足二分前提。
- 误区：B+ 树查找复杂度只看树高。 树高决定页访问次数，页内定位也有 CPU 成本。
- 追问：内部页查找和叶子页查找有什么不同？ 内部页找子指针，叶子页找记录或扫描起点。
- 误区：二分永远比线性扫快。 小数组、缓存和分支因素可能让实现做不同取舍。
八、加强记忆
B+ 树查找要分成「页间」和「页内」。页间沿根到叶减少 I/O，页内在有序 key 或槽目录里定位位置。页越大扇出越高，树越矮；页内比较多一点，但在内存里很便宜。记住这个层次，就能解释为什么 B+ 树适合磁盘和页缓存，而不是只会背高度低。