Buffer Tree

外存访问的昂贵单位是一整块，而不是一次比较。Buffer Tree 故意推迟单条操作，让同一路径方向上的请求先凑成能填满许多块的批次，再顺序下推；延迟换来的不是更短的树高，而是让一次 I/O 同时为大量操作服务。

批量插入例子 ​

日志索引连续收到数百万条插入。逐条 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 也属于总批处理成本。

Buffer Tree 把一批更新攒满后向下刷新，单次 flush 很贵；摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。按每个元素穿过的树层收费，证明总 I/O 而非每次操作的即时 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，树高为

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

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