一句话定义:LSM 树(Log-Structured Merge-Tree,日志结构合并树)是一种“先在内存里攒着、攒够再层层合并写入磁盘”的存储结构,它把零散的随机写转化为成批的顺序写,因此特别适合应付大量写入。
原理:像还书车,不像书架
图书馆还书时,管理员不会每还一本就跑回书架插进去,因为那是随机写,而磁盘最怕随机写。他先把书堆在还书车上(内存里的 MemTable,一种有序结构,常见实现是跳表),车满了就整车上架:按索书号排好,写成一份只读、有序的文件(SSTable,Sorted String Table)放到磁盘上。写满一车就再推一辆新的,磁盘上于是攒下一摞新旧不同的“车”。
为了防止断电丢数据,每次写入还会顺序追加一条日志(Write-Ahead Log,WAL),内存里的内容丢了可以重放。
麻烦在于这些只读文件会越攒越多,查一个键得从新到旧挨个找(读放大)。所以后台有个“整理工”做合并(Compaction):把几份 SSTable 归并排序、丢掉被覆盖和被删除的旧版本,写成更大的新文件,通常按层组织(leveled),越往下层文件越大越老。删除也不是真删,先写一个墓碑标记(tombstone),等合并时一并清掉。
和 B+ 树的区别
一句话:B+ 树“原地改”,LSM“只追加、事后合并”。
| B+ 树 | LSM 树 | |
|---|---|---|
| 写入方式 | 找到位置原地更新页面 | 只追加,先内存后合并 |
| 写放大 | 较小 | 合并反复重写,写放大明显 |
| 读放大 | 通常几次 IO | 可能要查多层文件 |
| 适合 | 读多写少、范围查询 | 写多读少、写入吞吐高 |
代价与实际意义
LSM 的“便宜”其实来自代价转移:写入时几乎不排序、不改老文件,代价被推给后台合并。Compaction 会持续占用磁盘带宽和 CPU,和前台读写抢 IO,表现为延迟毛刺;如果写入长期快过合并,积压会越堆越多,读也越来越慢。所以运维 LSM 系统,一半功夫在调合并策略、层数和每层大小,另一半在盯积压指标。
对从业者:写多读少的场景——日志采集、时序数据、消息与 KV 存储(RocksDB、Cassandra、HBase 这一支)、特征存储、向量库底层的键值索引——LSM 常是默认答案;读极重、要求稳定低延迟的在线事务场景,B+ 树往往更稳。选型时问三句:写是不是远多于读?能不能容忍偶发延迟抖动?有没有人盯合并?具体参数与默认值以官方文档为准。
