B+Tree vs. LSM Tree

B+Tree 是按页组织的多路平衡搜索树；LSM Tree 是把更新分批排序、逐步合并的存储组织方式。 两者都能提供按 key 排序的访问，都能支持点查与范围扫描。LSM 的全称是 Log-Structured Merge Tree，它通常不是一棵由父子指针连接起来的树。

本文的 B+Tree 指典型的可变页实现；LSM 主要以 RocksDB / LevelDB 风格的 MemTable + SSTable + Leveled Compaction 为例。写时复制的 B+Tree、键值分离的 LSM 等变体会改变成本，不能把本文的倾向当成所有实现的定律。

数据结构不等于数据库

• B+Tree 管 key 的顺序与定位，叶子既可以放行数据，也可以放指向行的标识。
• LSM 管多个有序数据源的写入、查找与合并，不自动提供 SQL、复制或分布式一致性。
• 事务、隔离和持久性由完整存储引擎实现。WAL、MVCC、锁与恢复协议都不能只靠一个结构名称推断。

例如，InnoDB 的聚簇索引叶子承载行记录；二级索引记录包含主键，必要时再用主键查聚簇索引。PostgreSQL 的 B-tree 叶子则保存指向 heap 表元组的 TID，不能把两者的“回表”成本混为一谈。官方文档常统称 B-tree，本文沿用教学语境中的 B+Tree 来强调记录位于叶子的组织方式。索引布局来源：1、2、3

2.1 页面里放什么

内部页存分隔键与子页指针，用一个比较结果缩小搜索范围；叶子页存有序索引条目，并通常通过兄弟指针连接。所有叶子位于同一深度。页头还要保存条目数、空间信息等元数据，具体布局由引擎决定。

数据库处理的是字节容量，不是课本里固定的“每个节点三个 key”。变长 key、记录头、页目录、页内碎片、前缀压缩都会影响一个页能放多少条目。页内查找也不要求记录在物理字节上紧密排序，可以通过目录或偏移表定位。3、10

2.2 为什么树通常很矮

内部页不放完整行，能容纳很多子页指针，这个数量叫扇出（fanout）。做一个明确的容量估算：假设页大小 16 KiB，扣除开销后可用 12,000 B；每组分隔键与指针平均 24 B，则内部页扇出约为 500。若每个叶子页能放 80 条行记录：

根页 → 一层内部页 → 叶子页：500 × 500 × 80 ≈ 2,000 万条

这是三层树的理想化容量，不是 InnoDB 的容量承诺。长主键和宽行会降低容量；真实填充率也不会一直是 100%。InnoDB 默认页大小为 16 KiB，但不是所有 B+Tree 都采用这个大小。2

点查通常访问一条根到叶子的路径。树高不等于物理读盘次数：根页和上层内部页容易留在缓存中，热查询甚至不需要读盘；二级索引回表、MVCC 可见性检查又可能增加访问。

2.3 插入：先找位置，空间不足才分裂

1. 沿分隔键下降到目标叶子，把需要的页读入缓冲池。
2. 在短期页锁存器（latch）保护下插入条目，维护页内顺序，并记录恢复所需的日志。
3. 空间不足时，可能先整理页面或清理可回收条目；仍放不下才分裂。
4. 新建兄弟页，分配条目，修正链接，并在父页加入分隔键和新子页指针。
5. 父页也放不下则继续向上分裂；根分裂使树高增加一层。

顺序递增插入集中在树的一端，往往有较好的缓存局部性和页面利用率，但高并发下可能形成热点页争用。随机 key 把修改分散到更多页，缓存之外的读改写压力可能更大。“B+Tree 写入都是随机 I/O”不成立，WAL 是追加写，脏页也可以合并修改、批量刷出。

2.4 更新与删除不是简单的原地覆盖

如果是不改变 key 的定长字段更新，可变页引擎有机会只修改当前记录所在页。但变长 value 可能放不下，改变索引键通常意味着删除旧索引项、插入新索引项；涉及多个索引时会放大维护工作。

