6.2 B-Trees：页访问、多路查找、分裂与结构证书

6.2 · B-trees覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“6.2 · B-trees”如何以磁盘页为成本单位，用多路节点、查找、插入与分裂控制外存访问
  • 能逐项核对 B树、外存查找、多路查找节点、页访问成本、B树查找、插入与分裂，并区分作者站内容与本页独立补充
  • 能按“M 阶 B 树高度为 O(log_M N)，一次查找读取从根到叶的一页序列”手算一个最小输入，逐步检查“除根外节点保持规定的最小/最大占用，所有叶位于同一深度，键分隔子树范围”
  • 能注入“满节点分裂时提升了错误中位键，或只更新兄弟页而漏写父页的子指针”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“6·2 · B-trees”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“6·2 · B-trees”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“6·2 · B-trees”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：6.2 · B-trees

  • 1. B树：在本页通过“读取根页”连接解释、交互状态和练习验收。
  • 2. 外存查找：在本页通过“页内定位区间”连接解释、交互状态和练习验收。
  • 3. 多路查找节点：在本页通过“下降到子页”连接解释、交互状态和练习验收。
  • 4. 页访问成本：在本页通过“插入并检测溢出”连接解释、交互状态和练习验收。
  • 5. B树查找、插入与分裂：在本页通过“分裂提升并核对叶深”连接解释、交互状态和练习验收。

从“一次磁盘页访问，应该多带回几百个分支”开始

B树（B-trees）不是为了减少CPU comparisons，而是为了减少slow storage与fast memory之间的page transfers。

先预测：有十亿keys时，binary search tree高度约30；若一个8 KiB page能容纳约300个separator/pointer pairs，B-tree可能只需4层左右。即使每层在page内比较若干keys，昂贵I/O次数仍从几十次降到几次。

外存查找（external-memory search）把数据分成pages。Root与hot upper levels可能cache在memory，访问lower child通常触发I/O。

6.2.1 Page model：fanout由format决定

设page size为B bytes，header/slot metadata为H，separator key平均K bytes，child pointer或page id为P bytes。粗略fanout：

m≈⌊B−HK+P⌋m\approx\left\lfloor\frac{B-H}{K+P}\right\rfloor

实际layout还受prefix compression、variable-length records、alignment、checksums、sibling links与fill factor影响，但公式揭示核心：一个page携带many routes。

页访问成本（page access cost）近似tree height。若branching factor为m、records为N：

H=O(log⁡mN)H=O(\log_m N)

Page变大可提高fanout，却增加read amplification与split write size；key/pointer变大则降低fanout。Production index必须以真实serialized bytes测量，而不是用object count代替。

6.2.2 Multiway search nodes：separator partition key space

多路查找节点（multiway search nodes）把key space切成ordered ranges。

对于separators (k_1\lt k_2\lt\cdots\lt k_q)，q+1 children分别负责：

(−∞,k1), [k1,k2),…,[kq,+∞)(-\infty,k_1),\ [k_1,k_2),\ldots,[k_q,+\infty)

Exact inclusive/exclusive convention由implementation定义；关键是每个search key只进入one child，并且所有descendant keys满足该child range。

Page内route可linear scan、binary search或SIMD search。它影响CPU cost，不改变每层只读取一个child page的I/O path。Variable-length keys还需明确comparison/collation与separator truncation rules。

6.2.3 B-tree invariants：局部node规则构成全局balance

设order convention允许最多m children。常见B-tree invariants：

  1. 每个node keys strictly sorted。
  2. Internal node有q keys时有q+1 children，或按实现的sentinel-entry convention有对应entry count。
  3. Child subtrees满足parent separator ranges。
  4. 除root外，每个node至少half full、至多full。
  5. All leaves位于same depth。
  6. Root可有较低occupancy；empty tree是special root。

定义“order”“degree”“keys per node”在教材和数据库间并不统一。验收不能只写“minimum degree t”，必须把max keys、max children、min occupancy、separator ownership和leaf payload placement逐项列出。

