第 18 章 B 树、斐波那契堆与 van Emde Boas 树

本章合并原书第 V 部分导言与第 18、19、20 章。三种结构各解决一个具体问题：B 树让存在磁盘上的有序数据只需极少几次 I/O 就能查到，是数据库与行情库索引的基础；斐波那契堆把优先队列的 DECREASE-KEY 降到摊还 \(O(1)\)，是 Prim、Dijkstra 等图算法理论最快界的来源；van Emde Boas 树在关键字是有界整数时突破比较模型的 \(\Omega(\lg n)\)，与订单簿按价位（tick）组织的位图结构一脉相承。对量化读者，本章以"用途、结构要点、复杂度"为主，B 树讲得稍细，后两种讲清思路即可；需要完整伪代码和证明时请回原书。

学习目标

读完本章，你应当能够：

1. 说出 B 树的定义（最小度数 \(t\)、每结点 \(t-1\) 到 \(2t-1\) 个关键字、叶子等深），推导高度界 \(h\le\log_t\frac{n+1}{2}\)，并解释为什么它让磁盘访问次数极少。
2. 描述 B 树"遇满先分裂"的单程插入和"保证下降结点至少 \(t\) 个关键字"的删除思路；说清 B+ 树与 B 树的区别。
3. 用 B+ 树的结构解释数据库里联合索引的列顺序为什么决定范围查询快不快。
4. 列出斐波那契堆各操作的摊还复杂度，说清"懒惰合并 + 级联切断"的思想和势函数 \(\Phi=t(H)+2m(H)\)，知道它为什么在实践中很少用。
5. 说明 vEB 树如何靠"按 \(\sqrt u\) 分簇 + summary + 存 min/max"做到 \(O(\lg\lg u)\)，并把它与订单簿的分层位图联系起来。

读前导读

本章是选读。 三种结构都偏向系统工程和理论计算机科学，研究员日常写策略、做因子不需要自己实现它们。第一次读完全可以跳过本章，直接进入第 21 章（不相交集合）和第 22、23 章（图算法），后面的内容不依赖本章的细节。

如果只读一点，读这两处。 一是 18.5.1"B+ 树与行情数据库的索引"：它解释了为什么数据库按 (代码, 日期) 建索引时取单只股票的时间序列很快、取某天全市场截面却慢，以及为什么按时间追加的行情写入很快。这几条结论不需要看懂 B 树的插入删除细节也能直接用。二是 18.2.3 的高度界：一棵 B 树每个结点可以有成百上千个分支，所以 10 亿条记录也只需要三四层，查一条数据只读三四次磁盘。直观上就像一本很厚的通讯录：先翻总目录（第一层），再翻分目录（第二层），再到具体那一页，层数少，每层一次翻页。

用到的数学很少。 对数 \(\log_t n\) 表示"\(t\) 自乘多少次能到 \(n\)"，例如 \(\log_{1000}10^9=3\)；\(\lg\lg u\) 是对 \(\lg u\) 再取一次以 2 为底的对数，\(u=2^{32}\) 时 \(\lg u=32\)、\(\lg\lg u=5\)，增长极慢。斐波那契堆的复杂度依赖上一章的势能法；如果第 17 章跳过了，18.3 节只看 18.3.1 和 18.3.6 的结论即可。复杂度记号见 第 00 册第 07 章 概率中的分析工具，对数见 第 00 册第 04 章 级数与收敛。

和后面章节的关系。 第 23 章 Prim 算法提到的"斐波那契堆让理论复杂度更低"来自 18.3，那里只需要知道结论；订单簿按价位组织的位图（18.5.2）在第 07 册市场微观结构部分会再遇到。

18.1 第 V 部分概览：高级数据结构

原书第 V 部分在第 III 部分（栈、队列、散列表、二叉搜索树、红黑树）的基础上研究更专门的动态集合结构，其中两章大量使用上一章的摊还分析：

原书还提到了几种书中没有展开的结构，知道它们的名字就好：动态树（dynamic trees，Sleator–Tarjan，用于最快的网络流算法）、伸展树（splay trees，标准操作摊还 \(O(\lg n)\) 的自调整 BST）、持久化数据结构（persistent data structures，可查询历史版本——想想"任意历史时点的订单簿快照"）、融合树（fusion trees）、以及支持边增删的动态图数据结构。

18.2 B 树

18.2.1 为什么要为磁盘专门设计一种树

主存（DRAM）比磁盘贵一个数量级以上，磁盘容量又比主存大至少两个数量级，所以大数据集只能放在辅存上。原书以机械硬盘为例：7200 转的盘转一圈 8.33 ms，比 50 ns 的内存访问慢 5 个数量级以上，平均访问时间 8–11 ms。为摊薄机械等待，磁盘按页（page）读写，一页常为 \(2^{11}\)–\(2^{14}\) 字节。读一页往往比检查读到的全部内容更花时间。

因此 B 树算法的代价分两项衡量：磁盘访问次数（读写了多少页）和 CPU 时间。伪代码中用 DISK-READ(x) 把结点读进内存，用 DISK-WRITE(x) 写回。B 树算法任一时刻只需在主存里保留常数个页，所以主存大小不限制树的规模。