MVCC 还要求保留旧读者需要的版本。PostgreSQL 的更新可能在 heap 中产生新版本，并带来新索引条目；HOT 优化和索引垃圾清理会改变这一成本。因此，“B+Tree 每个 key 永远只保留一个物理版本”是错的。3

删除也可能先做逻辑标记，待可见性条件满足后再回收。课本中的借位、合并、递归修复是算法模型；生产引擎常延迟处理，不能假设每次删除都立即合并半空页。InnoDB 有页面合并阈值，PostgreSQL 有 bottom-up deletion 和 VACUUM 等清理机制。页内空间可复用，也不等于表文件立即缩小并归还操作系统。2、3

3.1 前台写入的四个环节

以启用 WAL 的普通 RocksDB 写入为例，概念路径如下。并发写、分组提交和流水线优化可以调整执行细节，但不能破坏可见性与恢复顺序。4

1. 分配序列号，让更新具有确定的版本顺序。教学上可把内部 key 理解为 user_key + sequence + type；同一 user key 的新版本排在旧版本前面。
2. 追加 WAL，记录这次写入或整个 WriteBatch。WAL 按写入顺序组织，不按 key 排序。要求同步持久化时，返回成功前还要完成相应同步。
3. 插入活跃 MemTable，使读取能看到已发布的更新。RocksDB 默认使用跳表维护顺序，也支持其他 MemTable 实现；“内存表就是哈希表”不是通用结论。
4. 切换与刷盘，活跃 MemTable 达到阈值后冻结，新的 MemTable 接收写入；后台把冻结表刷成 SST 文件。

3.2 SSTable 不是“把日志改个文件名”

SSTable 是 Sorted String Table，在这里可理解为不可变的有序键值文件。刷盘遍历 MemTable 的有序内容生成它；WAL 则保留操作顺序，两者用途与格式都不同。

RocksDB 默认的 BlockBasedTable 主要包含：5

• 数据块：按 key 排序的条目分块存储，块可以独立压缩并带校验信息。
• 索引块：把 key 范围映射到数据块的偏移与大小，不必把整个 SST 读入内存。
• 过滤器：配置 Bloom Filter 等过滤策略后，帮助跳过不可能包含目标 key 的文件或分区。
• 元数据与 footer：记录属性、元块位置等信息，用于打开和解释文件。

SST 不可变意味着更新不需要在它内部移动已有记录，压缩与校验也更容易以块为单位处理。代价是新版本要在别处存放，之后通过合并消除冗余。

3.3 层级、文件与有序段不要混淆

一个 **sorted run（有序段）**是逻辑上连续有序的一组数据，可以由一个文件或多个按范围切开的文件组成。在经典 Leveled 模型里：

• L0 接收刷盘文件。不同批次的 key 范围可以重叠，所以一个 key 可能对应多个候选文件。
• L1 及更深层通常各自构成一个有序段，层内文件按 key 范围分区，跨层仍然可以重叠。
• 下层的目标总容量通常按倍率增长，不等于每个文件都按相同倍率变大，也不等于层内所有记录都比上层的每条记录更旧。

读取需要根据文件元数据缩小候选范围。层数、文件数和数据块读取次数是三个不同指标；“LSM 查询扫描所有 SST”同样不准确。6

3.4 谁记得哪些文件有效

MANIFEST 记录文件集合及其变更，CURRENT 指向当前 MANIFEST。 合并写出新文件后，需要可靠地发布“加入这些文件、移除那些文件”的元数据变更，才能切换读视图。旧文件还要等不再被读者引用后才能删除。

恢复不能简单地扫描目录，把所有 .sst 当作有效数据。崩溃时可能存在尚未发布的合并输出，也可能存在尚未物理删除的旧文件。WAL 解决未刷盘更新的恢复，MANIFEST 解决文件集合的一致性，这两个职责不同。9

4.1 同一组操作，两种物理组织

从空库开始，执行下面五次已成功提交的单 key 操作。在序列号 101 之后保存一个读快照。这里的 s 是教学上的全局操作序号，不表示所有数据库都用 RocksDB 的序列号实现 MVCC。

