space-amplification 标签归档 | 土法炼钢

B+tree 与 LSM-tree：原地更新与异地更新的读、写、空间代价

2026-04-19 | algorithms · database | #b-plus-tree #lsm-tree #write-amplification #space-amplification #rum-conjecture #leveldb #rocksdb #innodb #bloom-filter

从 O'Neil 1996 与 Dostoevsky 的代价模型推导两类结构的读写空间放大，用计数模拟器在同一负载上实测：B+tree 写放大随缓冲池从 126 降到 8.6，leveled LSM 为 14.4，并对照 RUM 猜想原文与生产数据。

【存储工程】LSM-Tree 工程调优：三种放大的权衡

2025-09-09 | storage | #lsm-tree #compaction #write-amplification #read-amplification #space-amplification #bloom-filter

LSM-Tree 的核心设计是把随机写转换为顺序写，但这个转换不是免费的。写入经过 MemTable 刷盘、再经过多次 Compaction 合并，每一字节的用户数据在磁盘上可能被反复读写数十次。读取一个 key 时，最坏情况下需要逐层搜索，直到命中或遍历全部层级。与此同时，旧版本数据和墓碑标记占用的额外空间，在 Co…