B+ 树

形式陈述 ​

B+ 树沿用B 树公理库B 树B-tree以高扇出、有界节点占用率和等深叶层降低外存查找 I/O 的平衡搜索树。的高扇出、节点占用下界和所有叶等深性质，但内部节点只保存分隔键与子指针，完整记录或键值对全部位于叶节点。查找从根按分隔区间下降，即使内部出现与目标相等的 separator，也必须继续到叶层确认记录。叶节点按键序通过 next 指针连成链公理库链表Linked list节点通过指针连接并支持局部插入删除的线性数据结构。，常同时保留 prev 指针支持反向扫描。

内部节点中 separator 的具体约定可选，例如令 $k_i$ 等于右子树最小键；关键不变量是每个子指针负责的键区间互不冲突并覆盖该节点范围。插入先修改叶；叶溢出时分裂并把右叶首键的副本插入父节点，父节点也可能递归分裂。删除造成低占用时向同层兄弟借记录或合并，并同步修正祖先 separator。若每个节点占一外存块，单键操作为 $O({\log }_{B}N)$ I/O，连续输出 $z$ 条记录通常为 $O({\log }_{B}N+z/B)$ I/O。

直觉 ​

内部层只负责导航，把记录集中到叶层后，一个内部块可以装入更多键与指针，树高往往更小。叶链又把逻辑相邻记录变成可连续读取的物理访问序列：先用树定位范围起点，随后顺链扫描，不必为每个后继键重新走根路径。

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

例子与边界 ​

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

叶分裂时若左叶保留较小半、右叶接收较大半，父节点插入右叶最小键作为 separator；该键同时出现在叶中并不表示两份独立记录。删除右叶首键后，即使节点未欠载，父 separator 也可能需要更新，否则后续路由仍使用旧边界。

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

推论与应用 ​

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

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

参考资料

• Douglas Comer, “The Ubiquitous B-Tree,” ACM Computing Surveys 11(2), 1979, pp. 121–137.
• Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom, Database Systems: The Complete Book, 2nd ed., Pearson, 2009, Ch. 14.