最新视图应返回 10=B、30=C，20 不存在；快照 S101 应返回 10=A、20=X，30 不存在。查询结果由隔离语义决定，不能因为换了存储结构就改变。

B+Tree 引擎先用索引找到候选记录，再根据自身 MVCC 机制判断可见性或访问旧版本。LSM 可能在内存与不同 SST 中保存这些内部条目，读取时选择快照可见的最新版本；普通序列号模型下，就是同一 key 中最大的 s ≤ snapshot_seq。若选中删除标记，就返回不存在。3、8

4.2 LSM 点查如何减少搜索

在没有 Merge Operand、范围删除等扩展的普通点查模型中，可先查活跃与冻结 MemTable，再按版本优先关系检查候选 SST。不能把“内存找到同名 key”直接等同于“找到可见版本”。旧快照可能需要继续查找。

对一个磁盘候选文件，依次利用 key 范围、过滤器、块索引和块缓存缩小工作量。经典 Leveled 的非 L0 层通常只需定位一个候选文件；同一 user key 的内部版本跨文件边界等实现细节，可能让“每层恰好一个文件”不再是严格上限。

Bloom Filter 只回答“肯定不在集合里”或“可能在”。 正确构造和使用时没有假阴性，但可能误报；它既不返回 value，也不判断事务可见性。带旧版本或删除标记的 key 仍可能让过滤器返回阳性。11

4.3 范围扫描的区别

B+Tree 定位到第一个满足下界的叶子条目后，沿叶子页向右扫描，直到越过上界。若扫描二级索引还要访问行数据，回表可能成为主成本；叶子逻辑相邻也不保证磁盘物理相邻。

LSM 则为相关 MemTable 与 sorted run 建立迭代器，分别 seek 到下界，再做多路归并：取最小 key，收集该 key 的版本，选出当前读视图可见的值，跳过被删除的 key，再推进迭代器。上面的 [10, 30] 扫描在最新视图只输出两条，但可能检查超过两条物理记录。

普通的整 key Bloom Filter 不能直接证明任意范围里都没有数据；前缀过滤器可优化符合前缀约束的扫描，不等于所有范围查询都有同样效果。4、11

5.1 Leveled 与 Tiered 的差别

Leveled Compaction 会选择某层的一些文件，与下一层 key 范围重叠的文件归并，再把输出切成新文件。这样控制层内重叠，但上层的小批更新可能带动下层大量已有数据重写。没有重叠且满足其他条件时，有些文件可以只做元数据上的迁移，不必重写内容。6

Tiered / Size-tiered 倾向于积攒多个大小相近的有序段，再一起合成更大的段，减少反复把小段并入大段的重写；查询却可能需要检查更多段，也常需要更大的临时磁盘余量。RocksDB 的 Universal 属于这一类，不能把它的参数和所有系统的 Size-tiered 规则视为完全相同。7

5.2 删除标记为什么不能随便丢

继续使用上一节的 key 和序列号。假设快照 S101 已释放，合并只覆盖图中的 L0 与 L1；未参与的 L2 里还有 20@101=X。

回收必须同时守住两个条件：

1. 不能破坏活跃快照。 若 S101 仍存在，10@100=A 和 20@101=X 仍可能被它读取，不能仅因出现新版本就删除。
2. 不能让合并范围外的旧值重新可见。 即使没有旧快照，只要更深层还可能有被删除标记遮蔽的值，就要保留标记，或把相关数据纳入能证明安全的清理过程。

“只有到最底层才可以删除”是一种保守记法，不是所有实现的必要条件。对普通点删除，若能证明更深层相关范围没有旧值，也可能更早丢弃标记。反过来，即使已到最底层，活跃快照仍可能阻止旧版本清理。8、12

5.3 合并赶不上写入，会怎样

待刷盘 MemTable、L0 文件或待合并字节不断累积，内存、读放大和磁盘占用随之上涨。RocksDB 会触发减速甚至 write stall（暂停写入），让后台维护有机会追上。13