今天的固态硬盘、操作系统页缓存、CPU 缓存行其实是同一问题在不同层级上的重现：一次取一块比一次取一个字节划算得多，所以"每个结点塞满一块、让树尽量矮"的思路始终有效。

18.2.2 定义

B 树是推广的搜索树：内部结点 \(x\) 存 \(x.n\) 个有序关键字，就有 \(x.n+1\) 个孩子，这些关键字把 \(x\) 负责的范围切成 \(x.n+1\) 段，查找时在 \(x\) 做 \((x.n+1)\) 路分支。原书图 18.1 是一棵以英文辅音字母为关键字的 B 树：根为 M，第二层为 D H 与 Q T X；查找 R 只需经过根 → Q T X → R S 三个结点。

形式定义（\(t\ge2\) 为固定的最小度数 minimum degree）：

1. 每个结点 \(x\) 有 \(x.n\) 个非降序关键字 \(x.key_1\le\cdots\le x.key_{x.n}\)，以及布尔值 \(x.leaf\)。
2. 内部结点有 \(x.n+1\) 个孩子指针 \(x.c_1,\dots,x.c_{x.n+1}\)。
3. 关键字分隔子树范围：若 \(k_i\) 是子树 \(x.c_i\) 中任一关键字，则 \(k_1\le x.key_1\le k_2\le\cdots\le x.key_{x.n}\le k_{x.n+1}\)。
4. 所有叶子深度相同，即树高 \(h\)。
5. 除根以外每个结点至少 \(t-1\) 个关键字（因此至少 \(t\) 个孩子），根非空时至少 1 个关键字；每个结点至多 \(2t-1\) 个关键字（至多 \(2t\) 个孩子）。恰有 \(2t-1\) 个关键字的结点称为满的（full）。

\(t=2\) 是最简单的情形：每个内部结点有 2、3 或 4 个孩子，即 2-3-4 树；把红黑树中每个黑结点和它的红孩子合成一个结点，得到的就是 2-3-4 树（原书 18.1-5），两者是同一棵树的两种画法。实践中 \(t\) 取几十到上千。

两个常见变体：B+ 树（B+-tree）把卫星数据（记录本身或指向记录的指针）全部放在叶子，内部结点只存关键字和孩子指针，以最大化内部结点的分支因子；叶子之间通常还按顺序串成链表，便于范围扫描。B* 树要求内部结点至少 2/3 满。

18.2.3 高度：为什么 B 树这么矮

定理 18.1　任意含 \(n\ge1\) 个关键字、高 \(h\)、最小度数 \(t\ge2\) 的 B 树满足

证明思路：求高度为 \(h\) 的 B 树至少有多少关键字。根至少 1 个关键字、2 个孩子；深度 1 至少 2 个结点，深度 2 至少 \(2t\) 个，……，深度 \(h\) 至少 \(2t^{h-1}\) 个，非根结点每个至少 \(t-1\) 个关键字，所以

即 \(t^h\le(n+1)/2\)。

红黑树和 B 树的高度都是 \(O(\lg n)\)，但 B 树对数的底是 \(t\)，查访结点数约少 \(\lg t\) 倍。原书图 18.3 给出一个震撼的例子：每个结点 1000 个关键字（分支因子 1001）、高度为 2 的 B 树，可以存 \(1000+1001\times1000+1001^2\times1000\)，即超过 10 亿个关键字；根常驻内存，找任何关键字至多读 2 次盘。

18.2.4 查找

B-TREE-SEARCH 是 BST 查找的直接推广：在结点内找到第一个不小于 \(k\) 的关键字，相等则返回，否则下降到对应孩子。磁盘访问 \(O(h)=O(\log_t n)\)；结点内线性扫描时 CPU 时间 \(O(t\log_t n)\)，改成二分查找后为 \(O(\lg n)\)，与 \(t\) 无关（原书 18.2-6）。

18.2.5 插入：遇满先分裂

B 树不能像 BST 那样新建一个叶子（那会破坏"叶子等深"），只能把关键字放进已有的叶子。叶子满了怎么办？分裂（split）：把有 \(2t-1\) 个关键字的满结点 \(y\) 按中位关键字 \(y.key_t\) 一分为二，两半各 \(t-1\) 个关键字，中位关键字上移到父结点作为两半的分界。父结点也可能满，于是分裂可能一路向上传到根。

原书的技巧是单程（one-pass）插入：从根往下找插入位置时，一路上遇到满结点就预先分裂（包括叶子）。这样每当要分裂某个结点时，它的父结点保证不满，不必回头。

• 根满时，先新建一个空根 \(s\)，把旧根作为 \(s\) 的唯一孩子，再分裂它。分裂根是 B 树长高的唯一途径，所以 B 树是在顶部长高，而不是像 BST 那样在底部长高。
• 分裂一次 CPU \(\Theta(t)\)、\(O(1)\) 次磁盘操作；整个插入 \(O(h)\) 次磁盘访问、\(O(t\log_t n)\) CPU 时间。插入过程是尾递归，可以写成循环，任一时刻主存里只需常数个页。

