Skip to content

0013.md

Latest commit

 

History

History
221 lines (144 loc) · 5.41 KB

0013.md

File metadata and controls

221 lines (144 loc) · 5.41 KB

面试题：LSM-Tree 和 B+ Tree 的本质区别是什么？

一句话总结：

B+ Tree = 面向读优化的“磁盘随机读友好型”索引结构。 LSM-Tree = 面向写优化的“磁盘顺序写友好型”日志结构合并树。

它们最核心的哲学差异是：

  • B+ Tree： 减少磁盘随机 IO（适合读多写少）

  • LSM-Tree： 减少写放大、变随机写为顺序写（适合写多读少、写吞吐大）

下面从结构、写入路径、查询路径、磁盘布局、适配场景等维度做深度拆解。

一、核心设计目标完全不同（本质区别）

项 B+ Tree LSM-Tree
设计初衷 快速查找，减少磁盘随机 IO 提高写入吞吐，顺序写替代随机写
适配介质 HDD（机械盘随机读慢） HDD / SSD（顺序写极快）
推荐场景 MySQL (OLTP)、KV 读多场景 RocksDB、LevelDB、高写入量 KV 系统

核心区别：

B+ Tree：重点优化“读”，代价是“写成本高（随机 IO）”。 LSM-Tree：重点优化“写”，代价是“读放大、空间放大、合并成本”。

二、存储结构完全不同

1. B+ Tree：平衡树（多叉树）

  • 每个节点存 key（有序）、子节点指针
  • 数据节点按叶子链表顺序排列
  • 查找为 O(log N)
  • 插入删除需要在树上随机读写磁盘页

其核心是：

节点页在磁盘中随机散布，“一次 IO = 读一个页” → 随机 IO 很多。

2. LSM-Tree：二段结构（内存 + 多层 SSTable）

  • 写操作先写 WAL（顺序写）
  • 再写 MemTable（跳表 / 红黑树）
  • 内存满后 flush 成 SSTable（顺序写、不可修改）
  • 后台 compaction 合并 SST 层级

核心是：

所有写都是顺序写，没有随机写。

LSM 是典型的“写优先”结构。

三、写路径区别（写放大 vs 随机写）

B+ Tree 写入

写一次需要：

  1. 找到目标页（随机 IO）
  2. 在页内插入/更新 key（页内移动数据）
  3. 若页满，分裂（多次随机 IO）

代价：

  • 随机写 IO 非常贵（尤其机械盘）
  • 写放大高（一次写可能变成多次页分裂）

LSM 写入

写一次：

  1. 写 WAL（顺序 IO）
  2. 写 MemTable（内存）
  3. MemTable 满 → Flush 成 SST（大块顺序写）
  4. 后台 Compaction（顺序读+写）

代价：

  • 写清晰可控
  • 磁盘只做顺序写，吞吐极高

难点：

Compaction 会产生写放大，严重时写放大可达几倍甚至十几倍。

总结：

  • B+ Tree 写 = 随机写
  • LSM 写 = 顺序写

四、读路径区别（读放大 vs 一次命中）

B+ Tree 读：

Root → Child → Leaf → Data
  • logN 次随机读
  • 不需要扫描多个文件
  • 查询快、稳定

LSM 读：

读的时候需要查多个层级：

MemTable → Immutable MemTable → Level0 → Level1 → Level2 ...

因此会出现：

  • 读放大（Read Amplification）
  • 若无 Bloom Filter，可能多个 SST 都要查

为减少读放大，LSM 引入：

  • Bloom Filter
  • Block Cache
  • Key index/cache
  • 更复杂的 compaction 策略

所以：

LSM = 写快但读慢 B+Tree = 写慢但读稳定

五、空间放大对比

B+ Tree

  • 节点分裂导致额外空间
  • 但总体空间放大不大（常见 < 2）

LSM

  • 多层 SST 同时存在
  • Compaction 前旧文件和新文件并存
  • 删除、更新要等 compaction 回收

LSM 空间放大显著：

RocksDB 典型空间放大：1.5～3倍

六、延迟稳定性对比（P99/P999 重要指标）

B+ Tree 延迟稳定

读写都是直接访问页，不依赖后台任务：

  • 延迟稳定
  • P99/P999 平滑
  • MySQL 适合强一致性要求的 OLTP

LSM 延迟抖动明显

Compaction 会导致：

  • 磁盘 IO 飙升
  • 用户读写延迟陡升
  • Worst Case 极端抖动

所以 TiKV/RocksDB 方案需要非常多的资源隔离。

七、业务场景适配对比（关键）

场景 推荐结构 原因
即时读多写少（OLTP） B+ Tree 读稳定、低延迟、随机写少
写多读少、吞吐极大 LSM 写吞吐强、顺序写优秀
SSD 集群、大规模 KV LSM SSD 特性决定顺序写更快
金融、电商事务 B+ Tree P99 延迟更稳定、读取更快
日志、监控、时序数据 LSM 写多、批量写、压缩好

八、面试可背总结

你可以这样回答面试官：

“B+ Tree 和 LSM-Tree 的本质区别在于它们的设计哲学完全不同：

B+ Tree 是面向读优化的结构，通过减少随机读实现稳定的读性能； LSM-Tree 是面向写优化的结构，通过顺序写与分层 SSTable 来获得高写入吞吐。

在写路径上：

  • B+ Tree 需要随机 IO、页分裂，写放大高
  • LSM 只做顺序写，写非常快

在读路径上：

  • B+ Tree 读一次命中，延迟稳定
  • LSM 要查多个层级，读放大明显

代价方面：

  • B+ Tree 空间放大低
  • LSM 空间放大高，还会引入 compaction 导致延迟抖动

B+ Tree 更适合读多写少、低延迟的 OLTP 场景（如 MySQL）， LSM 更适合写密集型、高吞吐的 KV 系统（如 RocksDB、LevelDB、TiKV）。”
⚡