加大缓冲区或调高暂停阈值，可以吸收短时突发，不能解决长期输入速率高于处理能力的问题。增加合并线程也只有在 CPU、存储队列和带宽仍有余量时才可能有效；否则只是让前台读和后台合并竞争得更激烈。

6.1 WAL 约束的是持久化顺序

典型可变页 B+Tree 引擎采用 write-ahead 规则：数据页的某次修改持久化之前，能够恢复该修改的日志必须先持久化。 这不要求每次修改内存页之前都单独同步一次日志，也不要求提交时把所有脏页刷盘。14

LSM 的 MemTable 同样易失。启用 WAL 后，恢复可以重放尚未反映在有效 SST 集合中的更新；只把更新放进内存并不能保证掉电不丢。两类引擎都可用 group commit 让多个写入共享一次日志同步，从而摊薄成本。

上述同步保证还依赖操作系统、文件系统和设备遵守持久化契约。本机日志同步不等于复制确认，也不等于备份。 比较性能时必须对齐这些边界。

6.2 崩溃发生在维护中间

B+Tree 页分裂涉及多个页和父子关系，日志与恢复协议必须能处理分裂中断。页写入也可能只完成一部分；例如 PostgreSQL 的 full_page_writes 会在 checkpoint 后第一次修改页面时，把完整页写入 WAL，避免仅靠局部修改日志无法恢复撕裂页的问题。16

LSM 合并必须先可靠完成新输出，再可靠记录文件集合变更，最后安全回收旧文件。读者只应该看到一个一致的文件集合。SST 不可变简化了单文件并发访问，但没有消除文件发布和恢复的复杂度。9、10、14

6.3 Latch、事务锁和 MVCC 是三件事

Latch 保护内存中的页或共享结构不被并发修改破坏，通常持有很短；事务锁约束逻辑读写冲突；MVCC 决定某个读视图能看到哪个版本。能一致地读取一个页，不代表已经实现事务隔离。

B+Tree 的分裂不能要求所有读者等待整棵树重建。PostgreSQL 的 B-link 风格实现用页的 high key 和右兄弟指针帮助搜索在遇到并发分裂时继续向右定位，读取单页时仍需保护共享缓冲区。10

LSM 的不可变 SST 不需要对原记录做页内修改，但仍要协调 MemTable 写入、序列号发布、版本集合切换与旧文件回收。RocksDB 另外提供悲观和乐观事务接口；普通 Get 后 Put 不是自动的原子读改写，快照也不自动提供可串行化隔离。8、15

7.1 写放大：每写入 1 B，设备收到多少 B

引擎写放大 WA = 观察窗口内引擎写出字节 / 应用逻辑写入字节

分子是否包含 WAL、索引、合并输出和元数据，必须写清楚。设备内部的 FTL 垃圾回收还会产生额外写放大，不能把数据库统计的写出量直接当成 NAND 写入量。压缩也会影响按字节计算的比值。

B+Tree 的页粒度成本： 假设更新 100 B 最终独占一次 16 KiB 页写回，只计该数据页，比例为 16,384 / 100 ≈ 164。但如果同一页的 100 次修改合并成一次写回，这一项就降为约 1.64。WAL、其他页、索引和版本维护还没计入；不能拿这个假设当实测写放大。

LSM 的重写成本： 假设应用写入 1 GiB，窗口内 WAL 写出 1 GiB、flush 写出 1 GiB、compaction 写出 8 GiB，则上述口径的 WA 为 10。若这段时间只把数据堆在内存和 L0，数字会暂时偏低，后续合并会补上成本。Leveled 与 Tiered 的策略选择会直接影响这一项。6、7

7.2 读放大：候选文件不等于磁盘 I/O

读放大可以按探测的有序段数、物理读取字节或块读取次数计量。对不存在的 key，返回字节为零，用“读取字节 / 返回字节”没有意义，此时更适合看每次请求的 I/O 数和 CPU 时间。

