# 面试题：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）。”