All-leaves-same-depth由split propagation维持，不依赖rotations。它给出worst-case height bound。若minimum children约为 m/2m/2，height随 log⁡m/2N\log_{m/2}N 增长；即使nodes只half full，high fanout仍让树很矮。

6.2.4 Search：一页内选一个child

B-tree search insertion and splitting先从search开始。At external/leaf node，比较keys并返回matching value或absent；at internal node，找到包含target的child interval并递归height-1。

Official BTree.java的internal entry key代表其child subtree的lowest key。Search选择j，使j是last entry，或target小于next entry key：

private Value search(Node x, Key key, int ht) {
    Entry[] children = x.children;
    if (ht == 0) {
        for (int j = 0; j < x.m; j++)
            if (eq(key, children[j].key)) return (Value) children[j].val;
    } else {
        for (int j = 0; j < x.m; j++)
            if (j + 1 == x.m || less(key, children[j + 1].key))
                return search(children[j].next, key, ht - 1);
    }
    return null;
}

Correctness invariant：进入node x时，target属于x的range。Sorted separator scan选择唯一containing child；induction到leaf后，exact key comparison决定found/absent。

Search certificate应记录page ids、separator interval与chosen slot。只返回value无法定位bad separator是否恰好被sample绕过。

6.2.5 Insert：先到leaf，再把overflow向上传播

Abstract 2-3-4 style insertion：

  1. Descend到target leaf。
  2. 按sorted order插入key/value；existing key按map contract update。
  3. Node overflow时围绕median split成left/right pages。
  4. 把median或right-page lower bound作为separator插入parent。
  5. Parent也可能overflow，继续向上。
  6. Root split时创建new root，height加一。
Node u = insert(root, key, value, height);
if (u != null) {
    Node nextRoot = new Node(2);
    nextRoot.children[0] = entry(minKey(root), root);
    nextRoot.children[1] = entry(minKey(u), u);
    root = nextRoot;
    height++;
}

每次insert只访问one root-to-leaf path，再沿同一路径传播splits。Worst-case page writes为O(height)，而不是重建全树。

6.2.6 Split：restore occupancy并保持key ranges

节点分裂发生在node达到overflow capacity时，必须同时维护：

  • Left/right entries各自sorted。
  • 两边occupancy合法。
  • Parent新增separator正确划分ranges。
  • Internal children不丢失、不重复。
  • Leaf depth不变。

通用B-tree常把median key提升到parent；B+ tree通常把records都留在leaves并复制right lower bound到parent。Official implementation采用entry-array convention：M=4且M必须even，node到4 entries时：

private Node split(Node h) {
    Node t = new Node(M / 2);
    h.m = M / 2;
    for (int j = 0; j < M / 2; j++)
        t.children[j] = h.children[M / 2 + j];
    return t;
}

Left保留前2 entries，returned right持有后2；caller用right first key建立parent entry。Stable node在下一次overflow前最多3 entries。

6.2.7 Root growth与height

Only root split增加height。New root指向old left root与new right page；所有existing leaves相对new root同时加深一层，所以equal leaf depth保持。

若N records、effective branching m，page probes大致：

1+⌈log⁡mN⌉1+\lceil\log_m N\rceil

其中1是否单列取决于height definition：官方empty/single external root的height为0，但search仍访问root page。报告成本时应区分edge height与pages visited。

Root通常resident in cache；physical I/O可能少于logical probes。相反，copy-on-write、WAL与split可增加writes。Read height bound不能直接当update latency。

6.2.8 Official M=4 implementation layout

Current BTree.java使用一个Entry type复用两种角色：

  • Internal node：使用key和next，val unused。
  • External node：使用key和val，next unused。

Node.m表示active entries count，array capacity M=4。Search/insert递归显式携带remaining height，因此不需要在node存leaf flag。