假设一次 LSM 查空有 6 个候选 SST，每个过滤器的误报率都是 1%，过滤器和索引已在内存，且每次误报只触发一次数据块读取：

期望的额外数据块读取数 = 6 × 1% = 0.06 次 / 查询

这解释了 LSM 的查空为什么不一定慢。但 6 次过滤器探测及其 CPU 开销仍在，冷过滤器会增加元数据 I/O，真实数据布局也未必满足“一次误报只读一块”。RocksDB 文档给出的常用量级是约 10 bits/key 对应约 1% 的误报率，具体实现和规模会影响结果。11

7.3 空间放大：平时占用与维护峰值分开看

空间放大 SA = 实际占用的存储字节 / 当前逻辑存活数据字节

同样要说明压缩、索引、WAL 和副本是否计入。B+Tree 的来源包括未填满的页、碎片和未回收版本；LSM 的来源包括旧版本、删除标记、多个有序段，以及合并期间新旧文件同时存在。

Leveled 稳态下，如果层容量倍率为 T=10，各层恰好达到几何比例，则总容量相对最底层约为 1 + 1/10 + 1/100 + … ≈ 1.11。分母是最底层数据量，不是逻辑存活数据量，所以不能据此承诺“空间放大最多 1.11”。L0 积压、快照、压缩差异和合并临时文件都没有被这个公式覆盖。Universal 的全量合并甚至可能暂时同时保留接近一整份输入和一整份输出。6、7

7.4 复杂度只能解释结构，不能代替压测

B+Tree 点查的页面路径约为 O(log_F N)，F 为有效扇出；理想的叶子范围扫描还要加上输出所跨越的页数。LSM 的内存写入可能是 O(log M)，后台成本需要按整个合并周期摊销；查询成本取决于候选段、过滤器、缓存和版本数量，不能概括成“写 O(1)、读 O(log N)”。

对 k 路有序输入，使用堆归并的朴素扫描模型约需 O(P log k) 次比较，其中 P 是实际消费的物理条目数，不是最终返回条数；初始化 seek 和读取数据块的 I/O 另算。真实引擎可能优化迭代器切换，不能把模型当作实现的精确指令数。

更值得从 B+Tree 开始验证的负载

• 短范围扫描、排序分页、频繁索引定位，并且希望扫描路径尽量直接；先确认索引是否覆盖查询。
• 热数据能装入缓冲池的小幅反复更新，修改合并可以显著降低数据页写回量。
• 业务需要成熟的关系型数据库能力，现有 PostgreSQL / MySQL 已满足要求；不要只为“LSM 写得快”重做 SQL、约束和运维能力。

更值得从 LSM 开始验证的负载

• 大量超出缓存工作集的随机键写入，普通 Put 不必先读取旧数据页，批量落盘可能更有利。
• 持续摄入的 KV、状态存储或写密集服务，且能预留合并 CPU、I/O 与磁盘余量。
• 应用本来就需要嵌入式有序 KV 引擎，能够自行负责上层数据模型、事务使用方式和备份策略。

这些是起点，不是判决。读多的服务可能因 Bloom Filter 和缓存而在 LSM 上表现很好；写多的业务也可能受益于 B+Tree 的热页更新合并。读写比例相同，key 分布、记录大小、索引数量不同，结论就可能反转。

9.1 一次有意义的基准测试要固定什么

1. 数据模型：key / value 长度分布、压缩率、存活数据量、二级索引数量、比较器与排序规则。
2. 访问模式：插入 / 覆盖更新 / 删除比例，均匀随机或热点分布，查空比例，扫描长度与并发数。
3. 同等语义：日志是否开启、何时同步、批量大小、隔离级别、复制确认策略。不能用异步 KV 写入对比同步 SQL 事务。
4. 同等资源：总内存而非单个缓存参数，设备与文件系统、CPU、后台线程预算、磁盘剩余空间。
5. 足够长的阶段：预装数据、热身，再运行到树或 LSM 层级充分形成；混合更新与删除必须覆盖足够多的维护周期。
6. 真实的负载施加方式：记录发送速率、完成速率、超时与排队时间。只看阻塞客户端的平均响应，可能漏掉拥塞时本应到达的请求。

