B+ 树和 LSM 树有什么区别？为什么写多场景常提 LSM？

简化版

B+ 树倾向于原地维护有序页，读和范围查询稳定，但随机写可能触发页分裂和随机 I/O。LSM 树把写入先追加到内存和顺序日志，再批量刷盘、后台 Compaction，写吞吐好，但读取可能查多层 SSTable，并带来读放大和写放大。

详细版

B+ 树和 LSM 都是存储引擎常见索引结构，但优化目标不同：

• B+ 树：维护一棵页式有序树，点查和范围查路径短，更新直接作用于目标页；
• LSM：写入先进入 MemTable 和 WAL，刷成不可变 SSTable，后台合并多层文件。

对比：

维度	B+ 树	LSM 树
写入	可能随机改页	追加写、批量刷盘
点查	一棵树路径	可能查 MemTable + 多层 SSTable
范围查	叶子链表顺序扫	多路归并多个文件
后台成本	相对少	Compaction 成本明显

写多场景常提 LSM，是因为它把随机写转成顺序写和批量合并，但并不是所有场景都比 B+ 树好。

完整版教学

一、两者解决的是同一个问题吗

B+ 树和 LSM 树都可以作为存储引擎的有序索引结构，用来支持按 key 查找和范围扫描。但它们面对磁盘的方式不同。B+ 树努力维护一棵随时有序、可直接查的页结构；LSM 树则接受数据分散在多个有序文件中，通过后台合并逐步整理。

所以它们不是简单谁淘汰谁，而是读写成本分配不同。B+ 树偏即时维护，LSM 偏延迟整理。

记忆钩子：B+ 树是边写边整理书架，LSM 是先把书放到收纳箱，晚上再批量归档。

二、B+ 树写入为什么可能贵

B+ 树插入要找到目标叶子页，然后把记录放进去。如果页满了，需要分裂页，并更新父节点。随机 key 会让写入分布在很多页上，导致随机 I/O、页分裂、缓存页频繁变脏。

例如随机插入 10000 条 UUID 主键，写入位置可能散落在大量叶子页；而自增主键大多写右侧末尾，局部性更好。B+ 树并不是不能写多，而是随机写模式会放大维护成本。

三、LSM 写入为什么吞吐高

LSM 写入通常先写 WAL 保证崩溃恢复，再写内存 MemTable。MemTable 满后刷成磁盘上的有序 SSTable 文件。这个过程主要是追加写和批量顺序写，避免每条写入都随机修改磁盘页。

write -> WAL append -> MemTable
MemTable full -> flush -> SSTable
background -> compaction -> larger SSTable

顺序写对磁盘和 SSD 都更友好，批量写还能摊薄排序和索引构建成本。

四、LSM 的读放大和写放大是什么

LSM 的代价来自多层文件。点查一个 key 时，可能要查 MemTable、Immutable MemTable、Level0 多个 SSTable，以及更低层文件。Bloom Filter 能减少无效查找，但不能完全消除复杂性。范围查询还可能需要多路归并多个有序文件。

写放大来自 Compaction：同一条数据可能在后台合并中被反复读写多次。删除也常通过 tombstone 标记，等 Compaction 才真正清理。

放大类型	B+ 树	LSM
读放大	路径较稳定	多层查找可能增加
写放大	页分裂、日志、脏页	Compaction 反复重写
空间放大	碎片和页填充	多版本和 tombstone

这三个放大是比较存储引擎时的高频词。

五、范围查询谁更强

B+ 树叶子页天然有序并通过链表连接，范围查询通常定位起点后顺序扫描。LSM 的每个 SSTable 内部有序，但同一范围的数据可能分布在多个层级和文件中，需要归并，还要处理新版本覆盖旧版本和 tombstone。

如果数据已经经过充分 Compaction，LSM 范围查询也可以不错；但在写入很猛、Level0 文件多时，范围查询压力会变大。B+ 树在传统关系型数据库的范围扫描和排序场景里非常稳定。

六、应该怎么选型

写多、吞吐优先、可接受后台 Compaction 抖动的场景，LSM 很有吸引力，例如日志型、时序型、KV 存储。读多、事务复杂、范围查询和低延迟稳定性要求高的场景，B+ 树仍然常见。

场景	更常见选择
关系型 OLTP 索引	B+ 树
写入吞吐很高的 KV	LSM
强范围扫描和排序	B+ 树常稳定
日志/时序追加写	LSM 常合适

实际系统会结合缓存、Bloom Filter、压缩、事务模型和硬件特性，不是只看索引结构。

七、常见误区与追问

• 误区：LSM 一定全面优于 B+ 树。 LSM 提升写吞吐，但会带来读放大、写放大和 Compaction 成本。
• 追问：B+ 树为什么怕随机写？ 随机写会修改分散页，触发页分裂和随机 I/O。
• 误区：LSM 不需要排序。 MemTable 和 SSTable 都要保持有序，只是排序批量化和层级化。
• 追问：Bloom Filter 在 LSM 中有什么用？ 快速判断某个 SSTable 大概率不含 key，减少无效读。
• 误区：B+ 树没有写放大。 日志、页分裂、脏页刷盘也会带来写放大，只是形式不同。

八、加强记忆

B+ 树和 LSM 的差别可以记成「即时维护 vs 延迟整理」。B+ 树每次写都努力维护页式有序结构，读路径稳定；LSM 先顺序写入，再后台 Compaction 整理，写吞吐强但读和后台成本更复杂。比较时一定带上读放大、写放大、空间放大，以及点查、范围查、写入吞吐这些维度。