LSM 树

工作原理

LSM 树的核心思想是：永远不做随机写，只做追加顺序写。新写入的数据首先进入内存中的可变结构（MemTable，通常是跳表），当 MemTable 达到阈值时，整体刷写为磁盘上的 SSTable（Sorted String Table）文件——这是顺序 IO，比随机写快一到两个数量级。

随着数据不断写入，磁盘上会积累越来越多的 SSTable 文件。后台压缩（Compaction）进程定期合并多个 SSTable，同时清除已被删除或覆盖的旧版本数据，保持文件数量可控。LevelDB 的分层压缩策略（Level 0 到 Level N 容量逐层扩大10倍）是最经典的实现。[1]

读写权衡

LSM 树的代价是读性能：查找一个键需要先查 MemTable，再按从新到旧的顺序查各层 SSTable，可能需要多次文件 IO。布隆过滤器（Bloom Filter）是标配优化——以少量内存代价，快速判断一个键在某个 SSTable 中肯定不存在，从而跳过不必要的文件读取。

RocksDB 是 Meta（Facebook）在 LevelDB 基础上深度优化的版本，加入了列族（Column Family）、压缩加速、并行压缩等特性，成为当今最广泛部署的 LSM 存储引擎，被 MySQL（MyRocks）、TiKV、CockroachDB 等多个系统选为底层存储层。