用户传入的 key 叫做 user key，但 LevelDB 内部从不直接存储 user key。每次 Put 或 Delete 操作都会被分配一个全局递增的 SequenceNumber，然后与一个 ValueType（kTypeValue = 0x1 表示正常写入，kTypeDeletion = 0x0 表示删除）一起，追加在 user key 后面，组成 InternalKey。具体来说，SequenceNumber 占 56 bits，ValueType 占 8 bits，两者合并成一个 uint64 拼在 user key 尾部。
排序时，InternalKeyComparator 先用 user comparator 比较 user key 部分，如果相同，则 SequenceNumber 更大的排在前面。这个排序规则非常关键——它意味着对于同一个 user key，最新的版本总是最先被找到。后续我们会反复看到这条规则如何贯穿 Get 流程、Iterator 遍历和 Compaction 中的丢弃逻辑。
用于查找的 LookupKey 则在 InternalKey 前面再加上一个 varint32 编码的长度前缀。查 MemTable 时用完整的 LookupKey（因为 MemTable 的 entry 格式就带长度前缀），查 SSTable 时用去掉长度前缀的 InternalKey 部分。
InternalKey
user_key bytes ... tag(8B, little-endian)
+----------------------------------+--------------------------------------+
| user_key | sequence(56 bits) | type(8 bits) |
+----------------------------------+--------------------------------------+
tag = (sequence << 8) | type
InternalKeyComparator 排序规则：
1) user_key 升序
2) sequence 降序（同一个 user_key 最新版本排最前）
LookupKey（MemTable 查找用）
+-------------------+--------------------------------------+
| varint32(key_len) | InternalKey（不含长度前缀本体） |
+-------------------+--------------------------------------+
MemTable 是写入路径上最先接触的数据结构。所有 Put 和 Delete 操作都会先写入当前活跃的 MemTable。当它的大小达到 write_buffer_size（默认 4MB）时，会被转为只读的 Immutable MemTable，同时创建一个新的空 MemTable 继续接收写入。因此，在任意时刻，内存中最多同时存在两个 MemTable：一个正在写，一个等待被 dump 到磁盘。
把 MemTable / Immutable MemTable / Flush 的关系放在一张图里更直观：
Put/Delete
|
+--> WAL（顺序追加） -------------------------------> disk
|
+--> MemTable（mutable, SkipList）
|
| 达到 write_buffer_size
v
Immutable MemTable（read-only, 等待 flush）
|
| Minor Compaction（dump）
v
SSTable（Level-0 / Level-1 / Level-2 ...）
约束：任意时刻内存最多两个 MemTable（一个 mutable + 一个 immutable）
MemTable 的底层实现是一棵 SkipList。LevelDB 没有选择红黑树或 B 树，而是选择了实现更简单、在随机写场景下性能相当的跳表。跳表可以看作是在一条有序链表上叠加了若干层”快速通道”——每一层都是下一层的子集，查找时从最高层开始向右走、向下走，逐步逼近目标。每个新节点的高度由随机函数决定（每层有 1/4 的概率升到上一层，最高 12 层），这种概率性平衡使得插入操作不需要像红黑树那样做旋转调整。
跳表的“向右走/向下走”的查找过程，可以粗略画成这样：
level 3: head ---------------------------> [k7] -------------------------> nil
level 2: head ---------> [k3] -----------> [k7] ------------> [k9] -----> nil
level 1: head -> [k1] -> [k3] -> [k5] -> [k7] -> [k9] ------------------> nil
level 0: head -> [k1] -> [k2] -> [k3] -> [k4] -> [k5] -> [k6] -> [k7] -> ...
查找：从最高层 head 开始 → 能向右就向右 → 不能再向右就下到下一层 → 直到 level 0
插入：随机决定节点高度（出现在哪些 level），只改动这些 level 的 next 指针
template<typename Key, class Comparator>
class SkipList {
struct Node {
Key const key;
std::atomic<Node*> next_[1]; // 柔性数组，实际长度 = 节点高度
};
Node* const head_; // 哨兵头节点，高度 = kMaxHeight
std::atomic<int> max_height_;
Comparator const compare_;
Arena* const arena_; // 内存分配器
};
跳表有一个对 LevelDB 极为友好的特性：由于 InternalKey 中包含 SequenceNumber，不可能出现两个完全相同的 key，所以永远不需要更新已有节点，也永远不需要删除节点（Delete 操作只是插入一条 kTypeDeletion 类型的新记录）。这意味着跳表的并发控制可以极大简化——只需要对节点指针使用 std::atomic 的 release/acquire 语义就够了，写线程插入时不需要加锁就能保证读线程的安全。
MemTable 中每条数据的存储格式是：key_size(varint32) | internal_key(key_size) | value_size(varint32) | value(value_size)。所有数据都分配在 Arena 上。Arena 是一个非常简单的内存池：每次按 4KB 的 block 向系统申请内存，小分配请求在当前 block 内顺序切割，大于 1KB 的请求直接 malloc。Arena 不支持释放单个对象——整个 MemTable 生命周期结束时，Arena 析构，一次性归还所有内存。这种设计既简单又高效，因为 MemTable 本身就是一个”只进不出”的数据结构。
当 Immutable MemTable 被 dump 到磁盘，或者 Compaction 产生新的输出文件时，数据就以 SSTable（Sorted String Table）的格式持久化。SSTable 是 LevelDB 中最精心设计的数据格式之一，它在一个只读文件中同时容纳了数据和索引，使得对任意 key 的点查只需要最多一次磁盘 I/O（假设索引信息已在缓存中）。
Block：SSTable 的基本单元。 SSTable 内部的数据以 Block 为单位组织。每个 Data Block 大约 4KB（由 block_size 配置），是读写磁盘的最小粒度。Block 内部的设计兼顾了空间效率和查找速度。
Block 内的 entry 采用前缀压缩来节省空间。因为 key 是有序的，相邻 key 往往共享很长的前缀。每个 entry 存储的不是完整的 key，而是 shared_bytes | unshared_bytes | value_bytes | delta_key | value——shared_bytes 表示与前一个 key 相同的前缀长度，unshared_bytes 是本条 key 独有的后缀长度，delta_key 就是那段后缀。这样一来，如果前后两个 key 只有最后几个字节不同，就能省下大量空间。
但前缀压缩也带来了一个问题：要还原任意一个 key，必须从某个起点开始顺序回放。如果每次查找都要从 Block 头开始遍历，代价就太高了。LevelDB 的解决方案是设置 restart point。每隔 block_restart_interval（默认 16）个 key，就重新开始一轮前缀压缩——该 key 的 shared_bytes 为 0，存储完整的 key。所有 restart point 的偏移量记录在 Block 末尾的 restarts 数组中。查找时，先对 restarts 数组做二分查找定位到目标所在的压缩区间，然后在区间内顺序扫描，最多遍历 16 个 entry。
一个小例子（用 restart_interval = 4）能把 restart point 的意义讲清楚：
keys（有序）：
apple:0001
apple:0002
apple:0003
apple:0004 <- 前 4 个是一组
banana:0001 <- restart（shared=0，存完整 key）
banana:0002
banana:0003
banana:0004
Block 里存储（概念化）：
entry0: shared=0 unshared="apple:0001" <- restart
entry1: shared=6 unshared="0002"
entry2: shared=6 unshared="0003"
entry3: shared=6 unshared="0004"
entry4: shared=0 unshared="banana:0001" <- restart
...
restarts[] = [offset(entry0), offset(entry4), ...]
查找：先二分 restarts[] 定位到 entry4 这一组，再在组内最多顺扫 4（一般是 16）个 entry
Block 的完整布局如下：
[entry0] [entry1] ... [entryN]
[restart0(uint32)] [restart1(uint32)] ... [restartM(uint32)]
[num_restarts(uint32)]
[compression_type(1B)] [crc32(4B)] ← trailer，不计入 BlockHandle 的 size
SSTable：由多个 Block 组成的完整文件。 一个 SSTable 文件从头到尾的布局是：若干 Data Block，然后是 Meta Block（当前版本未实质使用），MetaIndex Block，Index Block，最后是固定 48 字节的 Footer。
SSTable 文件布局（从文件头到文件尾）
+-----------+-----------+-----+-----------+-----------+--------+
| DataBlk 0 | DataBlk 1 | ... | MetaIndex | IndexBlk | Footer |
+-----------+-----------+-----+-----------+-----------+--------+
^ ^
| |
BlockHandle(metaindex) BlockHandle(index)
读取：先读 Footer（固定 48B）→ 解出 IndexBlk 位置 → 把 IndexBlk 常驻内存
点查：IndexBlk（二分）→ 定位 DataBlk → 读 DataBlk（缓存/磁盘）→ Block 内 restart 二分+顺扫
Index Block 是 SSTable 的”目录”。它本身也是一个标准的 Block，只是每个 entry 对应一个 Data Block：key 是该 Data Block 的 end-key（准确地说是通过 FindShortestSeparator 计算出来的一个尽量短的分隔键，大于当前 Block 最后一个 key，小于下一个 Block 第一个 key），value 是该 Data Block 的 BlockHandle（offset + size 的 varint 编码）。这个分隔键的设计是一处精妙的优化——它使得 Index Block 中存储的 key 尽可能短，减小索引占用的空间，从而让 Index Block 更容易整个放入内存。
Footer 位于文件末尾，长度固定为 48 字节，包含 MetaIndex Block 和 Index Block 的 BlockHandle，以及一个 8 字节的 magic number 用于校验。读取 SSTable 时，先从文件末尾读 Footer，从中解出 Index Block 的位置，再读出 Index Block 加载到内存——这就是 Table::Open() 做的事情。从此以后，这个 SSTable 的所有点查和范围扫描都可以先在内存中的 Index Block 里二分定位目标 Data Block，再做一次磁盘 I/O 读取该 Data Block。
LevelDB 为 SSTable 的元信息提供了 TableCache（key 是文件的 FileNumber，value 是打开的 Table 句柄和 Index Block），为 Data Block 提供了 BlockCache（key 是 cache_id + block_offset，value 是解压后的 Block 数据）。两级缓存协同工作：一次热点 key 的 Get，可能完全命中缓存，零次磁盘 I/O。
两级缓存（概念）
TableCache: file_number -> (Table 句柄 + Index Block)
BlockCache: (cache_id, block_offset) -> Data Block（解压后内容）
常见命中路径：
Get -> TableCache 命中 -> IndexBlock 在内存 -> BlockCache 命中 -> 0 次磁盘 I/O
LevelDB 将所有对数据的遍历访问统一抽象为 Iterator 接口：Seek(key), SeekToFirst(), SeekToLast(), Next(), Prev(), Key(), Value()。这套接口之上，构建了一个层层嵌套的迭代器组合体系，是 LevelDB 中最优雅的设计之一。
最底层是 Block::Iter，它在一个 Block 内部操作。Seek 时先对 restarts 数组二分查找，再在 restart point 内顺序扫描。Next 就是按前缀压缩格式解析下一个 entry 并还原完整 key。Prev 比较麻烦——由于前缀压缩是单向的，Prev 需要回退到当前 entry 所在的 restart point，然后顺序扫描到目标位置。
往上一层是 TwoLevelIterator，它是 LevelDB 中复用度最高的组合迭代器。它的思想是：有一个 index iterator 和一个 data iterator，index iterator 的 Value() 能够定位到一个数据容器，然后用一个 hook 函数从这个容器构造出 data iterator。Seek 时先让 index iterator Seek 找到目标容器，再让 data iterator 在容器内 Seek 找到目标 key。TwoLevelIterator 被用在两个地方：一是作为单个 SSTable 的迭代器，index iterator 是 Index Block 的 Block::Iter，hook 函数是 Table::BlockReader（根据 BlockHandle 读取并缓存 Data Block，返回其 Block::Iter）；二是作为非 level-0 某一层所有 SSTable 的迭代器，index iterator 是 LevelFileNumIterator（在该层排序好的 FileMetaData 列表上做二分查找），hook 函数是 TableCache::NewIterator（打开 SSTable 并返回其 TwoLevelIterator）。也就是说，后者实际上是一个”三级迭代器”——LevelFileNumIterator → SSTable 的 TwoLevelIterator → Block::Iter。
再往上是 MergingIterator，也就是归并迭代器。它持有一组 child iterator，每次 Next 时在所有 child 的当前值中选最小的（FindSmallest），Prev 时选最大的（FindLargest）。MergingIterator 还维护了一个 direction 状态来优化：如果连续做 Next，只需要让上一次输出的那个 child 前进一步再重新选最小即可，不需要每次都重新 Seek 所有 child。
最外层是 DBIter，它包装了一个 MergingIterator，负责处理应用语义：跳过同一 user key 的旧版本、跳过已被删除的 key、以及按照 Snapshot 的 SequenceNumber 过滤数据。正向遍历时 FindNextUserEntry() 相对简单——遇到的第一个版本就是最新版本，如果它是 Deletion 就跳过整个 key 继续走。反向遍历时 FindPrevUserEntry() 比较复杂，因为对于同一 user key，最新版本排在前面（也就是反向遍历时最后才遇到），所以 DBIter 需要用 saved_key_ 和 saved_value_ 缓存中间结果，直到遇到不同的 user key 才能确定前一个 key 的最终状态。
整个 DB 的内部迭代器 NewInternalIterator() 把以下内容组装成一个 MergingIterator 返回：MemTable 的 SkipList Iterator、Immutable MemTable 的 SkipList Iterator、Level-0 中每个 SSTable 各自的 TwoLevelIterator（因为 Level-0 的文件之间可能有 key 范围重叠，必须独立参与归并）、Level-1 到 Level-6 每层各一个 TwoLevelIterator（同层文件不重叠，可以用一个组合迭代器表示整层）。这棵迭代器树就是 LevelDB 读取路径的骨架。
把这棵“迭代器树”画出来会更清晰：
DBIter（处理 Snapshot / 去重 / 删除语义）
|
v
MergingIterator（全局归并）
|
+-- MemTable::Iter
+-- ImmutableMemTable::Iter
+-- Level-0: TableIter(file#N) TableIter(file#N-1) ...（每个文件一个 child）
+-- Level-1+: TwoLevelIterator（每层一个 child）
|
+-- index iter: LevelFileNumIterator（在该层文件元数据上二分找目标文件）
+-- data iter: TableIter（目标文件内部又是 IndexBlk -> DataBlk 的 TwoLevel）
写路径。 用户调用 DB::Put(key, value) 或 DB::Delete(key) 后，内部将操作封装成 WriteBatch。WriteBatch 可以包含多个 Put/Delete 操作，它们共享同一批 SequenceNumber（从 batch 的起始 sequence 开始递增），保证原子性。
写入的第一步是检查当前 DB 的状态，这由 MakeRoomForWrite() 负责。它实现了一套精心设计的流控策略：如果 Level-0 的文件数量达到 kL0_SlowdownWritesTrigger（默认 8），写线程会 sleep 1ms 来减速（只触发一次）；如果 MemTable 还没满，直接放行；如果 MemTable 已满但 Immutable MemTable 还在等待 dump，写线程阻塞等待 Compaction 完成；如果 Level-0 文件数达到 kL0_StopWritesTrigger（默认 12），也阻塞等待；如果以上都不满足（MemTable 满了、没有 Immutable），则将当前 MemTable 转为 Immutable，创建新 MemTable 和新 WAL 文件，触发 Compaction，然后放行。
通过流控后，先将 WriteBatch 的数据追加到 WAL 日志文件（log::Writer::AddRecord），然后遍历 WriteBatch 中的每个操作，逐条插入 MemTable 的 SkipList。最后更新全局 SequenceNumber。整个写路径没有任何磁盘随机 I/O——WAL 是顺序追加写，MemTable 是纯内存操作。
写路径（把随机写变顺序写）
Put/Delete
|
v
WriteBatch（分配 sequence）
|
v
MakeRoomForWrite（流控/等待 Compaction）
|
+--> WAL append（顺序写）
|
+--> MemTable insert（内存 SkipList）
|
v
（后台）Immutable -> dump -> SSTable -> VersionEdit -> MANIFEST
读路径。 DB::Get(key) 的过程是一次从新到旧的搜索。首先确定 SequenceNumber 上界：如果 ReadOptions 指定了 Snapshot，就用 Snapshot 的 sequence；否则用当前最新的 last_sequence。然后构造 LookupKey（user_key + sequence），按以下顺序依次查找，找到就返回：
在当前 MemTable 中查找。SkipList 的 Seek 定位到第一个 >= LookupKey 的 entry，如果 user key 匹配，检查 ValueType——是 kTypeValue 就返回 value，是 kTypeDeletion 就返回 NotFound。
在 Immutable MemTable 中查找（如果存在的话），逻辑同上。
在磁盘上的 SSTable 中逐 level 查找（Version::Get）。对于 Level-0，因为文件之间可能重叠，需要先找出所有 key 范围覆盖目标 key 的文件，按 FileNumber 从大到小排序（越新的文件越先查），然后逐个在文件中查找。对于 Level-1 及以上，每层的文件不重叠且按 key 排序，所以可以对 files_[level] 基于 FileMetaData::largest 做二分查找，最多定位到一个文件。
在 SSTable 内部查找时，先在内存中的 Index Block 里二分找到目标 key 可能所在的 Data Block，然后通过 Table::BlockReader 从 BlockCache 读取（未命中则从磁盘读取并加入缓存），最后在 Data Block 内用 restart point 二分 + 顺序扫描找到目标 key。
读路径（从新到旧）
Get(user_key, snapshot_seq)
|
+-- MemTable（mutable）
+-- Immutable MemTable（如果存在）
+-- Level-0（可能多个文件重叠：挑出覆盖范围的文件，按 FileNumber 新到旧查）
+-- Level-1..6（每层文件不重叠：二分最多定位到一个文件）
|
v
SSTable 查找：IndexBlk（二分） -> DataBlk（缓存/磁盘） -> restart（二分+顺扫）
读路径有一个巧妙的副作用：如果一次 Get 在某个 SSTable 中做了无效查找（key 不在该文件中），LevelDB 会将该文件的 allowed_seeks 减一。allowed_seeks 的初始值约等于 file_size / 16KB，它的含义来自一个成本估算——一次磁盘 seek 的代价约等于 compact 40KB 数据的代价，当一个文件被无效 seek 的次数超过阈值，说明它的 key 范围分布不够合理，应该被优先 compact。当 allowed_seeks 降到 0，该文件会被标记为 file_to_compact_，在下一次 Compaction 中被选中。
WAL（Write-Ahead Log）保证了写入的持久性。即使进程崩溃，重启后也能通过回放 WAL 恢复 MemTable 中尚未 dump 到 SSTable 的数据。
WAL 和 MANIFEST 共用同一套 log 文件格式，这是 LevelDB 中一处很聪明的复用。文件被划分为固定大小（32KB）的 Block，每个 Block 内包含若干 Record。每条 Record 的格式是：checksum(4B) | length(2B) | type(1B) | data(length)。type 有四种取值：FULL 表示一条完整的记录，FIRST / MIDDLE / LAST 表示一条记录跨越了多个 Block 时的首段、中间段和末段。如果一个 Block 剩余空间不足 7 字节（Record 头部大小），就填充全零作为 trailer，Record 写入下一个 Block。
WAL / MANIFEST 的 log 文件切块方式（32KB）
Block 0 (32KB) Block 1 (32KB)
+----------------------------+ +----------------------------+
| [Record FULL] [Record...] | | [Record FIRST][Record MID] |
| ... padding(0...) | ---> | [Record LAST] padding |
+----------------------------+ +----------------------------+
说明：
- 单条 Record 可能跨多个 Block：FIRST/MIDDLE/LAST 串起来才是一条逻辑记录
- Block 剩余空间不足写 header（7B）时，用 0 填充到块尾（trailer）
写入 WAL 时，每次 WriteBatch 作为一条 Record 追加写入。是否在写入后立即 fsync 由 WriteOptions::sync 控制——默认不 sync，靠操作系统的 page cache 缓冲，这意味着进程崩溃时可能丢失最后几次写入；设置 sync = true 则每次写入后都 fsync，绝对安全但代价是每次写入都有一次磁盘同步。
DB 重启时的恢复流程是：先从 MANIFEST 中恢复出上次关闭前的 Version 状态，然后找到比 MANIFEST 中记录的 log_number 更新的 WAL 文件，逐条回放其中的 Record，重建 MemTable。如果重建过程中 MemTable 达到阈值，就顺便 dump 成 SSTable。最后将残留的 MemTable 也 dump 掉，生成新的 WAL 和 MANIFEST，启动完成。
如果说 WAL 保护的是 MemTable 中的数据，MANIFEST 保护的就是 DB 的”结构”——每一层有哪些 SSTable 文件、当前的 SequenceNumber 和 FileNumber 是多少、每一层下次 Compact 从哪个 key 开始。
LevelDB 中，DB 在某一时刻的完整状态用 Version 表示。每个 Version 记录了各 level 上所有 SSTable 的 FileMetaData（file number、file size、smallest key、largest key）。每次 Compaction 完成后会产生一个新的 Version——某些文件被删除，某些新文件被加入。为了不丢失历史版本（可能有正在进行的读操作引用着旧 Version），所有活跃的 Version 通过双向链表组织在 VersionSet 中，并使用引用计数管理生命周期。当一个 Version 的引用计数降为 0 且它不是 current 时，就可以安全删除，其中独有的 SSTable 文件也可以被清理。
Version 之间的差异用 VersionEdit 表示，它记录了”要删除哪些文件、要新增哪些文件”，以及 log_number、next_file_number、last_sequence 等元信息的更新。应用一个 VersionEdit 到当前 Version 上就得到新 Version，这个过程由 VersionSet::Builder 完成——它以 base Version 的 files_[level] 为基础，合入 VersionEdit 中的增删操作，输出新 Version 的 files_[level]。
MANIFEST 文件的格式就是上文提到的 log 格式。文件开头写入一条包含完整状态的 VersionEdit 作为基线快照（VersionSet::WriteSnapshot），之后每次 Compaction 完成时追加一条增量 VersionEdit。DB 重启时，先读取基线快照，然后依次 replay 后续的 VersionEdit，就能恢复出退出前的 Version 状态。CURRENT 文件则简单记录当前使用的 MANIFEST 文件名，是整个恢复链的入口。
Version / VersionEdit / MANIFEST（概念关系）
CURRENT ---> MANIFEST-000xyz
MANIFEST 内容：
[VersionEdit: snapshot（全量基线）]
[VersionEdit: delta] [delta] [delta] ...
VersionSet（内存）：
Version(prev) <-> Version(current) <-> Version(next) ...
（读请求可能持有旧 Version，所以需要链表 + 引用计数）
每次生效新 Version 时（VersionSet::Finalize），还会计算出两个关键的 Compaction 调度参数：compaction_score_ 和 compaction_level_。对于 Level-0，score = 文件数 / kL0_CompactionTrigger（默认 4），因为 Level-0 文件可能重叠，文件数量直接影响读性能。对于 Level-1 及以上，score = 该层总文件大小 / 该层的容量配额（Level-1 的配额是 10MB，之后每层乘 10）。score 最大的那一层就是最需要被 Compact 的层。
Compaction 是 LevelDB 中最复杂的子系统。它负责两件事：将 Immutable MemTable dump 成 Level-0 的 SSTable（Minor Compaction），以及将不同 level 之间的 SSTable 归并整理（Major Compaction）。整个 DB 只有一个后台 Compaction 线程。
Level 结构（示意）
Level-0: [---f1---] [--f2--]
[----f3----] （允许重叠，读时可能要查多个文件）
Level-1: [--g1--][--g2--][--g3--]（不重叠，按 key 排序）
Level-2: [------h1------] [...]
Major Compaction（n -> n+1）：
选中 level-n 的一批文件（轮转） + level-(n+1) 中所有重叠文件
-> MergingIterator 归并遍历
-> 输出到 level-(n+1) 的新文件（并控制与 grandparent 的重叠量）
-> VersionEdit：删旧文件 + 加新文件
Minor Compaction 比较简单：遍历 Immutable MemTable 的 SkipList Iterator，将所有 entry 按序写入一个新的 SSTable（通过 TableBuilder），然后通过 PickLevelForMemTableOutput 决定这个 SSTable 应该放在哪一层。如果它的 key 范围与 Level-0 有重叠就只能放 Level-0；否则尝试推到更高的 level（最高到 Level-2，由 kMaxMemCompactLevel 限制），条件是不能与目标层或目标层的下一层有过多重叠。这个策略的目的是尽量减少 Level-0 的文件数量（Level-0 是读性能的最大瓶颈），同时避免推得太高导致后续 Compaction 代价过大。
Major Compaction 的触发有两个来源：一是 compaction_score_ >= 1（某一层的文件数量或大小超标），二是 file_to_compact_ 非空（某个文件的 allowed_seeks 耗尽）。前者优先级更高。选定要 Compact 的 level-n 后，PickCompaction 会选出参与的文件：在 level-n 中，选取 start key 大于该层上次 Compact 结束位置（compact_pointer_[n]）的第一个文件（这保证了同一层的 Compact 是轮转进行的，不会反复碾压同一段 key 范围）；然后在 level-(n+1) 中找出所有与 level-n 选出文件的 key 范围有重叠的文件。SetupOtherInputs 还会尝试在不扩大 level-(n+1) 参与范围的前提下，多拉入一些 level-n 的文件。
实际的归并由 DoCompactionWork 完成。它将所有参与的 SSTable 构建成一个 MergingIterator（Level-0 的文件各自作为一个 child，level-(n+1) 的文件集合作为一个 TwoLevelIterator child），然后从头到尾遍历。遍历过程中丢弃重复 key 的旧版本，丢弃已删除的 key（前提是该 key 在更高 level 中不存在，且不被任何 Snapshot 引用），将留存的 key-value 写入新的 level-(n+1) SSTable 文件。写入时还会监控与 level-(n+2)（grandparent）的重叠量，如果超过 kMaxGrandParentOverlapBytes（默认 20MB），就提前切换到下一个输出文件，避免将来 Compact level-(n+1) 时产生过多的读入量。
Compaction 完成后，产生的 VersionEdit（删除所有 input 文件，加入所有 output 文件）通过 LogAndApply 写入 MANIFEST 并生效为新的 current Version。然后清理废弃文件——遍历 DB 目录，删除不再被任何活跃 Version 引用的 SSTable 文件以及过期的 WAL 和 MANIFEST 文件。
Snapshot 的实现出乎意料地简单。一个 Snapshot 本质上就是创建时刻的 SequenceNumber，所有 Snapshot 通过一个双向链表按照 sequence 从小到大排列。
创建 Snapshot：取当前 last_sequence，包装成 Snapshot 节点插入链表。 使用 Snapshot：将它的 sequence 作为 Get 或 Iterator 的 SequenceNumber 上界，这样就只能看到 Snapshot 创建之前的数据。 对 Compaction 的影响：当 Compaction 遇到一个 kTypeDeletion 的 entry 时，不能简单丢弃——如果存在某个 Snapshot 的 sequence 介于该 delete 和它之前的 put 之间，这条 delete 记录就必须保留，否则那个 Snapshot 看到的数据就会变。具体的判断是：如果 entry 的 sequence <= 所有活跃 Snapshot 中最小的 sequence，才可以安全丢弃。
Snapshot（按 sequence “定格”视图）
sequence 增长方向 ------------------------------------------------------->
Put(k) seq=40
Put(k) seq=41
Snapshot S(seq=41) <- 读到这里为止
Delete(k) seq=42
Compaction 遇到删除标记时：
- 如果它可能影响某个活跃 Snapshot 的可见性，就必须保留
- 只有当 entry.sequence <= min_snapshot_sequence 才能安全丢弃旧版本/删除标记
最后，让我们把所有模块串起来，跟踪一条数据从写入到被读取的完整旅程。
一次 Put / Get 的端到端路径（高度概括）
Put/Delete
|
+--> WAL（顺序写，崩溃可恢复）
|
+--> MemTable（SkipList）
|
| full
v
Immutable MemTable
|
v
SSTable (L0) --compaction--> (L1..)
Get
|
+--> MemTable -> Immutable -> L0 -> L1..（SSTable: IndexBlk -> DataBlk -> restart）
用户调用 Put("user_key", "value")。引擎将它封装为 WriteBatch，分配 SequenceNumber = 42，ValueType = kTypeValue。MakeRoomForWrite 检查通过后，WriteBatch 被序列化为一条 Record 追加到 WAL 文件的当前 Block。然后 MemTable 收到一条 entry：internal_key = "user_key" + pack(42, kTypeValue)，value = "value"，通过 SkipList::Insert 插入跳表。
经过许多次写入后，MemTable 达到 4MB。它被转为 Immutable MemTable，Compaction 线程被唤醒。线程遍历 Immutable MemTable 的全部 entry，通过 TableBuilder 写入一个新 SSTable 文件——先按 4KB 切成 Data Block（内部做前缀压缩），写入时同时构建 Index Block，最后写 Footer。根据 key 范围，这个 SSTable 被放到了 Level-0。VersionEdit 记录”新增 Level-0 文件 000042.ldb”，写入 MANIFEST，生效新 Version。旧的 WAL 可以被删除了。
又经过更多写入和 dump，Level-0 堆积了 4 个文件，compaction_score 超过 1。Compaction 线程选出 Level-0 中最早的一个文件和 Level-1 中有重叠的文件，构建 MergingIterator，归并排序后输出若干 Level-1 的新 SSTable。输出过程中，遇到同一 user key 的多个版本只保留最新的，遇到 kTypeDeletion 且无 Snapshot 引用的就丢弃。完成后更新 MANIFEST，删除旧文件。
这时用户调用 Get("user_key")。先查当前 MemTable 的跳表——没找到。查 Immutable MemTable——不存在。查 Level-0：对每个文件的 key 范围做检查，找到一个可能包含该 key 的文件，通过 TableCache 获取其 Index Block，二分查找定位到目标 Data Block，从 BlockCache 读取（或从磁盘读取后加入缓存），在 Block 内 restart point 二分 + 顺序扫描，找到 "user_key" + pack(42, kTypeValue)，ValueType 是 kTypeValue，返回 "value"。
这就是 LevelDB 的全貌。每一层设计都在做同一件事：把随机写变成顺序写，然后用各种索引、缓存和归并策略让读性能在可控范围内。代码简洁到几乎没有多余的抽象，每个类都有明确的职责。这也是为什么它不仅是一个实用的存储引擎，更是学习存储系统设计最好的入门教材之一。