一、主流阵营

在主流的、通用的、基于 HDD/SSD 的持久化存储引擎领域中，LSM-Tree 和 B+ Tree 确实是主流的两大主导阵营，它们分别代表了 优化写 和 优化读 两种核心设计的权衡。

两种数据结构的设计都源于一个基本的存储硬件特性：随机 I/O 远比顺序 I/O 慢。举例来说，对于一个寻道延迟为 10ms、吞吐量为 100MB/s 的硬盘，访问一个随机 1KB 数据所需的大约时间是 10ms，而访问下一个顺序块的时间大约是 10µs, 随机与顺序延迟的比率是 1000:1。

• 机械硬盘 (HDD): 随机 I/O 涉及磁头寻道和盘片旋转，延迟在毫秒 (ms) 级别，但是顺序 I/O 要快很多
• 固态硬盘 (SSD): 虽然没有机械部件，随机读的性能大大提升（微秒/µs, 级别），但 SSD 的物理特性决定了它不能原地更新，对一个数据的写操作，必须先擦除，然后再写入新的数据。擦除操作非常耗时，且 SSD 有擦写次数寿命限制

1. 放大型问题

因此，一个好的存储结构设计，必须尽量避免随机写，并将写操作 (尽可能) 转化为顺序写，同时尽可能避免写放大、读放大、空间放大问题。

• 写放大：系统写入的数据量 / 应用请求写入的逻辑数据量；假设应用请求写入 1MB 数据，但存储系统最终向硬盘写入 10MB 数据，写放大就是 10
• 读放大：系统读取的数据量 / 应用请求读取的逻辑数据量；假设应用请求读取 1MB 数据，但存储系统最终向硬盘请求 50MB 数据，读放大就是 50
• 空间放大：存储系统占用的总空间 / 应用存储的有效逻辑数据空间；应用存储了 1GB 的数据，但系统占用了 3GB 的磁盘空间，那么空间放大就是 3

这三个 “放大型问题” 并非孤立，而是相互制约，形成了一个的 “设计权衡三角”：

(1) 写放大和空间放大

例如 LSM-Tree Compaction 策略，激进的 Compaction 策略：高频次的 Compaction 过程会降低空间放大，但会导致极高的写放大；保守的 Compaction 策略：低频次的 Compaction 过程会显著降低写放大，但会导致更高的空间放大。

(2) 读放大和空间放大

例如 LSM-Tree 的 SSTable 设计，更少的 SSTable 文件策略：采用 Level-style compaction，每层只有一个大文件，可以降低读放大，因为查询路径更短；但为了维持这种结构，需要更激进的 Compaction 策略，从而增加写放大。

允许更多的 SSTable 文件 (例如，采用 Tiered-style compaction，每层有多个文件): 写操作更简单（只需不断堆叠新文件），写放大更低。但读操作需要在更多文件中查找，读放大更高。 B+ Tree vs. LSM-Tree 的根本权衡:

(3) 读放大和写放大

B+Tree 的读取放大低于 LSM-Tree，而 LSM-Tree 的写放大低于 B+Tree。

这也是 B+ Tree vs. LSM-Tree 的根本权衡: B+ Tree 通过较高的写成本（随机写）换取了极低的读放大和空间放大；而反过来，LSM-Tree 通过极低的写成本（顺序写）为代价，接受了较高的读放大、写放大和空间放大等 “潜在问题”，并通过后台 Compaction 进程来解决这些 “潜在问题” 。

一般来说，一个数据结构最多可以优化写放大、读放大、空间放大三个问题中的两个，这也意味着，一种数据结构不太可能在三个问题上都完全优于另一种数据结构。

2. B+ Tree

B+Tree 属于原地更新型的数据结构，为快速读取而优化。

通过在内部节点中使用较大的度数来减少树的高度，将传统的二叉树结构 (又瘦又高型)  变为一棵又矮又胖的平衡树，充分利用硬件和操作系统提供的缓存局部性（预读）和磁盘请求友好顺序，来最小化定位数据所需的寻道次数。

B+tree 能够提供最优的读性能，主要体现在 I/O 次数非常少并且非常稳定，范围查询非常高效，叶子节点之间的双向链表可以实现顺序 I/O。

但是 B+tree 的写性能并不好，每次写操作需要先定位到叶子结点，然后把叶子节点的数据读出来 -> 修改 -> 再写回去。这种原地更新的方式开销较大，因为整个过程不仅需要多次寻道，而且存在较高的写放大。例如，要在一个 8KB 的节点中更新一条 128B 的数据记录，必须读写整个节点，那么这就会带来 64 倍 (8KB / 128B) 的写放大。这样的话，对于一块 640MB/s 带宽的磁盘来说，持续写入的带宽最多只能达到 10MB/s。所以 B+tree 对于写入密集型的应用并不是一个好的选择，尤其是每条数据记录比较小的情况下。

