Buffer Tree

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

批量插入例子 ​

日志索引连续收到数百万条插入。逐条 B-tree 查询会为每条记录访问一条根叶路径；buffer tree 先在根聚合，按键区间成批分给子树，让一次读入的块处理许多记录。同一键的插入与删除用时间戳保留先后顺序，随后按顺序合成为等价操作。

查询与边界 ​

即时点查询要检查根到叶路径上尚未下推的相关缓冲，并按时间合成同键操作；批量 search 则可随更新一起下推，延迟返回结果。批处理减少的是长期平均 I/O，单次查询或触发 flush 的更新仍可能承担较大开销。

操作排序与正确性 ​

同一键的更新可能同时位于祖先和后代缓冲。下推时应按时间戳稳定排序，或先按键分组，在相邻查询之间折叠成等价更新，确保较晚 delete 不被较早 insert 覆盖。批量 search 可作为带时间戳操作一路下推，在叶与此前更新合并后输出；合并更新时必须保留每个查询时刻的答案，不能只保存整段最后的净状态。

I/O 模型不计已经驻留内存的数据之间的比较成本；缓冲容量因而要与可用内存相匹配。若批处理结束时要把待办请求全部落实到叶层，还需执行最终清空，并计入未满缓冲的读写成本。

Buffer Tree 适合大量更新和可延迟查询的外存任务。它把逐条根叶访问改成按键区间分发操作批次；树的平衡负责控制层数，缓冲负责让每层的块传输被多条操作分担。

同一缓冲思想还可用于外存优先队列：沿最左路径下推相关操作后，把一批最小元素集中到内存中，再连续回答删除最小值请求。不同接口的关键区别在于何时必须返回答案，这决定了哪些请求可以继续积累、哪些缓冲需要立即处理。