B+ 树

内部层只负责导航，把记录集中到叶层后，一个内部块可以装入更多键与指针，树高往往更小。叶链把按键相邻的叶页连接起来：先用树定位范围起点，随后顺链扫描，不必为每个后继键重新走根路径。相邻叶页在磁盘上未必物理连续，因此这个保证是少读索引页，不是每次读取都能变成连续磁盘访问。

B+ 树不是“B 树再加一层”，而是重新分配两类节点的职责。内部 separator 可能复制叶键，但复制的是导航信息，不是重复存放整条记录。

图中根的分隔键为 $40,70$，三个叶页分别保存 $[10,20,30]$、$[40,50,60]$、$[70,80,90]$。查询 $[45,80]$ 先进入中间页，跳过 $40$，输出 $50,60$；沿 next 到右页输出 $70,80$，遇到 $90$ 就结束。根只用于首次定位，叶链承担后续扫描。

索引键按学生编号排序时，查询单个编号沿内部 separator 到达唯一候选叶，再在叶内确认。查询区间 $[202000,202999]$ 则先定位第一个不小于下界的叶位置，然后沿叶链输出，越过上界即停止。范围成本与实际输出块数相关，而非为每条记录再次支付树高。

叶分裂时若左叶保留较小半、右叶接收较大半，父节点插入右叶最小键作为 separator；该键同时出现在叶中并不表示两份独立记录。在本页“右子树最小键”的约定下，删除右叶首键后，即使节点未欠载，也须更新相应 separator。例如删除 $70$ 后将根中的 $70$ 改为 $80$。有些实现只要求 separator 是合法范围边界，允许保留过时但仍能正确路由的分隔值；不能把两种维护契约混用。

重复键会破坏“一个键定位一条记录”的默认叙述。实现可以把重复记录集中成列表、用复合键区分，或允许跨叶重复；选择必须与范围边界和删除语义一起规定。并发更新还涉及页锁、版本和崩溃恢复，不由树形定义自动解决。

B-link树理路B-link树：父页滞后时的查找B-link tree · Lehman–Yao tree · B-link concurrent search给每层页加范围上界和右链，让查找在父页尚未登记分裂时向右修正，并明确原子页图像与发布次序。将这里的并发结构边界具体化：在每层增加排他上界与右链，先初始化新右页，再整体发布旧页的左半与链接，允许父页暂时落后。读者拿着旧父指针仍能向右修正，但一致页图像、页生命周期和持久化责任必须分别满足。

B+ 树是数据库与文件系统有序索引的常见结构，尤其适合等值查找、范围查询和全序遍历混合负载。叶链把树索引与顺序文件连接起来，内部高扇出则控制访问层数。

聚簇索引会让叶顺序接近记录物理顺序，非聚簇索引的叶可能只存记录标识；两者拥有同一 B+ 树路由语义，却有不同的数据访问成本。分析时应把索引 I/O 与回表 I/O 分开。

覆盖访问与回表的四笔账 ​

把叶条目定义为(key,RID,payload)，RID指向堆文件中的记录。覆盖索引表示查询所需的返回列及残余过滤列都能从索引得到或由其条件保证；不只是WHERE中的搜索列出现在索引里。即使值覆盖，事务可见性仍可能要求读取堆页，不能把“覆盖”直接写成“物理上零回表”。

固定冷缓存下定位首个匹配叶的路径为根、内部页、首叶共3页；匹配范围跨2个叶页，后继叶再读1页，共4个索引页。六个匹配RID依次指向堆页h1,h1,h5,h8,h8,h9。若能保留或按页集中处理这些访问，额外回表读4页，合8；若六个RID各落不同页，则是10。若数据与可见性都能在已缓存的辅助状态加索引中判断，覆盖访问只有4个索引页。输出页、辅助状态缺页和维护成本在这些数之外。

这里“不同堆页数”是能够复用同页读取的成本，不是所有缓冲调度的无条件上界。若RID顺序反复交错、缓存过小，被淘汰页可以重读。顺序扫堆的成本也应加入备选：若整表仅5页而索引方案要8页，在统一I/O计价下扫描更便宜。设备随机读权重与缓存状态另行影响实际选择。

重复搜索键可用复合(key,RID)保证索引条目唯一，或用每键的RID列表；等值查询必须遍历整个同键范围。叶条目从两个相同key返回两个RID，是两份记录出现，不能把它们误当导航separator的无意义副本。增加payload也会降低每叶容量、增加叶页数，所以上面2个匹配叶的假设必须针对具体覆盖索引重新计算。

PostgreSQL的index-only scan还查询visibility map：对应堆页若不能证明all-visible，仍需到堆里检查MVCC。这个实现例说明结构层覆盖与逻辑可见性是两层条件；它不把本页单版本B+树定义改成某一种MVCC格式。

多个访问路径的RID还可在位图堆访问理路位图堆访问、候选组合与有损重检Bitmap heap scan · TID bitmap · Lossy bitmap · Bitmap recheck以稳定物理出现构造多个索引候选，定义exact与lossy页的AND/OR，证明完整重检恢复真实bag，并核算降精度、访问次序与索引加回表成本。中按物理出现做AND/OR组合，再按页回表。忘掉槽号的lossy页必须完整重检；同一RID只检索一次，不会把不同RID的同值记录去重，原索引键序也不能沿用。