深入浅出分析LSM树（日志结构合并树）
最新回答
最初的地方
2026-02-01 12:58:30
在调研NoSQL数据库时，发现RocksDB、LevelDB、HBase以及Prometheus等底层存储引擎都采用LSM树这一数据结构。为深入了解，决定撰写此篇。
LSM树设计于1996年，年仅35岁，比我还年轻。它采用“疯狂到不顾一切”的磁盘顺序写策略，提供无与伦比的写吞吐量。
插入操作简单，数据直接插入内存排序树中，不论数据是否已存在。插入复杂度为树高log(n)，性能优越。
删除操作通过墓碑标记表示，不直接删除数据，只在内存排序树中插入墓碑标记。操作复杂度同样为log(n)，效率高。
修改操作类似于删除，也是插入墓碑标记。修改操作复杂度为log(n)，不影响性能。
查询操作需要从内存至磁盘，逐层查找。查询复杂度较高，极端情况下需扫描整个库，性能受限。
合并操作是LSM树的核心，用于处理内存数据写入磁盘及磁盘文件归并。合并操作复杂度为O(n)，效率高。
LSM树优势在于写操作效率高，但读操作性能相对较弱，不擅长区间范围读取。归并操作消耗性能，需合理设置参数。
总结，LSM树设计原则侧重于写性能，牺牲部分读性能。适用于写吞吐量远大于读吞吐量的场景，广泛应用于NoSQL数据库。
热门标签
