打开任何一个数据库——MySQL、PostgreSQL、MongoDB、Cassandra、RocksDB——在它优雅的 SQL 接口之下，都藏着一个默默干脏活累活的核心组件：存储引擎。它要回答一个看似简单、实则极难的问题：当数据多到内存装不下，必须存在磁盘上时，怎样组织这些字节，才能既快速地写进去、又快速地查出来？这个问题的两种主流答案——B 树和 LSM 树——划分了整个数据库世界的两大阵营。
破除误解：数据结构的快慢，要看它跑在什么硬件上
学过算法的人都知道，平衡二叉搜索树的查找是 ，听起来已经很好。那为什么数据库不直接用二叉树，偏要发明 B 树这种"一个节点装几百个键"的怪东西？
答案藏在一个常被忽视的事实里：算法的真正瓶颈不是比较次数，而是磁盘 I/O 次数。 从内存读一个数据要几十纳秒，从机械硬盘读一次要几毫秒——相差十万倍。即使是固态硬盘（SSD），单次随机读写也比内存慢上千倍。更关键的是，磁盘读取有最小单位（"块"或"页"，通常 4KB 或更大），你想读 1 个字节，硬件也得把整页搬上来。
这彻底改变了游戏规则。一棵高瘦的二叉树，查一个键要走几十层，每下一层可能就是一次昂贵的磁盘访问。而一棵矮胖的树——每个节点塞进几百个键、有几百个分叉——只需走三四层就能定位几亿条记录中的任意一条，把磁盘访问次数压到极致。B 树的全部设计哲学，就是为磁盘这种"批量读取、随机访问昂贵"的硬件量身定做的。 脱离硬件谈数据结构的优劣，是初学者最常见的盲区。
B 树：读优化的经典之作
B 树（B-Tree，1970 年由 Bayer 和 McCreight 提出）及其变体 B+ 树，统治数据库存储引擎近半个世纪。它是一棵多路平衡搜索树：
- 每个节点存储多个有序的键，以及指向子节点的指针（一个节点可能有几百个分叉）。
- 所有叶子节点都在同一层（完美平衡），保证任何查找的路径长度一致。
- 在 B+ 树中，所有真实数据都存在叶子层，且叶子之间用指针串成有序链表——这让范围查询（"找出所有 18 到 25 岁的用户"）变得极快，顺着叶子链表扫一遍即可。
顺带破除一个高频误解：B 树不是二叉树（binary tree）。发明者 Bayer 与 McCreight 当年在波音研究实验室（Boeing Research Labs）工作，论文 1970 年起在内部流传、1972 年正式发表，但两人从未公开解释 "B" 究竟代表什么——Boeing、balanced（平衡）、broad（宽）、Bayer 都只是后人的猜测。能确定的只有一点：它绝不是每个节点只有两个分叉的二叉树，恰恰相反，分叉越多越好。
这个"多"有多夸张？以 MySQL 的 InnoDB 为例，其默认页大小是 16KB；当主键是定长整数时，单个节点能容纳数百到上千个键与指针。于是一棵只有三到四层的 B+ 树，就足以索引数十亿条记录——查任意一条，最坏也只需三四次磁盘读取。这正是"矮胖"在工程上的真正分量。
B 树的杀手锏是就地更新（update-in-place）：要改一个值，直接找到它所在的磁盘页，原地改写。这让它的存储结构紧凑、读取路径短而可预测。MySQL 的 InnoDB、PostgreSQL 的默认索引、几乎所有关系数据库的核心，都是 B+ 树。
但就地更新也是它的软肋：写入往往是随机的磁盘 I/O。 插入一条新记录可能落在磁盘上任意位置的某一页，对机械硬盘而言，随机写意味着磁头疯狂寻道，慢得令人发指。当写入压力极大时，B 树会力不从心。
LSM 树：写优化的反向思路
针对"随机写慢"这个痛点，另一派给出了截然相反的设计。LSM 树（Log-Structured Merge-Tree，由 O'Neil 等人 1996 年提出，因 Google 的 Bigtable 和后来的 LevelDB/RocksDB、Cassandra、HBase 而风靡）的核心信念是：绝不随机写磁盘，只顺序追加。
它的工作方式分三步：
- 内存缓冲（MemTable）：所有写入先进入内存中的一个有序结构（通常是跳表或平衡树）。内存操作极快，且此时还没碰磁盘。同时，为了不丢数据，每次写入会先追加到一个磁盘上的预写日志（WAL）——这是顺序写，很快。
- 刷盘（Flush）：当内存缓冲满了，把它整体、有序地、顺序写入磁盘，成为一个不可变的文件（SSTable，Sorted String Table）。注意：是顺序写一整块，而不是东一下西一下的随机写——这正是 LSM 树写入快的根源。
- 后台合并（Compaction）：磁盘上会越积越多 SSTable 文件，后台进程定期把它们归并排序、合成更大的文件，并在此过程中丢弃被覆盖的旧值和被删除的记录。
这个设计把"随机写"巧妙地转化成了"顺序写 + 后台批量整理"，写入吞吐能比 B 树高出数倍乃至一个数量级。
微妙之处：天下没有免费的午餐
LSM 树的写入优势不是白来的，它把代价转移到了别处，理解这些代价是选型的关键。
读放大（Read Amplification）：查一个键时，它可能在内存缓冲里，也可能在磁盘上任意一个 SSTable 里。最坏情况下要从新到旧翻遍多个文件才能确定。为缓解这点，LSM 树大量使用 data-structures 中的布隆过滤器（Bloom Filter）——一种能极快判断"这个键肯定不在某文件里"的概率结构，让查询跳过绝大多数无关文件。它的代价极小：RocksDB 默认每个键只用 10 比特，误判率即可压到 1% 以下，而这个误判率有精确的概率公式可以事先算出。
写放大（Write Amplification）：同一份数据在后台合并过程中会被反复读出、重写多次。这意味着实际写入磁盘的数据量，远大于用户提交的数据量。在 SSD 上，写放大会加速闪存磨损，缩短硬盘寿命——这是一个真实的硬件成本。
空间放大（Space Amplification）：在合并完成前，同一个键的多个旧版本可能同时存在于不同文件中，占用额外空间。
于是出现了一个经典的"不可能三角"：读放大、写放大、空间放大三者往往无法同时最小化，调优 LSM 树本质上是在这三者间做权衡（这被称为 RUM 猜想）。
合并策略：一个被低估的关键旋钮
LSM 树性能的成败，很大程度上系于后台合并到底怎么做。两种主流策略恰好站在 RUM 三角的两端。
分级合并（Leveled Compaction）：把磁盘组织成若干层，每层容量约为上一层的 10 倍，每层内部保持全局有序、互不重叠。它的读放大和空间放大都小，但写放大偏大——一个字节从某层并入下一层时，要与下一层约 10 倍的数据一同重写，逐层累加，总写放大常常超过 10，典型估算约在 30 上下。RocksDB 在较大的层默认采用它。
分层合并（Tiered / Size-Tiered Compaction）：攒够若干个大小相近的文件，再一次性归并。它的写放大显著更低，但同一个键可能散落在更多文件里，读放大与空间放大随之上升。Cassandra 默认走的就是这条路。
没有哪种策略全面占优，这正是 RUM 猜想在工程上的具体化身。RocksDB 干脆提供"分层 + 分级"的混合策略：小层用分层、大层用分级，试图同时摁住三种放大。
代价与争议：选哪个？
没有绝对的赢家，选择取决于工作负载：
| 维度 | B 树 | LSM 树 |
|---|---|---|
| 写入吞吐 | 较低（随机写） | 高（顺序写） |
| 读取延迟 | 低且可预测 | 可能较高（需查多文件） |
| 空间利用 | 紧凑 | 有放大，但压缩友好 |
| 典型代表 | InnoDB、PostgreSQL | RocksDB、Cassandra、HBase |
| 适用场景 | 读多写少、需强一致 | 写密集、海量数据摄入 |
界限正在模糊：现代引擎在互相借鉴。一些 B 树实现引入了日志结构来改善写入；LSM 树则不断优化合并策略来压低读延迟。MyRocks（基于 LSM 的 MySQL 存储引擎）与传统 InnoDB 的并存，正说明同一个数据库可以按需切换底层引擎。事实上，Dong、Callaghan 等 Facebook 工程师在 2017 年的论文里报告：在他们的生产负载下，RocksDB 占用的存储不到 InnoDB 的一半，性能却相当甚至更好——这正是 Facebook 用 MyRocks 替换部分 InnoDB 集群的直接动因。但 Callaghan 也长期强调：脱离具体的读写比例、数据规模和硬件，空谈"B 树和 LSM 谁更好"是没有意义的。
存储引擎的研究也仍在推进。一条活跃的路线是键值分离（key-value separation）：威斯康星大学的 WiscKey（FAST 2016）提出，把键留在 LSM 树里、把体积更大的值单独存进一个追加日志，合并时只搬动小小的键、不再反复重写笨重的值，写放大因此大幅下降；论文报告其随机查找比 LevelDB 快 1.6 到 14 倍。这一思路已被 Go 语言写成的 BadgerDB 等引擎直接采用，RocksDB 自身也在 2021 年加入了同源的 Integrated BlobDB 机制。
跨域连接
- 文件系统：日志结构的思路先出现在文件系统里——把整块盘当成只追加的日志，随机写就变成顺序写，代价是需要后台清理器回收作废数据。存储引擎的刷盘与合并是同一套账，只是把清理改名叫压实。两边都必须回答同一个问题：清理什么时候做、占多少带宽。
- 半导体物理：闪存用困在浮栅里的电荷表示比特，写入与抹除都要让电子穿过绝缘层，每次都累积损伤；而抹除的粒度远大于写入的粒度。写放大因此不是固件缺陷，而是器件物理的直接后果，它同时决定寿命与成本。也因此，把大值搬出合并路径这类做法的收益，直接等于少写了多少字节。
- 概率论：布隆过滤器只可能假阳性、绝不假阴性，这条不对称才是它能安全跳过文件的理由。误判率有闭式公式，可以事先按每键几个比特把它压到百分之一以下，用极小空间换掉大量无谓的磁盘访问。
- 机会成本：读放大、写放大、空间放大构成一条可能性边界，调参只是在边界上移动。因此"某引擎全面更优"若为真，只能说明比较基准原本落在边界内部（实现不佳），而不是边界本身被推开了。同理，声称同时压住三种放大的混合策略，实际做的是按层分别选点。
- 古气候与冰芯：冰芯是天然的追加式日志，只能自顶堆积，读历史要往下钻，而深层被自重压实、分辨率下降。这与分层合并的取舍同构：越靠下的层越大、越少改动，代价是定位一条旧记录要穿过更多层。冰芯的分辨率随深度下降，也正对应旧数据被反复合并后失去的时间粒度。
参考文献
- Bayer, R. & McCreight, E. Organization and Maintenance of Large Ordered Indices. Acta Informatica 1, 1972. （B 树原始论文）
- O'Neil, P. et al. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33, 1996. （LSM 树原始论文）
- Athanassoulis, M. et al. Designing Access Methods: The RUM Conjecture. EDBT, 2016. （读/写/空间放大权衡的理论框架）
- Lu, L., Pillai, T. S., Arpaci-Dusseau, A. C. & Arpaci-Dusseau, R. H. WiscKey: Separating Keys from Values in SSD-Conscious Storage. USENIX FAST, 2016. （键值分离，从根本上削减写放大）
- Dong, S., Callaghan, M., Galanis, L., Borthakur, D., Savor, T. & Strum, M. Optimizing Space Amplification in RocksDB. CIDR, 2017. （RocksDB 在生产负载下比 InnoDB 节省一半以上空间）
- Rosenblum, M. & Ousterhout, J. K. The Design and Implementation of a Log-Structured File System. ACM Transactions on Computer Systems 10(1), 1992. （日志结构思想的源头）
延伸阅读
- Kleppmann, M. Designing Data-Intensive Applications. O'Reilly, 2017. 第3章. （对两类存储引擎最清晰的工程对比）