为什么 MySQL 选了 B+ 树，LevelDB 却选了 LSM-Tree？

看两个事实：MySQL 的 InnoDB 引擎，用 B+ 树组织数据，统治了 OLTP 世界二十年；LevelDB 及其后裔 RocksDB，用 LSM-Tree 组织数据，撑起了写密集场景的半壁江山。两者面对的是同一道题——如何把海量数据放进磁盘，还扛得住读写——却在数据结构上做出了几乎相反的选择。

这不是谁更聪明的问题。这两个选择，是同一组物理约束下两条自洽的路线：一条把宝押在”读要快”，一条把宝押在”写要快”。把这对镜像看透，存储引擎的半部教科书就读完了，而且你会获得一个可复用的选型心法。

一、共同的起点：磁盘的物理现实

一切要从硬件说起。机械硬盘的随机读写和顺序读写之间隔着两三个数量级——顺序写一秒钟几百 MB，随机写每秒只有几百次；SSD 把随机读拉平了，但随机小写入依然昂贵，因为它会引发写放大，磨损闪存寿命。

存储引擎的所有设计，本质上都在回答同一个问题：当”读得快”和”写得快”不可兼得时，把资源押给谁？

答案是：看负载。读多写少的交易库和写吞吐爆炸的日志管道，注定要走上不同的路。B+ 树和 LSM-Tree，就是这两条路的代表。

二、B+ 树：为读而生的一棵”胖树”

InnoDB 的世界里，数据住在 16KB 的页里，页与页之间用 B+ 树组织。这棵树有两个关键特征：矮和胖。非叶子节点只放路标不放数据，一个 16KB 的页能塞进几百上千个路标，于是扇出极大——三四层的树，就足以索引千万乃至上亿行。树越矮，找到一份数据要做的磁盘跳转越少：根节点常驻内存，实际只需要一两次 IO。

叶子节点之间用双向链表串起来，这让 B+ 树天生擅长范围查询——”查某个时间段的订单”这类 OLTP 常见请求，顺着链表扫过去就行。再加上主键聚簇索引的加持，单行点查快而稳。

它的代价在写。B+ 树是原地更新的结构：改一行，要先定位到那一页，改的是页本身。一页写满再插入，就要页分裂；一页删空，还要页收缩。每一次这些动作发生在磁盘的哪个位置，完全由 key 决定——这正是”随机写”的定义。为了让崩溃可恢复，还得先写 WAL 再动页，脏页攒多了又要有 Checkpoint 机制慢慢刷回磁盘。一条小小的 UPDATE，背后是定位、加锁、日志、刷脏一整套动作，这就是 B+ 树的写放大。

一句话总结：B+ 树把复杂度留在了写路径，换来了读路径的极简——一次查询，一条确定性的短路径，走完就到。

三、LSM-Tree：为写而生的一摞”账本”

LSM-Tree 的世界观完全相反：既然随机写贵，那就永远顺序写。

它的写路径简单到极致：数据先追加到 WAL，再插入内存中的 memtable（通常是一棵跳表）；memtable 攒满了，整体刷成一个不可变的 SSTable 文件落盘。整个写入过程没有一次随机 IO——这就是它写吞吐惊人的原因，也是 Kafka 这类顺序写系统的共同哲学。

但账不能只记不理。磁盘上会积累一层又一层的 SSTable，同一份数据在不同层里有不同版本。于是需要一个后台角色：compaction，把各层的文件归并排序、去重、扔掉被删除的旧版本，压成更干净的新文件。

天下没有只赚不赔的买卖，LSM 把复杂度全部转移到了读路径。查一个 key，它不知道数据在哪一层，只能从 memtable 开始逐层找：

get(key):
  1. 查 memtable，命中即返回
  2. 查 L0 的每个 SSTable（L0 文件之间 key 范围可能重叠，都要查）
     —— 每个文件先用布隆过滤器快速判断"不可能包含此 key"则跳过
  3. 逐层向下查 L1、L2……Ln（同层文件不重叠，二分定位）
  4. 命中即返回，全部未命中则返回"不存在"

这就是读放大：最坏情况要翻好几层、好几个文件。LSM 用布隆过滤器（一步过滤掉绝大多数”肯定没有”的文件）和层级设计（新数据在上层，越新越先被查到）把读放大压到可接受，但压不没。

还有两笔隐性成本。一是空间放大：归并完成前，同一个 key 的多个版本同时存在，删除也只是先记一个墓碑标记；二是 compaction 对前台的干扰：后台归并和前台写入抢磁盘带宽，压得狠了会触发 write stall，表现为监控图上毫无征兆的延迟毛刺——这是 LSM 系数据库最经典的线上问题。

四、取舍的本质：放大的三角

把两条路线放到同一张表里，取舍一目了然：

维度	B+ 树（InnoDB）	LSM-Tree（LevelDB/RocksDB）
写路径	随机写，原地更新，写放大中等	顺序写，写吞吐极高
读路径	短而确定，点查与范围查询都快	需逐层查找，读放大，依赖布隆过滤器
空间	紧凑（原地更新无多版本）	空间放大（多版本与墓碑并存）
延迟形态	平稳	均值低但有 compaction 毛刺
典型负载	读多写少、强事务、复杂查询	写密集、追加型、日志与时序

学术界给这个现象起过一个名字：RUM 假说——读开销（Read）、写开销（Update）、空间开销（Space），三者不可能同时最优，任何结构都只能追求其中两项的均衡。B+ 树押了”读 + 空间”，LSM 押了”写 + 读（配合过滤器）”，三角形的第三条边永远是软肋。

这也解释了今天的融合趋势：FaceBook 把 RocksDB 塞进 MySQL 做成 MyRocks，用 LSM 的顺序写和压缩特性，给写密集业务省下大半存储成本；而 RocksDB 又长年给 LSM 加布隆过滤器、加并发 compaction，拼命补读的短板。没有哪个结构赢得了三角，工程能做的是根据负载把资源挪向最重要的那条边。

五、选型的心法

落到工程决策上，可以收敛成三条。

先量化负载，再看结构。拿出真实的读写比：每秒几百次写、读写比 10:1 的交易库，B+ 树稳如泰山；日志、指标、用户行为流水这类写吞吐为主、读多走批量扫描的数据，LSM 系更省钱。选型争论之所以常见，是因为争论双方看的负载根本不是同一个。

理解写放大，才能读懂生产现象。为什么 InnoDB 大批量导入前建议关掉部分二级索引？为什么 RocksDB 的延迟曲线总有周期性尖刺？为什么顺序写比随机写快上百倍不是玄学而是物理？答案都在写放大里。

把”没有免费的结构”当作通用心法。这个视角可以迁移到一切选型问题上：缓存与一致性、索引与写入代价、副本与可用性——每一次”为什么 X 不用 Y”的追问，最终都会落到同一个答案：负载不同，押注不同。

下一次，当你在技术方案评审里听到”用 LevelDB 还是 InnoDB”的争论，别急着站队。先问一句：这个场景里，读、写、空间，哪两项是你真正买得起的？数据结构的选型，从来不是选最强的，而是选最配的。