数据记录和写放大成反比例，单条数据记录越小，写放大就越大。

对于并发控制来说，B+Tree 中的同一个 Key 只有一份，虽然树结构更容易进行加锁/解锁操作，但是实现比较复杂，对树结构的修改（如节点分裂/合并）需要使用精细的锁来保护临界区，容易成为并发瓶颈。

综上，B+Tree 对 HDD 和 SSD 都适用，适合读多写少、对空间放大非常敏感、需要非常稳定且低延迟的点查询和范围查询的场景，但是其随机写特性在 HDD 上表现得更差，典型的应用场景在传统关系型数据库，例如 MySQL (InnoDB 存储引擎), PostgreSQL 等。

3. LSM-Tree

LSM-Tree 属于 “追加写/延迟更新” 的数据结构。为快速写入而优化。

通过将数据先写入内存中的 MemTable，MemTable 写满之后，变为只读的 Immutable MemTable，然后 Immutable MemTable 作为一个整体（SSTable）顺序刷到磁盘，通过写入内存中的 MemTable（极快）外加写入 WAL 来保证持久性（一次顺序写），整个过程几乎都是内存操作和顺序磁盘写操作，写性能非常高。

当然，LSM-Tree 实现高性能写入的同时，也带来了读放大和写放大问题，对于读操作来说，需要依次查询 MemTable、多层 SSTable，最坏情况下，需要查询所有层级才能找到数据，虽然单个 SSTable 内的数据有序，但跨层级的 SSTable 数据无序，范围查询需要在多层 SSTable 上进行归并查找，比 B+ Tree 复杂且效率略低 (主要取决于 LSM-Tree 层级数量和 B+Tree 的高度)；对于写操作来说，一个数据在其生命周期内会被多次重写：MemTable -> L0 SSTable -> L1 SSTable -> … LN SSTable, 每次 Compaction (压缩) 过程都会读出旧数据并写入新数据，过多的数据擦除次数对 SSD 寿命很不友好。

对于并发控制来说，LSM-Tree 中的同一个 Key 会存在多份 (具体取决于 Compaction 进程的频次和速率)，一般使用 MVCC 进行控制，实现也相对简单，写操作是无锁的（写入 MemTable 可以使用无锁数据结构），读操作是无锁的（SSTable 是不可变的），主要冲突可能发生在 Compaction 进程。

综上，LSM-Tree 更适合 SSD，因为它将随机写转换成为批量的顺序写，符合 SSD 的物理特性，适合写多读少、数据写入后较少更新、能够容忍稍高的读延迟，但需要极高的写入吞吐量的场景，典型的应用场景在 NoSQL 和现代分布式数据库，例如 LevelDB, RocksDB, TiDB (使用 RocksDB 作为存储引擎) 等。

4. 小结

我们可以根据一些应用场景 (图中的比例值可以根据具体场景修改)，叠加基准测试的结果来选择不同的存储引擎。

二、非主流阵营

B+ Tree 和 LSM-Tree 的经典设计，主要优化目标是减少 I/O 次数和将随机 I/O 顺序化。我们可以说，至少在 HDD 硬件上，B+tree 和 LSM-tree 都处于最优的设计领域中。

当然，这个版图阵营并非仅此两家独大，除此之外，还存在其他重要的数据结构，它们在特定场景下甚至比 LSM-Tree 和 B+ Tree 更优越。当硬件特性发生变化，例如，出现了廉价的大容量内存、速度媲美 DRAM 的持久内存 (PMem, 断电后不丢数据)，或是 I/O 本身已经非常快时 (例如 Nvme)，这时，新的优化机会和设计范式便会应运而生。

例如，以 Bitcask 为代表的、追求极致点查性能的 哈希索引 阵营，大量混合和特化的数据结构（例如 WiscKey、分形树、Trie 等）也在各自的细分领域展现出强大的生命力，不断丰富和挑战着已有的数据存储引擎格局。

1. 哈希索引

B+ Tree 和 LSM-Tree 本质上都是有序结构，它们维护了 Key/索引 的排序信息，以便支持范围查询。但如果我们放弃范围查询这个需求，只关心一个最基本的 KV 存储问题：“某个 Key 对应的数据在哪里？” 那么显然，一种更直接、更快速的方案就是使用 哈希索引。

