LSM树(日志结构合并树)

LSM树(Log-Structured Merge-Tree,日志结构合并树)是一种为高吞吐写入优化的磁盘数据结构,由帕特里克·奥尼尔(Patrick O Neil)等人于1996年提出。它通过把随机写转化为顺序写来提升写入性能,广泛用于现代键值存储引擎。

概述

传统B树在磁盘上原地更新数据,写入时会产生大量随机磁盘寻址,写吞吐受限。LSM树采用分层设计:新写入的数据先追加到内存中的有序结构(通常称为内存表),同时记录预写日志保证持久性;当内存表写满后,整体作为一个不可变的有序文件顺序写入磁盘。磁盘上的文件被组织成多个层级,后台进程不断把小文件合并成大文件,清理重复和删除标记。

核心原理

• 内存表:新数据先写入内存中的有序缓冲,提供极快的写入速度。
• 不可变磁盘文件:内存表刷盘后成为只读的有序字符串表文件,顺序写入磁盘。
• 合并压实:后台将多个磁盘文件归并排序、合并成更大的文件,回收空间。
• 读取放大:查询可能需要检查内存表和多个层级的文件,常配合布隆过滤器加速。

应用场景

LSM树是众多NoSQL数据库和存储引擎的基石,广泛应用于宽列数据库、分布式键值存储和时序数据库中。凡是写入远多于读取、或需要承接海量顺序写入的系统,如日志存储、监控指标、消息持久化等,都倾向采用LSM树结构。许多嵌入式键值库也以LSM树为默认引擎。

常见问题

问:LSM树相比B树的取舍是什么?答:LSM树以写入性能见长,把随机写变为顺序写,写吞吐更高;代价是读取可能要查多个文件带来读放大,以及后台合并消耗磁盘带宽带来写放大。B树读取更直接但随机写较慢。选型取决于读写比例。

问:什么是LSM树的合并压实?答:随着数据不断刷盘,磁盘上会积累许多小文件,包含重复键和删除标记。合并压实是后台把这些文件归并排序、去除冗余、合并成更大文件的过程,用以控制文件数量、回收空间并维持读取效率。