Bε 树导论：把写入优化做进 B 树

📋 概述

Usenix ;login: 2015 年 10 月号的经典综述，作者包括 Michael Bender、Martin Farach-Colton 等。Bε 树是 B 树的变体：每个内部节点留出一块写在磁盘上的缓冲区存消息，插入编码成 insert message、删除编码成 tombstone message，缓冲区满了就整批下推，从而不必为每个小写入满盘寻道；ε 在 0 到 1 之间决定节点空间如何分给枢轴（约 B 的 ε 次方）和缓冲（约 B 减去 B 的 ε 次方）。文中给出与 B 树、LSM 树的渐近 I/O 对比，并介绍 upsert：更新不必先读旧值，把回调与增量塞进消息即可。TokuDB 与 BetrFS 都是它的工业实现。