Buffer Tree

结构 ​

在参数为 $(M,B)$ 的外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。中，取扇出 $\mathrm{\Theta }(M/B)$ 的多路树。每个内部节点除分隔键外还维护可容纳 $\mathrm{\Theta }(M)$ 条操作的缓冲；新 insert/delete/search 请求先写入根缓冲，不立即沿路径执行。叶保存键或最终操作结果。

Flush 不变量 ​

缓冲满时，把其中 $\mathrm{\Theta }(M)$ 条操作按目标孩子分组，并以顺序块写入各孩子缓冲；一次 flush 读写 $O(M/B)$ 块，平均每条操作 $O(1/B)$ I/O。每条操作向下经过

$$O({\log }_{M/B}(N/B))$$

层，所以批量操作的摊还 I/O 为 $O((1/B){\log }_{M/B}(N/B))$，总量达到 Sort 级别。结束前必须 drain 所有缓冲，未下推操作仍是逻辑状态的一部分。

批量插入例子 ​

日志索引连续收到数百万条插入。逐条 B-tree 查询会为每条记录访问一条根叶路径；buffer tree 先在根聚合，按键区间成批分给子树，让一次读入的块处理许多记录。重复键的 insert/delete 顺序需在缓冲内保留时间戳，不能简单相消后改变语义。

查询与边界 ​

单个 point query 可能要检查根到叶路径上尚未 flush 的所有缓冲，延迟并非普通 B-tree 的简单 $O({\log }_{B}N)$。结构优化的是 batched/摊还 I/O，不是数据库 buffer pool，也不保证每次更新最坏便宜。缓冲容量、扇出和内存内分组算法必须共同满足 $M$ 约束；flush 若对每个孩子随机写小片段，会丢失块效率。

操作排序与正确性 ​

同一键的更新可能同时位于祖先和后代缓冲。下推时应按时间戳稳定排序，或先按键分组再折叠成等价净操作，确保较晚 delete 不被较早 insert 覆盖。批量 search 可作为带时间戳操作一路下推，在叶与此前更新合并后输出。

一次 flush 的内存内排序是否免费取决于 I/O 模型：CPU 免费但 $\mathrm{\Theta }(M)$ 项必须已在内存；若缓冲超过 $M$ 就不能一次分组。最终报告结果前 drain 的 I/O 也属于总批处理成本。

一次 flush 的操作次序 ​

根缓冲满时，先按目标孩子对操作稳定分组；对同一键的多条操作再按时间排序，必要时合并 insert-delete 对或保留最后写。每组以连续 I/O 写入对应孩子缓冲，孩子溢出则递归 flush。先按键排序却丢掉时间序，会让较旧删除覆盖较新插入。

一次 flush 移动 $\mathrm{\Theta }(M)$ 条操作，向 $\mathrm{\Theta }(M/B)$ 个孩子各付常数块 I/O，总计 $\mathrm{\Theta }(M/B)$ 次。因此每条操作每下降一层摊到 $O(1/B)$ I/O，树高为

$$O({\log }_{M/B}\frac{N}{B}),$$

批量更新摊还为该高度除以 $B$。这个界依赖缓冲确实批满后再写；若每来一条就随机写子节点，批处理优势消失。

点查询要沿根到叶检查所有尚未下推的缓冲，并按时间合成同键操作，不能只查叶。Buffer Tree 因而主要优化批量吞吐，不保证单次查询或更新的低尾延迟。

参考资料

• Lars Arge, The Buffer Tree: A New Technique for Optimal I/O Algorithms, WADS, 1995.
• Jeffrey Vitter, External Memory Algorithms and Data Structures, ACM Computing Surveys, 2001.