这份代码是教学骨架，不是完整storage engine：

  • Nodes只是Java objects，不做真实page serialization、buffer pool或crash recovery。
  • M固定为4，无法展示real page fanout。
  • No deletion/rebalancing implementation。
  • Null-value-as-delete的文档与实际put path不一致。
  • put没有先查existing key：它会插入duplicate、每次n++，与“replace old value”的symbol-table contract不一致。

6.2.9 Page engineering beyond the skeleton

真实B-tree/B+ tree常加入：

  • Leaf sibling links支持range scan。
  • Prefix/key compression提高fanout。
  • Buffer pool、pin/unpin与dirty-page tracking。
  • WAL或copy-on-write保证crash consistency。
  • Latch coupling或optimistic concurrency。
  • Split/merge policy与target fill factor。
  • Checksums、page generation和root metadata。

这些机制不改变ordered multiway-search核心，却改变证书：除了logical ranges，还要检查on-disk bytes、parent/child page ids、sibling chain、LSN/recovery与concurrent visibility。

6.2.10 Independent structural certificate

单个lookup成功不能证明B-tree valid。Independent validator应从root递归传播allowed range，并检查：

function validate(node, low, high, depth) {
  assert(strictlySorted(node.keys));
  assert(node.keys.every((key) => low < key && key < high));
  assert(validOccupancy(node));
  if (node.isLeaf) recordLeafDepth(depth);
  else {
    assert(node.children.length === node.keys.length + 1);
    for (const childRange of partition(low, node.keys, high))
      validate(childRange.child, childRange.low, childRange.high, depth + 1);
  }
}
assert(allRecordedLeafDepthsEqual());

Insert differential test还应与trusted ordered map对照：random unique keys、sorted/reverse input、duplicates、root split、cascading split和missing lookup。每次mutation后立刻跑structural validator，能把first broken operation定位出来。

6.2.11 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“6.2 · B-trees”的两个最小情境间切换，再逐项选择正式概念。预测“M 阶 B 树高度为 O(log_M N)，一次查找读取从根到叶的一页序列”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

6.2 · B-trees：对象、操作与不变量

以磁盘页为成本单位，用多路节点、查找、插入与分裂控制外存访问

选择最小情境

切换正式概念

输入合同操作证书algs4-6.2 · 先给前提，再执行，再验收当前概念：1/6
页访问
每页容纳 4 个分支，在三层树中查找键 K
当前观察
B-trees：成本按读取的页数计，不按页内每次比较等同于一次磁盘 I/O
M 阶 B 树高度为 O(log_M N)，一次查找读取从根到叶的一页序列

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • B树：在实验 1 中指出对应状态，并写出一个通过条件。
  • 外存查找：在实验 2 中指出对应状态，并写出一个通过条件。
  • 多路查找节点：在实验 3 中指出对应状态，并写出一个通过条件。
  • 页访问成本：在实验 1 中指出对应状态，并写出一个通过条件。
  • B树查找、插入与分裂：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“M 阶 B 树高度为 O(log_M N)，一次查找读取从根到叶的一页序列”不是孤立结论？

问题 3：故障恢复。 怎样证明“满节点分裂时提升了错误中位键，或只更新兄弟页而漏写父页的子指针”已经修复？

小结

  • B-trees以page-sized multiway nodes降低external-memory search的page transfers。
  • Fanout由page bytes、key/pointer size与metadata决定，tree height约为log base fanout of N。
  • Multiway search nodes以sorted separators把key space分成disjoint child ranges。
  • B-tree search每层读取one page并选择one child；page access cost是主要外存指标。
  • Insert沿one path到leaf；overflow split page并把separator传播给parent。
  • Root split是height增长的唯一方式，因此all leaves始终同depth。
  • Official M=4 code在4 entries时split成2+2，内部entry使用key/next、external entry使用key/value。
  • 教学实现没有真实pages、deletion/recovery，且duplicate update语义需补齐。
  • Independent certificate必须检查sorted keys、occupancy、arity、separator ranges与equal leaf depth。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…