LSM树(日志结构合并树)是一种为提高写入性能而设计的存储数据结构。新写入的数据先累积在内存结构中,达到一定量后以有序的不可变文件形式顺序写入磁盘,后台任务再将这些文件分多个层级合并(compaction)为更大的文件。该结构由Patrick O'Neil等人在1996年发表的论文中提出。
由于它将随机写转换为顺序写,因此适合写密集型负载;读取需要查看多个层级的文件,通常借助布隆过滤器和索引加速。Google的Bigtable和LevelDB、Meta的RocksDB、Apache Cassandra等众多数据库和键值存储都采用了这种结构。