LSM 树
LSM 树先持久记录变更，再把新版本放进内存，将磁盘上的排序与合并留给批处理。前台写入不必立刻重排最终存储位置，代价转移到后面：读取可能检查多个重叠文件，后台压实还会重写已有记录。
写入先追加，数据后整理。序列号与从新到旧的读取顺序，保证整理延后时仍返回正确版本。
写入：WAL、内存表与刷盘
每次 put 和 delete 都获得递增的序列号。操作先追加 WAL，再更新内存表。本课假设 WAL 追加同步持久化，因此 WAL 与内存更新完成后即可确认写入，无须等待 SSTable 改变。
内存表每个键最多保留一个当前记录。连续写两次键 20 会替换内存槽中的版本，不会占两个不同键位置；两次变更仍留在 WAL 中，直到该日志段可回收。删除沿同一路径写入墓碑，也就是删除标记，不会到旧文件中原地擦除记录。
不同键数量达到容量时，整代内存表转为不可变，新活动内存表与 WAL 随即开启。不可变表按键升序刷入 L0，与写入顺序无关。新 SSTable 安装完成后，才能回收封存的 WAL 段。
逐步演示
默认内存表容量为三个键，L0 达到两个文件时开始压实。操作为：
put 20 A, put 10 B, put 30 C, put 20 A2, get 20, delete 10, get 10, put 40 D, get 20
- 写入
20:A #1、10:B #2、30:C #3，每次都先 WAL 后内存表。第三个不同键冻结第一代。刷盘结果是有序的S1 = [10:B #2, 20:A #1, 30:C #3]。 - 用
A2 #4覆盖键 20。新版本在活动内存表，S1 仍存着20:A #1。 - 读取 20，先查内存，返回
A2 #4后结束，不再读取 L0 的旧值。 - 删除 10，写入墓碑
#5。S1 中的10:B #2保持不变，新可见版本是墓碑。 - 读取 10，在内存表命中墓碑后结束。如果把它当成“本层没有键”而继续查 S1，就会让 B 复活。
- 写入
40:D #6，第二代达到容量，刷出S2 = [10:DEL #5, 20:A2 #4, 40:D #6]。L0 两个文件范围重叠，开始压实。 - 合并 S1、S2，每个键选最大序列号。20 保留
A2 #4，丢弃A #1。10 选墓碑#5；本次完整合并覆盖所有更低层的重叠旧版本，输出到模型最底层，又没有快照，因此墓碑与B #2都可移除。30、40 保持有效。 - 一次安装新的 L1：
[20:A2 #4, 30:C #3, 40:D #6]。服务状态切换后，才回收旧 L0 输入。 - 再读 20。内存表与 L0 已空，由 L1 返回
A2 #4。
六次逻辑变更形成两次有序刷盘；压实读取六个存储版本，写出三个有效 L1 记录。
读放大、写放大与空间放大
前台承担 WAL 追加和内存表更新，刷盘与压实在后续执行。工作被推迟，并未消失。
- 读放大：模型没有 Bloom 过滤器、缓存或文件内索引，L0 未命中时要检查所有重叠文件，再查 L1。
- 写放大：压实会重新读写已有记录。默认轨迹的六个输入版本变成三个输出记录。
- 空间放大：旧值、墓碑与替代版本共存，直到压实证明旧版本可丢弃。
较大的内存表通常减少刷盘次数、增大单次输出。提高 L0 触发阈值会积累更多文件，推迟压实，也让没有过滤器的未命中查询检查更多来源。降低阈值则提早花费后台 I/O，缩短读取路径。画布统计记录与来源数量，不统计字节或耗时，不能据此推导生产调参公式。
何时采用 LSM 树
写入占主导、存储适合顺序批量输出、后台还有 CPU 与 I/O 预算时，LSM 是合适的选择。点查询通常需要辅助结构：Bloom 过滤器排除不可能含键的文件，稀疏索引定位候选块，块缓存减少设备读取。它们降低读放大的实际成本，并未取消版本与文件层次。
对读取敏感时，可以减少触发压实所需的 L0 文件数。反向调整能推迟后台工作，但未命中查询要多查来源。真实引擎的 L0 积压还可能加重压实压力或导致写入停顿，本课不模拟这些现象。
点查、范围扫描与有序页局部性更重要，且页内维护的代价可接受时，可考虑 B+ 树。持续写入的追加与批量整理更重要时，可考虑 LSM。
从新到旧读取
模型按以下顺序查找：活动内存表、从新到旧的 L0 SSTable、唯一的底层 L1。首次命中有效值或墓碑都立即结束。
来源顺序与记录序列号作用不同。读取按新来源优先，防止旧文件遮住近期更新；压实汇集同键的多个版本，按最大序列号选胜者。
在 Read amplification 预设中，三个 L0 文件尚未达到阈值四。get(99) 检查内存表和三个文件，合计四次逻辑来源探测。这不等于四次磁盘 I/O；过滤器、索引、缓存和块位置决定实际设备工作。
压实与墓碑安全
压实是有序多路归并。每个输入的头部暴露尚未消费的最小键。选择最小用户键，汇集该键的所有当前版本，再选最大序列号。有效胜者追加到新输出，旧版本丢弃。
墓碑需要额外条件：若未参与合并的低层文件仍有旧值，提前丢弃墓碑就会暴露旧值。本课只有在合并全部 L0、完整重叠 L1、目标为最底层且不存在快照时，才移除墓碑。超出这些条件，必须保留到旧版本无法再出现为止。
Tombstone safety 预设让 10:B #1 留在 L1，新 L0 中放 10:DEL #5。读取在墓碑处结束。若没有同时消费 L1 的旧值就删除墓碑，B 会再次可见。
构建中的 L1 不提供部分结果。完整输出一次安装后，旧输入才失效并回收，读者不会看到半成品。
复杂度
设 M 为活动内存表大小，F0 为重叠 L0 文件数，S 为每个 L0 文件记录数，L1 为底层记录数，N 为压实输入记录总数，k 为选中输入路数。
| 操作 | 本模型中的增长 | 原因 |
|---|---|---|
| 前台变更 | O(log M) 加 WAL 追加 | 先记日志，再更新有序内存表 |
| 点查询 | O(log M + F0 log S + log L1) | 内存、相关 L0 从新到旧、L1 |
| 内存表刷盘 | O(M) 输出 | 有序内存可按键遍历 |
| 常规 k 路压实 | O(N log k) | 堆选择下一个输入头 |
| 展示用归并 | O(Nk) | Python 为便于阅读扫描最多五个可见输入头 |
这些表达式描述访问增长，不承诺延迟。WAL 追加可能需要同步，SSTable 查找可能命中内存，生产系统还有块、过滤器、缓存、压缩与并行后台任务。
边界情况
- 首次刷盘前只有内存表一个来源，未命中需要一次逻辑探测。若某次压实删掉了所有键，它仍会装上一个空的 L1 run，此后的未命中也要探测它。
- 同代覆盖更新序列号和值，不增加不同键槽数。
- 达到容量即冻结，不是超过容量才冻结。
- 删除不存在的键仍写入带序列号的墓碑。它可遮住旧文件中的值；没有旧值时，满足条件的底层压实可回收它。
- 命中新 L0 文件即结束，不查旧重叠副本。
- 墓碑表示删除结果，不能继续向下查。
- 跨多文件的缺失键会在读取账本中展示每个来源。
- 画布最多 12 个当前用户键、20 次操作。这些是绘图限制，不是 LSM 容量或写入停顿阈值。
常见错误
- 从最旧 L0 开始查，让旧值遮住新值。
- 把墓碑当未命中，让删除的值复活。
- 压实选择第一个候选，而非最大序列号。
- 每次压实都删除全部墓碑，忽略未选中的旧重叠版本和快照。
- 输出安装前就回收输入，产生读取缺口或部分结果。
- 把 SSTable 重写当成前台写入确认的前提。默认轨迹先确认 WAL 与内存状态。
- 把来源探测次数当成物理 I/O 次数。
模型范围
这是串行、两层模型：同步持久 WAL，一个活动表、最多一个不可变表，重叠 L0 文件，一个完整 L1，向最底层做全范围压实。省略快照、Bloom 过滤器、稀疏索引和块索引、块缓存、压缩、校验和、manifest 与版本集合、恢复重放、并发写入、多后台任务、部分重叠选择、输出文件大小和写入停顿。LevelDB、RocksDB 类引擎的策略更细。此处墓碑回收只在轨迹展示的完整重叠、最底层、无快照条件下成立。