原书图 18.7（\(t=3\)，结点至多 5 个关键字）完整演示了一串插入：初始根为 G M P X。插入 B 直接进叶子；插入 Q 时叶子 R S T U V 已满，分裂出 T 上移，根变成 G M P T X；插入 L 时根 G M P T X 已满，立即分裂，P 成为新根、树高加一；插入 F 时叶子 A B C D E 满，分裂出 C 上移，F 进入右半 D E。

18.2.6 删除：保证下降的结点"有余量"

删除可以发生在任意结点，不只是叶子；还要防止结点关键字数低于 \(t-1\)。原书的设计与插入对称：递归下降到结点 \(x\) 时，保证 \(x\) 至少有 \(t\) 个关键字（比下限多 1），于是从它的子树里删掉一个也不会违规。若根变成没有关键字的内部结点，就删掉根，让唯一的孩子当新根——这是 B 树变矮的唯一途径。

书中给出过程描述（不是完整伪代码），分三种情形：

1. \(k\) 在叶子 \(x\) 中：直接删。
2. \(k\) 在内部结点 \(x\) 中：(2a) 若 \(k\) 前面的孩子 \(y\) 至少有 \(t\) 个关键字，用 \(k\) 在 \(y\) 子树中的前驱 \(k'\) 替换 \(k\)，再递归删 \(k'\)；(2b) 否则若后面的孩子 \(z\) 至少 \(t\) 个，对称地用后继替换；(2c) 若两者都只有 \(t-1\) 个，把 \(k\) 和 \(z\) 合并进 \(y\)（得到 \(2t-1\) 个关键字），再从 \(y\) 中递归删 \(k\)。
3. \(k\) 不在内部结点 \(x\) 中：找到必含 \(k\) 的孩子 \(x.c_i\)。若它只有 \(t-1\) 个关键字，先补足再下降：(3a) 若有相邻兄弟至少 \(t\) 个关键字，就从 \(x\) 下移一个关键字给 \(x.c_i\)，再从兄弟上移一个关键字到 \(x\)（相当于"借位"或旋转）；(3b) 若相邻兄弟也都只有 \(t-1\) 个，就把 \(x.c_i\) 与一个兄弟合并，并从 \(x\) 下移一个关键字作为合并结点的中位关键字。

大多数关键字在叶子中，所以实践中删除多发生在叶子，一次下行完成。总代价 \(O(h)\) 次磁盘操作、\(O(t\log_t n)\) CPU 时间。把这段描述写成完整伪代码（原书 18.3-2）是检验理解的最好练习。

18.2.7 两道思考题