这里以 Bitcask 为代表，这种哈希索引数据结构的核心思想是：使用哈希函数直接将 Key 映射到数据的位置，实现 O(1) 复杂度的查找。

Bitcask 和 LSM-Tree 类似，所有的数据（KV 键值对）都以追加方式写入一个或多个数据文件中，可以将 Bitcask 看作 LSM-Tree 的 “精简版本”，这个 “精简版本” 两个主要的约束条件是：第一，全部 Key 都必须放入内存；第二，不支持范围查找。

对于写操作来说，因为写入是纯粹的顺序 I/O，速度极快，数据文件中的条目包含 Key、Value、时间戳等元信息；对于读操作来说，可以直接在内存的哈希表中查找 Key，获得其位置信息（一次内存访问，极快），然后根据位置信息，在磁盘上进行一次精确的随机 I/O，直接读出 Value 数据。更多的细节可以 查看之前的文章。

2. 针对特定硬件或场景的混合数据结构

LSM-Tree 的 Compaction 过程会带来巨大的写放大，因为每次合并过程都需要重写 Key 和 Value。现实系统中的 Value 通常比 Key 大得多（例如，Key 是一个 UUID，Value 是一张图片或一个 JSON 文档），即使一个 Value 本身没有发生任何变化，但仅仅因为它所在的 SSTable 文件需要被合并，这个巨大的 Value 也要被完整地从旧文件读取出来，再完整地写入到新文件中。

理所当然，WiscKey 的核心思想就 Key-Value 分离存储，精准地解决了 LSM-Tree 在处理大 Value 时的写放大问题，提升性能和 SSD 寿命，更多的细节可以 查看之前的文章。

3. 分形树索引 (Fractal Tree Index)

B-Tree (包括 B+Tree) 的问题在于写操作是同步的、阻塞的，一次节点分裂可能会带来一连串的 I/O，导致写延迟抖动很大，并可能引发更严重的 “级联影响”。

根据操作系统设计中的 Cache/Buffer 的启发，我们可以想到的一个优化方案是：针对内部节点设置写缓冲区。而这一点正是分形树索引的核心思想：在 B-Tree 的内部节点中设置缓冲区，将更新操作缓存在树的上层，然后将更新操作批量向下传递，可以看作是 B-Tree 和 LSM-Tree 的一种混合体数据结构。

一个知名的开源项目是 TokuDB, 其核心设计理念是将 LSM-Tree 的延迟更新/缓冲设计应用到 B+ Tree 上，摊平 B-Tree 中的写操作成本。

从数据角度来看，分形树仍然是一棵 B-Tree，但其内部节点不再仅仅是索引，还附带了消息缓冲区。对于写操作来说，不会立即去最深层的叶子节点修改数据，而是将写入操作当作一个 “消息”（例如，插入 (K,V)， 或删除 K）被写入到根节点的缓冲区中。当一个节点的缓冲区满了，就将缓冲区内的消息 刷新写入 到其所有子节点的缓冲区中，这个过程就像 “水流” 一样会一直 “从高到低” 持续进行下去，直到消息最终到达叶子节点，并被应用到实际的数据上。

通过缓冲优化可以优化为：大量的随机写被批量地、异步地应用到树的深层节点，这样单次写操作的延迟极低（只需写入根节点的内存缓冲区），写吞吐量大大提高。

4. 前缀树 (Trie / Radix Tree)

当 Key 是字符串类型时，B+ Tree 的比较开销会变大，且无法利用多个 Key 之间的公共前缀。

Trie 树（或称字典树、基数树）根据 Key 的前缀来组织数据，可以针对 字符串 Key 和可变长 Key 专门做优化，对于有公共前缀的 Key非常高效，支持按前缀的范围查询。例如， apple 和 apply 这两个 Key 会共享 appl 这段公共前缀路径，极大节省了空间。

对于 IP 路由表、编程语言中的字典数据结构实现等场景，前缀树几乎是最优选择。

三、总结

从更广阔的视角来看，B+ Tree 和 LSM-Tree 不再是孤立的两个阵营和单一选择，而是位于由多种设计/权衡维度构成的交叉区域。

• 数据有序还是无序，决定了是否支持高效的范围查询
• 数据原地更新还是追加写，决定了读写性能的选择倾向
• Key/Value 耦合还是分离，决定了写放大和对大 Value 的合并处理效率
• 数据同步更新还是缓冲/异步更新，决定了写入操作的延迟和抖动

没有银弹，根据系统场景，选择合适的数据结构即可