如果 L0 文件数或待合并字节持续增长，当前吞吐就是在积累维护任务，不能当作长期能力。B+Tree 也要观察脏页与清理积压，不能只跑一个全缓存、无清理压力的短测试。13

9.2 至少输出这组结果

• 吞吐与 P50 / P95 / P99 延迟，分别统计读、写、扫描，不只给一个平均值。
• 应用写入量、WAL / flush / compaction 写出量或数据页写回量，说明写放大的口径。
• 总内存、CPU、物理读写量、缓存命中率、磁盘占用的稳态值与峰值。
• 缺页、锁与 latch 等待、日志同步延迟；LSM 额外记录 L0 数量、pending compaction bytes 和 stall 时长。
• 长快照、持续删除、突发写入与后台维护并存时的退化，以及恢复正常所需时间。

9.3 从症状追到资源，不直接调旋钮

9.4 恢复测试与吞吐测试同样必要

在独立测试环境中，对写入、页分裂、flush、compaction 和文件发布过程注入故障。重启后验证：承诺持久化的写入仍在，原子批次没有部分生效，删除数据没有复活，范围扫描符合参考模型。测试设备 I/O 失败和空间耗尽时，确认引擎报错且不错误地返回成功。

只杀进程不足以测试掉电持久性，因为操作系统缓存仍然存在。系统崩溃、撕裂写和掉电场景需要相应的故障注入或隔离测试环境；不要在生产数据上做破坏性验证。

以下均为实现方文档或源码说明，核对日期为 2026 年 9 月 11 日。MySQL 采用 8.4 文档，PostgreSQL 采用 17 文档；RocksDB Wiki 持续更新，参数默认值与细节应再对照实际部署版本。文中的算式与数字示例为明确假设下的推导，没有跨引擎性能倍数的实测主张。

建议先读 3、4 建立模型，再读 6、10、12 深挖实现。 图示均为本文绘制，未复用来源中的图片。

1. MySQL 8.4：Clustered and Secondary Indexes

   。聚簇索引、二级索引中的主键与回表路径。

2. MySQL 8.4：The Physical Structure of an InnoDB Index

   。默认页大小、填充、顺序插入与合并阈值。

3. PostgreSQL 17：B-Tree Implementation

   。推荐起点，页结构、递归分裂、MVCC 版本造成的索引维护与回收。

4. RocksDB Overview 。推荐起点，MemTable、WAL、SST、快照、写入同步与缓存的整体关系。

5. RocksDB BlockBasedTable Format

   。数据块、索引、过滤器和 footer 的职责。

6. RocksDB Leveled Compaction

   。层内有序段、重叠范围合并与动态层容量。

7. RocksDB Universal Compaction

   。Tiered 思路、读写与空间取舍，以及全量合并的临时空间。

8. RocksDB Snapshot 。序列号可见性、快照生命周期与合并时的版本保留。

9. RocksDB MANIFEST 。一致文件集合、Version Edit 与 CURRENT。

10. PostgreSQL 17：nbtree README

    。深入阅读，B-link 并发、high key、兄弟指针与字节级分裂策略。

11. RocksDB Bloom Filter 。误报率、过滤器内存预算与整 key / 前缀过滤的边界。

12. LevelDB Implementation 。深入阅读，较小实现中的文件生命周期、合并范围和点删除标记回收条件；其中历史参数与硬件数字不作为本文性能依据。

13. RocksDB Write Stalls 。待刷盘表、L0 和待合并字节触发的背压。

14. PostgreSQL 17：Write-Ahead Logging

    。日志先于数据持久化、REDO 与分组同步。

15. RocksDB Transactions。悲观 / 乐观事务、原子 WriteBatch 与读写冲突保护。

16. PostgreSQL 17：full_page_writes

    。部分页写入的风险，以及完整页 WAL 记录的用途。