rum-conjecture 标签归档 | 土法炼钢

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-02 | storage | #storage-engine #heap-file #btree #lsm-tree #rum-conjecture #write-amplification

数据库系统的架构可以划分为两大层：上层的查询处理层负责解析 SQL、生成执行计划、优化查询；下层的存储引擎（Storage Engine）负责把数据持久化到磁盘，并在需要时高效地把数据取回来。查询处理层决定"做什么"，存储引擎决定"怎么存、怎么取"。同一个查询处理层可以对接不同的存储引擎——MySQL 的 InnoDB…