• 18-1 辅存上的栈：每页 \(m\) 个字。只在内存里留一页时，在页边界来回 PUSH/POP 会让每次操作都触发 I/O；留两页并采用合适的换页策略，就能让每个操作的摊还磁盘访问降到 \(O(1/m)\)。这与上一章的滞后区间是同一个想法。
• 18-2 2-3-4 树的连接与分裂：在 \(O(1+|h'-h''|)\) 时间内把两棵树和一个分隔关键字连接成一棵；再用一串连接操作在 \(O(\lg n)\) 时间内把一棵树按关键字 \(k\) 分裂成两棵。

18.3 斐波那契堆

18.3.1 要解决什么问题

可合并堆（mergeable heap）支持 MAKE-HEAP、INSERT、MINIMUM、EXTRACT-MIN、UNION 五个操作；斐波那契堆还支持 DECREASE-KEY 和 DELETE。原书图 19.1 对比了它和二叉堆：

最重要的是 DECREASE-KEY 摊还 \(O(1)\)。Prim 最小生成树（本册第 23 章）和 Dijkstra 最短路径对每条边可能调用一次 DECREASE-KEY，用二叉堆总共是 \(O(E\lg V)\)，用斐波那契堆变成 \(O(E+V\lg V)\)，在稠密图上是实质改进。

注意两点。第一，表中斐波那契堆的界是摊还界，单次 EXTRACT-MIN 可能很慢。第二，二叉堆和斐波那契堆都不支持高效 SEARCH，DECREASE-KEY 和 DELETE 需要直接拿到指向元素的指针。工程上常在堆元素与应用对象之间互存句柄（handle），也就是所谓"带索引的堆"（indexed heap）。

18.3.2 结构

斐波那契堆是一组最小堆有序（每个结点的关键字不小于父结点）的有根树：

• 每个结点有父指针 p、指向任意一个孩子的 child、度数 degree（孩子数），以及布尔标记 mark。
• 兄弟之间用环形双向链表相连，可以 \(O(1)\) 插删任意结点，也可以 \(O(1)\) 把两个链表拼接起来。
• 所有树根也连成一个环形双向链表，叫根表（root list）；H.min 指向关键字最小的根；H.n 为结点总数。

势函数：记 \(t(H)\) 为根表中的树数，\(m(H)\) 为被标记的结点数，

原书图 19.2 的堆有 5 棵树、3 个标记结点，势能为 \(5+2\times3=11\)。

18.3.3 懒惰：能推迟的工作都推迟

• INSERT：新结点自成一棵树挂到根表，必要时更新 H.min。实际 \(O(1)\)，势能增 1，摊还 \(O(1)\)。
• UNION：把两个根表拼接，取两者 min 的较小者。势能不变，摊还 \(O(1)\)。
• EXTRACT-MIN：推迟的工作在这里集中完成。把最小结点 \(z\) 的孩子全部挂到根表，删掉 \(z\)，然后调用 CONSOLIDATE 合并根表：反复找两个度数相同的根，把关键字较大的那个链接（link）为另一个的孩子，直到根表中各根度数互不相同。用一个按度数索引的辅助数组 \(A[0..D(n)]\) 记录"度数为 \(i\) 的根"，扫描一遍根表即可完成。

EXTRACT-MIN 的摊还分析：实际代价 \(O(D(n)+t(H))\)，其中 \(D(n)\) 是 \(n\) 结点堆的最大度数；合并后至多 \(D(n)+1\) 个根，势能从 \(t(H)+2m(H)\) 降到至多 \(D(n)+1+2m(H)\)。两者相加，\(t(H)\) 项被势能下降抵掉，摊还代价为 \(O(D(n))\)。直观上，每次链接的代价由"根数减 1"带来的势能下降支付。

18.3.4 DECREASE-KEY 与级联切断

把结点 \(x\) 的关键字减小后，若它比父亲 \(y\) 还小，就违反了堆序。处理方法是：把 \(x\) 切下（CUT）成为新根，然后对 \(y\) 执行级联切断（CASCADING-CUT）：

• 若 \(y\) 是根，停止；
• 若 \(y\) 未被标记，给它打上标记后停止（表示"它自成为孩子以来已失去一个孩子"）；
• 若 \(y\) 已被标记（这是它失去的第二个孩子），把 \(y\) 也切下成为根、清除标记，再对 \(y\) 的父亲递归。

原书图 19.5 演示了把 35 减为 5：5 成为根；其父 26 已标记，被切下；26 的父 24 也已标记，也被切下；24 的父 7 是根，级联停止。

设一次 DECREASE-KEY 引起 \(c\) 次 CASCADING-CUT 调用，实际代价 \(O(c)\)。之后树数为 \(t(H)+c\)，标记数至多 \(m(H)-c+2\)，

摊还代价 \(O(c)+4-c=O(1)\)。标记项的系数取 2 正是为此：切下一个已标记结点时势能降 2，1 个单位付切断的工作，另 1 个单位抵消它成为新根带来的势能加 1。

DELETE 就是先 DECREASE-KEY 到 \(-\infty\) 再 EXTRACT-MIN，摊还 \(O(\lg n)\)。

18.3.5 名字的由来：最大度数是 \(O(\lg n)\)

还差最后一块：证明 \(D(n)=O(\lg n)\)。关键是"失去两个孩子就被切下"这条规则保证了子树不会太"瘦"。

• 引理 19.1：设结点 \(x\) 的度数为 \(k\)，孩子按链接到 \(x\) 的先后为 \(y_1,\dots,y_k\)，则 \(y_i.degree\ge i-2\)（\(i\ge2\)）。因为 \(y_i\) 被链接时 \(x\) 已有至少 \(i-1\) 个孩子，而 CONSOLIDATE 只链接度数相同的根；之后 \(y_i\) 至多失去一个孩子。
• 引理 19.4：度数为 \(k\) 的结点，其子树大小 \(\mathrm{size}(x)\ge F_{k+2}\ge\phi^k\)，其中 \(F_k\) 是斐波那契数，\(\phi=(1+\sqrt5)/2\approx1.618\)。证明用到 \(F_{k+2}=1+\sum_{i=0}^{k}F_i\) 和 \(F_{k+2}\ge\phi^k\)（由 \(\phi^2=\phi+1\) 归纳）。
• 推论 19.5：\(n\ge\phi^k\)，所以 \(D(n)\le\lfloor\log_\phi n\rfloor=O(\lg n)\)。

注意：这只限制了度数，不限制树高。可以构造一串操作让堆变成一条 \(n\) 个结点的链（原书 19.4-1）。

18.3.6 理论与实践

原书明确说，斐波那契堆主要具有理论意义：常数因子大、实现复杂，实际中通常不如二叉堆、\(d\) 叉堆或配对堆（pairing heap）。工程上的典型做法是用二叉堆加懒惰删除：需要"减小关键字"时不去修改堆中的旧条目，而是直接压入一个新条目，弹出时跳过已过期的条目。Python 的 heapq 没有 DECREASE-KEY，基本都这样用（本册第 23 章的 Prim 实现就是这样）。

原书思考题 19-2 介绍的二项堆（binomial heap）是斐波那契堆的前身：一组二项树，每种度数至多一棵，对应 \(n\) 的二进制表示；所有操作最坏 \(O(\lg n)\)。

18.4 van Emde Boas 树

18.4.1 突破 \(\Omega(\lg n)\)

在比较模型中，INSERT 和 EXTRACT-MIN 不可能都是 \(o(\lg n)\)，否则就能 \(o(n\lg n)\) 排序。但计数排序告诉我们，关键字是有界整数时可以绕过这个下界。van Emde Boas 树（vEB 树）假设关键字是全域 \(\{0,1,\dots,u-1\}\) 中互不相同的整数（\(u=2^k\)），对 MEMBER、INSERT、DELETE、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR 都做到最坏 \(O(\lg\lg u)\)。

18.4.2 从位向量到常数高度树

原书 20.1 节的铺垫值得细看，因为工程实现往往就停在这一步。

• 位向量：\(A[x]=1\) 当且仅当 \(x\) 在集合中。插删查 \(O(1)\)，但最小值、后继要扫描，最坏 \(\Theta(u)\)。
• 叠加二叉树：在位向量上叠一棵二叉树，每个内部结点存两个孩子的"或"。最小值从根往下沿最左的 1 走；后继从叶子往上直到能向右拐，再往下找最小。所有操作 \(O(\lg u)\)。
• 叠加常数高度的树：设 \(u=2^{2k}\)，把位向量切成 \(\sqrt u\) 个簇（cluster），每簇 \(\sqrt u\) 位，再加一个 \(\sqrt u\) 位的 summary，\(summary[i]=1\) 当且仅当第 \(i\) 簇非空。求后继：先在本簇内向右找，找不到就在 summary 里找下一个非空簇，再在那个簇里找最左的 1。每个操作 \(O(\sqrt u)\)。

最后一种看似倒退，但"度为 \(\sqrt u\) 的树 + summary"正是 vEB 树的核心结构。

18.4.3 递归与 \(O(\lg\lg u)\)

把"按 \(\sqrt u\) 分簇"递归下去：全域 \(u\) 的结构由 \(\sqrt u\) 个全域 \(\sqrt u\) 的子结构加一个全域 \(\sqrt u\) 的 summary 组成。把 \(x\) 看作 \(\lg u\) 位二进制数，高半为簇号、低半为簇内偏移：

目标递推式是

令 \(m=\lg u\)、\(S(m)=T(2^m)\)，得 \(S(m)=S(m/2)+O(1)\)，所以 \(S(m)=O(\lg m)\)，即 \(T(u)=O(\lg\lg u)\)。另一种理解：全域的位数每层减半，从 \(\lg u\) 位减到 1 位需要 \(\lg\lg u\) 层。设计原则是：每层只花常数时间，且只递归进入一个子结构。

原书 20.2 节先构造的 proto-vEB 做不到这一点：求最小值要先递归 summary 找第一个非空簇、再递归该簇，两次递归使 \(T(u)=2T(\sqrt u)+O(1)=\Theta(\lg u)\)；后继更糟，为 \(\Theta(\lg u\lg\lg u)\)。

真正的 vEB 树（20.3 节）多存两样东西：min 和 max，并约定 min 不存入任何簇。这带来四个好处：

1. MINIMUM、MAXIMUM 直接返回，\(O(1)\)；
2. 求后继时，只需比较 \(\mathrm{low}(x)\) 与本簇的 max，就知道后继在不在本簇，然后只递归一边（本簇或 summary）；
3. 能 \(O(1)\) 判断树中有 0 个、1 个还是至少 2 个元素；
4. 往空树插入、从单元素树删除只需改 min/max，\(O(1)\)。这会截断递归：INSERT 时若目标簇为空，需要递归 summary，但往空簇插入是 \(O(1)\)；DELETE 时若删完簇变空需要递归 summary，但那说明刚才在簇里的递归只删了唯一元素，是 \(O(1)\)。

于是所有操作满足 \(T(u)\le T(\sqrt[\uparrow]{u})+O(1)\)，最坏 \(O(\lg\lg u)\)。（\(u\) 是 2 的奇数次幂时，用上平方根 \(\sqrt[\uparrow]{u}=2^{\lceil(\lg u)/2\rceil}\) 个簇、每簇全域为下平方根 \(\sqrt[\downarrow]{u}=2^{\lfloor(\lg u)/2\rfloor}\)。）

18.4.4 代价与改进

vEB 树的空间是 \(O(u)\)，创建空树也要 \(O(u)\) 时间（思考题 20-1），使用前必须知道 \(u\)。思考题 20-1 的缩减空间 vEB 树用散列表只存非空簇，把空间降到 \(O(n)\)；思考题 20-2 的 y-fast trie 用"散列所有前缀 + 分组平衡树"同样做到 \(O(n)\) 空间。原书注记提到，Pătraşcu 与 Thorup 证明了 vEB 树对前驱查询是最优的。

18.5 量化实战

18.5.1 B+ 树与行情数据库的索引

几乎所有关系数据库（MySQL InnoDB、PostgreSQL）的索引都是 B+ 树。理解了 B 树，就能解释量化研究中天天碰到的几个现象：

• 联合索引的列顺序决定哪种查询快。索引按关键字的字典序排列。日线表若按 (代码, 日期) 建索引，同一只股票的所有日期在叶子中是连续的，"取某只股票一段时间的 K 线"只需一次定位加一段顺序扫描；但"取某一天全市场的截面"会散落在每只股票的区段里。按 (日期, 代码) 建索引则正好相反，适合截面因子计算。两种查询都多时，就建两个索引，或者像很多时序库那样按日期分区、分区内按代码排序。
• 范围查询快、随机写入慢。范围查询是"一次定位 + 顺序读叶子"；随机键写入会打到不同的叶子页，引起大量随机 I/O 和页分裂。行情这种按时间追加的数据，若主键以时间开头，写入总落在最右边的叶子上，几乎是顺序写。
• 装满率。随机顺序插入时，B 树结点平均约 69% 满（理论值约 \(\ln 2\)）；按序批量导入可以接近 100%。很多数据库提供"按排序批量重建索引"的命令，就是这个道理。
• 列式存储（Parquet 的行组与页、kdb+ 的分区）不是 B 树，但设计目标相同：让每次 I/O 读到的数据尽量都是要用的。

18.5.2 订单簿价位与分层位图

撮合引擎和行情重建程序都要维护"哪些价位上有挂单"，并频繁查询最优买价（MAXIMUM）、最优卖价（MINIMUM）、某价位之外的下一档（SUCCESSOR/PREDECESSOR）。价格是以最小变动价位（tick）为单位的有界整数，正好是 vEB 树的适用场景。

实际的高性能实现通常不做完整递归的 vEB 树，而是停在 18.4.2 的"常数高度树"：用 64 位字做簇，配合 CPU 的 ctz/clz（数尾零/数前导零）指令一次处理 64 位。三层 64 位字就能覆盖 \(64^3=262144\) 个价位，每个操作只碰 3 个字。这就是"度为 \(u^{1/k}\) 的树"（原书 20.1-4）取 \(u^{1/3}=64\) 的情形。

18.5.3 代码

下面的代码做三件事：(1) 用定理 18.1 算不同 \(t\) 下 10 亿条记录的 B 树高度，并解原书 18.2-7 的页大小选择问题；(2) 实现一个最小的 B 树（CLRS 单程插入，结点内用二分），模拟 800 只股票 × 1000 天的日线库，比较两种联合索引做同一范围查询要读多少个结点；(3) 实现三层位图的价位集合，并在 20 万次随机挂撤单中与有序列表的结果逐一核对。

import numpy as np, bisect, math, random

# ---------- 1. B 树高度：定理 18.1 与页大小选择（原书 18.2-7） ----------
n = 10**9
for t in [2, 50, 500, 1000]:
    print(f"t={t:5d}  高度上界 log_t((n+1)/2) = {math.log((n+1)/2, t):5.2f}")
print(f"二叉平衡树 lg n = {math.log2(n):.1f}")
a, b = 5e-3, 10e-6                     # 读一页: a + b*t 秒
ts = np.arange(2, 5000)
cost = (a + b*ts) / np.log(ts)        # 查找时间 ∝ (a+bt)·log_t n
print("使 (a+bt)/ln t 最小的 t ≈", ts[np.argmin(cost)])

# ---------- 2. 一个最小的 B 树（CLRS 单程插入）+ 磁盘读计数 ----------
class Node:
    __slots__ = ("keys", "vals", "child", "leaf")
    def __init__(self, leaf):
        self.keys, self.vals, self.child, self.leaf = [], [], [], leaf

class BTree:
    def __init__(self, t):
        self.t, self.root, self.reads = t, Node(True), 0
    def _split(self, x, i):                       # B-TREE-SPLIT-CHILD
        t, y = self.t, x.child[i]
        z = Node(y.leaf)
        z.keys, z.vals = y.keys[t:], y.vals[t:]
        if not y.leaf: z.child = y.child[t:]; y.child = y.child[:t]
        x.keys.insert(i, y.keys[t-1]); x.vals.insert(i, y.vals[t-1])
        x.child.insert(i+1, z)
        y.keys, y.vals = y.keys[:t-1], y.vals[:t-1]
    def insert(self, k, v):
        r = self.root
        if len(r.keys) == 2*self.t - 1:           # 根满：先分裂，树长高
            s = Node(False); s.child = [r]; self.root = s
            self._split(s, 0); r = s
        x = r
        while not x.leaf:                         # INSERT-NONFULL 的迭代版
            i = bisect.bisect_right(x.keys, k)
            if len(x.child[i].keys) == 2*self.t - 1:
                self._split(x, i)
                if k > x.keys[i]: i += 1
            x = x.child[i]
        i = bisect.bisect_right(x.keys, k)
        x.keys.insert(i, k); x.vals.insert(i, v)
    def range(self, lo, hi, x=None):              # 返回 lo <= key <= hi 的所有值
        x = x or self.root; self.reads += 1; out = []
        i = bisect.bisect_left(x.keys, lo)
        while True:
            if not x.leaf: out += self.range(lo, hi, x.child[i])
            if i < len(x.keys) and x.keys[i] <= hi:
                out.append(x.vals[i]); i += 1
            else: break
        return out
    def stats(self):
        h, x = 0, self.root
        while not x.leaf: x = x.child[0]; h += 1
        cnt = [0, 0]
        def walk(x):
            cnt[0] += 1; cnt[1] += len(x.keys)
            for c in x.child: walk(c)
        walk(self.root)
        return h, cnt[0], cnt[1] / cnt[0] / (2*self.t - 1)

# 模拟日线库：800 只股票 × 1000 个交易日，键为 (股票代码, 日期)
random.seed(18)
rows = [(s, d) for s in range(800) for d in range(1000)]
random.shuffle(rows)                              # 写入顺序随意
bt = BTree(t=64)
for s, d in rows: bt.insert((s, d), (s, d))
h, nodes, fill = bt.stats()
print(f"80 万条记录, t=64: 高度={h}, 结点数={nodes}, 平均装满率={fill:.2f}")

bt.reads = 0
res = bt.range((123, 200), (123, 459))            # 单只股票一段时间的 K 线
print("按(代码,日期)索引查一只股票 260 天: 返回", len(res), "条, 读结点", bt.reads, "个")

bt2 = BTree(t=64)
for s, d in rows: bt2.insert((d, s), (s, d))      # 换成 (日期, 代码) 索引
bt2.reads = 0
res2 = [r for r in bt2.range((200, 0), (459, 10**9)) if r[0] == 123]
print("按(日期,代码)索引做同一查询: 返回", len(res2), "条, 读结点", bt2.reads, "个")

# ---------- 3. 订单簿价位的分层位图（vEB 的"常数高度树"思想） ----------
class Bitmap3:
    """全域 u = 64^3 = 262144 个价位（tick）。三层 64 位字：
       L0[w] 的第 b 位 = 价位 64w+b 有挂单；L1、L2 是逐层的 summary。"""
    def __init__(self):
        self.L0 = [0]*4096; self.L1 = [0]*64; self.L2 = 0
    def insert(self, x):
        self.L0[x >> 6] |= 1 << (x & 63)
        self.L1[x >> 12] |= 1 << ((x >> 6) & 63)
        self.L2 |= 1 << (x >> 12)
    def delete(self, x):
        w = x >> 6
        self.L0[w] &= ~(1 << (x & 63))
        if self.L0[w] == 0:
            self.L1[w >> 6] &= ~(1 << (w & 63))
            if self.L1[w >> 6] == 0: self.L2 &= ~(1 << (w >> 6))
    @staticmethod
    def lsb(v): return (v & -v).bit_length() - 1      # 最低位 1 的位置（ctz）
    def minimum(self):
        if not self.L2: return None
        i = self.lsb(self.L2); j = self.lsb(self.L1[i]); w = (i << 6) | j
        return (w << 6) | self.lsb(self.L0[w])
    def maximum(self):
        if not self.L2: return None
        i = self.L2.bit_length()-1; j = self.L1[i].bit_length()-1; w = (i << 6) | j
        return (w << 6) | (self.L0[w].bit_length()-1)
    def successor(self, x):                             # 严格大于 x 的最小价位
        w, b = x >> 6, x & 63
        m = self.L0[w] >> (b+1) << (b+1)                 # 本字内更高的位
        if m: return (w << 6) | self.lsb(m)
        i, j = w >> 6, w & 63
        m = self.L1[i] >> (j+1) << (j+1)                 # 同一 L1 字内下一个非空字
        if not m:
            m2 = self.L2 >> (i+1) << (i+1)               # 下一个非空 L1 字
            if not m2: return None
            i = self.lsb(m2); m = self.L1[i]
        w = (i << 6) | self.lsb(m)
        return (w << 6) | self.lsb(self.L0[w])

# 随机挂单/撤单，与有序列表的暴力结果核对
random.seed(20)
bm, ref = Bitmap3(), []
for step in range(200_000):
    p = random.randrange(100_000, 101_000)               # 价位集中在 1000 个 tick 内
    if p in ref and random.random() < 0.5:
        bm.delete(p); ref.remove(p)
    elif p not in ref:
        bm.insert(p); bisect.insort(ref, p)
    if step % 997 == 0 and ref:
        q = random.randrange(99_990, 101_010)
        k = bisect.bisect_right(ref, q)
        assert bm.successor(q) == (ref[k] if k < len(ref) else None)
        assert bm.minimum() == ref[0] and bm.maximum() == ref[-1]
print("分层位图与有序列表结果一致；当前价位数", len(ref),
      "最低价位", bm.minimum(), "最高价位", bm.maximum(),
      "100500 之后的下一个价位", bm.successor(100500))

运行输出：

t=    2  高度上界 log_t((n+1)/2) = 28.90
t=   50  高度上界 log_t((n+1)/2) =  5.12
t=  500  高度上界 log_t((n+1)/2) =  3.22
t= 1000  高度上界 log_t((n+1)/2) =  2.90
二叉平衡树 lg n = 29.9
使 (a+bt)/ln t 最小的 t ≈ 129
80 万条记录, t=64: 高度=2, 结点数=9117, 平均装满率=0.69
按(代码,日期)索引查一只股票 260 天: 返回 260 条, 读结点 7 个
按(日期,代码)索引做同一查询: 返回 260 条, 读结点 2426 个
分层位图与有序列表结果一致；当前价位数 678 最低价位 100000 最高价位 100998 100500 之后的下一个价位 100501

几点解读：

• 10 亿条记录，\(t=1000\) 的 B 树高度不超过 2（查找最多访问 3 个结点，根常驻内存时只读 2 次盘），而二叉平衡树约 30 层。按每次随机读盘 5 ms 算，这是十几毫秒与一百多毫秒的差别。
• 18.2-7 的页大小问题：读一页需要 \(a+bt\)，查找要读 \(\log_t n\) 页，总时间正比于 \((a+bt)/\ln t\)。在 \(a=5\) ms、\(b=10\,\mu\)s 时最优 \(t\) 约为 129。\(a\) 是定位开销，\(b\) 是每多读一个关键字的传输开销：定位越贵，页就该越大。
• 80 万条记录随机插入后高度只有 2，平均装满率 0.69，与随机插入的理论值约 \(\ln2\) 吻合。
• 同一个"取股票 123 的第 200–459 天"，用 (代码, 日期) 索引只读 7 个结点；用 (日期, 代码) 索引要读 2426 个——因为这只股票的记录分散在 260 个日期区段里，几乎每个叶子都要碰。这就是"联合索引最左列"规则的来源。
• 分层位图每次查询只访问 3 个 64 位字，与有序列表的暴力结果在全部抽检点上一致。用 C/C++ 实现时，lsb 对应一条 ctz 指令。

本章小结

B 树为外存设计：一个结点就是一页，最小度数 \(t\) 决定每个结点 \(t-1\) 到 \(2t-1\) 个关键字，所有叶子等深，高度 \(h\le\log_t\frac{n+1}{2}\)，查找、插入、删除都是 \(O(\log_t n)\) 次磁盘访问；插入"遇满先分裂"、删除"保证下降结点至少 \(t\) 个关键字"，都只需一趟下行；数据库索引普遍用其变体 B+ 树。斐波那契堆靠懒惰合并和级联切断，使 INSERT、UNION、DECREASE-KEY 摊还 \(O(1)\)、EXTRACT-MIN 摊还 \(O(\lg n)\)，是 Prim 和 Dijkstra 理论最优界的来源，但实践中常被二叉堆加懒惰删除取代。vEB 树在整数全域上按 \(\sqrt u\) 递归分簇，靠存 min/max 让每层只递归一次，各操作最坏 \(O(\lg\lg u)\)；工程中常见的分层位图就是它的"常数高度"版本。

练习

基础

1. 证明高度为 \(h\) 的 B 树最多存 \((2t)^{h+1}-1\) 个关键字。（原书 18.1-4。提示：每个结点都满，各层结点数为 \((2t)^i\)。）
2. 把 F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E 依次插入 \(t=2\) 的空 B 树，画出每次分裂前后的形态和最终形态。（原书 18.2-1。）
3. 为什么不允许 \(t=1\)？（原书 18.1-1。提示：非根结点可以没有关键字，分支失去意义。）
4. 在一个斐波那契堆中依次插入 1 到 8，然后执行一次 EXTRACT-MIN。画出 CONSOLIDATE 之后的根表。之后再把某个叶子的关键字减到 0，画出结果。（参考原书 19.2-1。）
5. 解释为什么斐波那契堆中会出现被标记的根，以及这为什么不影响分析。（原书 19.3-1。）

进阶

6. 写出 B-TREE-DELETE 的完整伪代码，并用本章的 Python B 树实现它，随机插删 10 万次后检查 B 树性质。（原书 18.3-2。）
7. 构造一串斐波那契堆操作，使堆最终只含一棵 \(n\) 个结点的线性链，从而说明树高不是 \(O(\lg n)\)。（原书 19.4-1。）
8. 若把级联切断的规则改为"失去第 \(k\) 个孩子才切"，\(k\) 为常数，是否仍有 \(D(n)=O(\lg n)\)？（原书 19.4-2。）
9. 把 vEB 树改成每层 \(u^{1/k}\) 个簇、每簇全域 \(u^{1-1/k}\)，各操作的时间是多少？结合 18.5.3 的三层位图，讨论层数与每层宽度的取舍。（原书 20.1-4、20.3-5。）
10. vEB 树创建需要 \(O(u)\) 时间。至少要执行多少次操作，才能让包括创建在内的摊还时间为 \(O(\lg\lg u)\)？（原书 20.3-6。提示：\(\Omega(u/\lg\lg u)\)。）

原书推荐习题：18.1-4、18.1-5、18.2-1、18.2-3、18.2-6、18.2-7、18.3-2，思考题 18-1；19.2-1、19.3-1、19.3-2、19.4-1、19.4-2，思考题 19-2；20.1-4、20.2-2、20.2-3、20.3-4、20.3-6，思考题 20-1、20-2。

原书对照