# 顺序写更快：LSM树为何没干掉B树 如果你写过任何带数据库的代码，大概率都干过同一件事：往一张表里加个 `WHERE id = ?` 的查询，然后顺手 `CREATE INDEX`。然后你发现查询变快了，写变慢了，于是心满意足地去写下一个功能。 但你有没有想过：那个索引，到底长什么样？为什么几乎所有的关系型数据库——MySQL、PostgreSQL、Oracle、SQL Server——的索引都是同一棵树？而另一边，撑起 Cassandra、HBase、RocksDB 这些写入怪兽的，又是另一棵完全不同的树？这两棵树，一个叫 **B-tree（准确说是 B+ tree）**，一个叫 **LSM-tree**。它们的分野，几乎是数据库世界里最重要的设计抉择，却被绝大多数应用层开发者当成"黑盒里的黑盒"。 2026 年 4 月，频道 **Priya Bansal** 发布了一条被反复转发的讲解视频——**《How Databases ACTUALLY Work (B-Trees vs LSM Trees, Explained)》**。它没有堆术语，而是用最直白的方式回答了一个被反复回避的问题：**数据库引擎真正的本事，从来不是"让一切变快"，而是"决定让哪一边变慢"。** 这一轮解读，我们就顺着这棵树往下挖，看清存储引擎背后那个残酷的"不可能三角"。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | How Databases ACTUALLY Work 😳 (B-Trees vs LSM Trees, Explained) | | 频道 | Priya Bansal（@priya_bnsl） | | 发布日期 | 2026 年 4 月 14 日（已核实） | | 时长 | 约 15 分钟量级（科普讲解型） | | 播放量 | 近期发布，持续增长中 | | 核心主题 | 数据库存储引擎两大主力数据结构：B+ 树 vs LSM 树的根本取舍 | ## 核心内容拆解 ### 一、索引不是 HashMap，是一棵被磁盘"压扁"的树 很多人第一次接触索引，脑子里浮现的是哈希表：给个 key，算个 hash，O(1) 拿到。这个直觉在**内存**里是对的，但数据库的数据在**磁盘**上，规则就被彻底改写了。 视频反复强调一个被忽视的事实：**磁盘的本质单位是"页"（page），不是"字节"。** 一次 I/O 读一个页（InnoDB 默认 16KB），无论你要这一页里的 1 个字节还是全部，代价几乎一样。所以最优的数据结构必须**把一页塞满尽可能多的索引信息**，让一次磁盘访问能排除掉尽可能多的搜索空间。 这正是 B-tree 被发明出来的理由。1970 年，Bayer 和 McCreight 提出 B-tree，1972 年正式发表在 *Acta Informatica* 上（论文名 *Organization and Maintenance of Large Ordered Indices*）。它的关键特征是**高扇出（high fanout）**：一个节点不是像二叉树那样只有 2 个孩子，而是可以有几百甚至上千个孩子。 > 延伸算一笔账：一个 16KB 的页，存 14 字节的键 + 6 字节的子指针，能塞下约 **800 多个键**。这意味着一棵只有 4 层的 B+ 树，理论上能索引 800⁴ ≈ **4×10¹¹（四千亿）** 条记录，而点查询只需要 **4 次磁盘访问**。这是任何平衡二叉树（需要 30+ 层）在磁盘上完全做不到的。 所以"为什么不用红黑树/AVL 树"——因为它们太"瘦高"了，每次比较就是一次潜在磁盘访问，10 亿条数据要访问 30 次。B+ 树是**为磁盘的访问粒度量身定做的矮胖树**。这是视频之外的背景，但它解释了一切后续设计。 ### 二、B+ 树的真正杀招：叶子链表与"原地更新" 视频中讲清楚了 B-tree 在数据库里的具体变体——**B+ 树**。它和教科书 B-tree 的关键区别有两个： 1. **所有真实数据只存在叶子节点**，内部节点只存"路由键"。这让内部节点更紧凑，扇出更高。 2. **所有叶子节点用双向链表串起来**。 第二个设计看似不起眼，却是 OLTP（在线事务处理）数据库的灵魂。`WHERE age BETWEEN 25 AND 35` 这种范围查询，先在树里定位到 25，然后**顺着叶子链表一路扫到 35**，全程顺序读，快得离谱。没有这条链表，范围查询就得反复回树，性能崩塌。 B+ 树的写操作是**就地更新（in-place update）**：找到目标叶子页 → 读进来 → 在内存里改 → 写回原来的磁盘位置。代价是**随机 I/O**——写到哪个物理位置完全取决于数据本身，磁盘得来回跳。 这里藏着 B+ 树的核心权衡：**它为读优化，为写付出随机 I/O 的代价。** 视频反复在这一点上停留——这也是后续 LSM 想要翻盘的突破口。 ### 三、LSM 树的颠覆：把"更新"彻底消灭掉 如果说 B+ 树的哲学是"找到位置，原地改"，那 LSM-tree 的哲学就是一句更激进的话——**根本没有"更新"这回事。** 视频清晰地还原了 LSM 的写入路径： - 写进来 → 先追加到 **WAL（Write-Ahead Log，预写日志）**，保证机器挂了数据不丢； - 同时写入内存里的 **MemTable**（通常用跳表 skip list 实现）； - MemTable 撑满（比如 4MB）→ 冻结成不可变的，**顺序刷盘**成一个 **SSTable**（Sorted String Table，已排序的磁盘文件），落到 Level 0； - 后台 **compaction（压实）** 线程不断把多个小 SSTable 合并、排序、去重，搬到更大的 Level 1、Level 2…… 注意整个过程**没有任何"找到旧位置去覆盖"的动作**。要更新某个 key？直接写一条新记录。旧的那条还躺在某个老的 SSTable 里，等着被 compaction 清理。要删除？写一个 **tombstone（墓碑标记）**，标记"这个 key 已死"，真正的物理删除依然要等 compaction。 > 我的延伸判断：**LSM-tree 的本质，是一个跑在后台的垃圾回收器。** 它把"写"做到极致——全部是顺序追加，磁盘最爱的访问模式。但代价是，"当前有效数据"散落在多层多个文件里，需要一个永不停歇的后台进程去收拾残局。这正是后面所有麻烦的根源。 ### 四、读放大的诅咒：为什么 LSM 不用就白写 LSM 写得爽，读起来却让人抓狂。视频点出了一个反直觉的现象：**一次点查询，可能要翻好几个文件。** 因为同一个 key 的新旧版本可能散布在 MemTable、Level 0 的多个 SSTable、以及更深层级里。一次 `get(key)` 要按"从新到旧"的顺序逐个查找，直到命中。这就是 **read amplification（读放大）**——逻辑上读 1 个值，物理上可能要读好几个磁盘块。 工业界的救命稻草是两个： - **Bloom filter（布隆过滤器）**：每个 SSTable 配一个，查询前先问一句"这个 key 大概率在不在这？"，不在就跳过，省掉一次真正的磁盘读。（顺带一提，这正是我们之前拆解过的"永不漏报只谎报"那个数据结构，在这里它撑起了 LSM 的读性能。） - **块缓存 / 表缓存（block cache / table cache）**：把热点 SSTable 的索引块和数据块常驻内存。 但即便如此，LSM 的点查询延迟通常仍**高于 B+ 树**——因为 B+ 树的查询路径是严格有界的 3-4 次 I/O，而且整条路径高度可缓存；LSM 则要面对"该查哪几层、命中率多少"这种不确定性。**SSD 让随机 I/O 变便宜了，但没让"读多个文件"变便宜。** ### 五、那个残酷的不可能三角：WAMP × RAMP × SAMP 这是整个视频、乃至整个存储引擎设计最该被记住的一页。视频把它讲成了三条互相打架的曲线： | 维度 | 含义 | B+ 树 | LSM 树 | |------|------|-------|--------| | **WAMP（写放大）** | 逻辑写 1 字节，物理要写多少 | 中等（WAL + 原地页写，约几倍） | **高**（compaction 反复重写，leveled 可达 10–50 倍） | | **RAMP（读放大）** | 逻辑读 1 次，物理要读多少 | **低**（树高有界，3-4 次） | 高（需扫多个 SSTable） | | **SAMP（空间放大）** | 存 1 份有效数据，实际占多少空间 | **低**（无重复，仅碎片 ~1.5 倍） | 较高（新旧版本共存 + compaction 期间的临时翻倍） | **没有任何数据结构能同时最小化这三者。** 你只能选一个要保住的、一个要牺牲的： - 选**读优先** → B+ 树（点查/范围扫描为主，事务型负载，OLTP）。 - 选**写优先** → LSM 树（海量写入、时间序列、日志型负载，Bigtable/Cassandra/HBase 这类）。 这正是我标题想说的那句反直觉的话：**LSM 写得明明更快，为什么没干掉 B 树？** 因为它在用"读慢一点、空间费一点、CPU 多烧一点（compaction）"去换那一份写速度。如果你的负载是读多写少的 OLTP，强行上 LSM 等于把最快的读路径换成最慢的——得不偿失。**没有免费的索引，只有被转嫁的成本。** ### 六、compaction：那个决定 LSM 生死的后台旋钮 视频把 compaction 作为独立重点来讲，这是对的——它是 LSM 性能里最不稳定的一环。 主流有两种压实策略： - **Leveled compaction（LevelDB/RocksDB 默认）**：每一层是全局有序的，同一 key 在每层至多出现一次。读放大低（每层最多查一个文件），但写放大高（数据要一层层重写上去）。 - **Size-tiered compaction（Cassandra 历史默认）**：把大小相近的 SSTable 一起合并。写放大低，但同一 key 可能在多个文件里都存在，读放大和空间放大都更高。 这个选择直接决定了"这台机器到底在读上还是写上更稳"。运维过 Cassandra 的人都知道 **compaction storm（压实风暴）**：写入高峰期 compaction 跟不上，SSTable 堆积，读延迟雪崩。这是 LSM 系统运维最难啃的骨头，也是 B+ 树系（如 Postgres）用户很少体会的痛苦。 > 一个有分量的学术补丁：2016 年的 **WiscKey** 论文（Lu 等，FAST'16）提出把"键"留在 LSM 里做排序，把"值"单独扔进一个 value log。因为压实时要反复搬移的大头其实是值，把值剥离出去，写放大立刻大幅下降。今天很多现代 KV 存储（包括 TiKV 用的 RocksDB 的演进、Pebble 等）都吸收了类似思想。这是视频没展开、但极其关键的一条进化线。 ### 七、为什么 SSD 时代，B 树还活着 最后一个很多人会问的问题：**SSD 把随机 I/O 和顺序 I/O 的鸿沟抹平了，B 树不是该淘汰了吗？** 视频的答案（也是业界的共识）非常清醒：**磁盘随机性的确变便宜了，但 LSM 的代价大头根本不在磁盘随机性上，而在"读放大 + compaction 的 CPU/写放大"上。** - HDD 时代：顺序 vs 随机差距是 **几百倍**，LSM 的顺序写优势压倒性。 - SSD/NVMe 时代：差距收窄到几倍甚至一倍多。但 LSM 还是要写多份（WAMP 高）、读多文件（RAMP 高）、烧 CPU 做 compaction。这些代价**和磁盘是否随机无关**。 与此同时，B 树也在进化：微软的 **Bw-tree**（无锁、log-structured 的 B 树变体）用在了 SQL Server Hekaton 和 Azure Cosmos DB 上，试图把 LSM 的顺序写优点嫁接到 B 树框架里。**两棵树正在互相靠近，但谁也没吃掉谁**——因为那个不可能三角没有消失。 ## 知识结构图 ```mermaid graph TD A[数据库存储引擎
核心抉择] --> B{你的负载读多还是写多?} B -->|读多 / 范围扫描 / OLTP| C[B+ 树] B -->|写多 / 日志 / 时序| D[LSM 树] C --> C1[高扇出矮胖树
为磁盘页粒度设计] C --> C2[叶子节点链表
顺序范围扫描] C --> C3[就地更新 in-place
随机 I/O] C --> C4[WAL + 页写
WAMP 中等] D --> D1[MemTable + WAL
内存写入 + 顺序追加] D --> D2[刷盘成 SSTable
不可变有序文件] D --> D3[后台 compaction
合并去重] D --> D4[更新=新版本
删除=tombstone] C4 --> E1[RAMP 低 ✅
点查 3-4 次 I/O] C4 --> E2[WAMP 中 ⚖️] C4 --> E3[SAMP 低 ✅
无重复] D4 --> F1[RAMP 高 ⚠️
需查多层+Bloom] D4 --> F2[WAMP 高 ⚠️
compaction 反复重写] D4 --> F3[SAMP 高 ⚠️
新旧版本共存] E1 & E2 & E3 --> G((不可能三角
WAMP × RAMP × SAMP
无法同时最小化)) F1 & F2 & F3 --> G ``` ## 实战启示 理解了这两棵树，你能做的第一个实战决定是：**别再盲目选数据库，先认清你的读写比例。** 如果你在做一个电商订单系统、用户中心、账务系统——**读多写少、大量点查、需要事务和范围查询**，老老实实选 B+ 树系（PostgreSQL / MySQL）。它们在点查和 ACID 上几乎是教科书级的稳。强行上 Cassandra 只会让你陷入"为什么我的点查延迟抖动这么大、compaction 一直在跑"的泥潭。 如果你在搞**日志收集、监控指标、IoT 时序数据、海量点击流**——写入量是读的几十上百倍、数据按时间衰减、很少做精确点查——那就该看 LSM 系（Cassandra / HBase / ScyllaDB / InfluxDB）。它们能把磁盘的顺序写带宽吃干抹净。 第二个实战点是**面向"放大系数"做容量规划**，而不是面向数据量本身。选了 LSM，就得给 compaction 留出 CPU 和磁盘余量（生产环境常见建议 compaction I/O 预算占盘带宽的 30%–50%），否则压实风暴一来，前台延迟直接崩。选了 B 树，要警惕写放大对 SSD 寿命的消耗——每次 in-place 写都要先 WAL 落盘再写数据页，再加上页分裂时的级联写。 第三个，也是最容易被忽视的认知升级：**学会从"放大"角度看所有存储系统。** Elasticsearch 倒排索引的 refresh、Kafka 的 segment compaction、Redis 的 RDB/AOF rewrite、甚至 ZFS 的 copy-on-write——本质上都在玩 WAMP/RAMP/SAMP 这个三角。一旦你建立了这副眼镜，看任何存储中间件的性能调优文档，都会从"配置项罗列"变成"它在帮我在三角上往哪一边挪"。 最后一句送给所有写 `CREATE INDEX` 的人：**你每一次建索引，都在替数据库做一次放大选择——读变快，写变慢，是物理定律，不是优化技巧。** ## 延伸学习路径 1. **Martin Kleppmann《Designing Data-Intensive Applications》第 3 章**（"Storage and Retrieval"）——公认讲 B-tree vs LSM-tree 最透彻的一章，有具体的写放大、读放大、空间放大推导，强烈推荐配合本文阅读。 2. **Patrick O'Neil 等人 1996 年原论文《The Log-Structured Merge-Tree (LSM-Tree)》**（*Acta Informatica* 33(4)）——LSM 的开山之作，看清它最初是为了解决"历史数据追加"而设计的。 3. **Google Bigtable 论文（Chang 等，OSDI'06）**——把 SSTable + MemTable + compaction 这套架构带进工业界的里程碑，读懂它就读懂了 HBase/Cassandra 的骨架。 4. **WiscKey 论文（Lu 等，FAST'16）《WiscKey: Separating Keys from Values in a Conscientious Storage Store》**——理解 LSM 写放大问题的现代解法，键值分离思想。 5. **Hussein Nasser / ByteByteGo（Alex Xu）的数据库内核系列视频**——配套视频之外，用可视化方式补齐 InnoDB 聚簇索引、RocksDB leveled compaction 的动态过程。 ## 一句话总结 数据库引擎不是魔法师，它是一个在"写放大、读放大、空间放大"这个不可能三角里替你做选择的会计师——B+ 树押注读，LSM 树押注写，而你之所以感觉不到这层残酷，是因为前人已经替你把代价藏进了背景里。 ## 参考来源 1. [How Databases ACTUALLY Work (B-Trees vs LSM Trees, Explained) — Priya Bansal](https://www.youtube.com/watch?v=jQ3w63Lx3aA) — 本次解读的核心视频（发布于 2026-04-14，已核实标题/频道/日期） 2. [The Log-Structured Merge-Tree (LSM-Tree), O'Neil et al., 1996](https://link.springer.com/article/10.1007/s002360050048) — LSM 原始论文 3. [Bigtable: A Distributed Storage System, Chang et al., OSDI 2006](https://research.google/pubs/bigtable-a-distributed-storage-system-for-structured-data/) — SSTable/compaction 架构的工业落地 4. [WiscKey (FAST'16)](https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf) — 键值分离降低写放大 5. [Designing Data-Intensive Applications, Martin Kleppmann](https://dataintensive.net/) — 第 3 章存储与检索，B-tree vs LSM 的权威对照 --- > 本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵**爱卫生**（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 > 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。 > [!tip] 51学通信知识星球 > **星主：爱卫生**（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 > **星球定位**：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 > **当前规模**：5200 篇主题 / 990 个回答，198 元/年。 > **加入福利**：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 > **AI 加持**：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。