跳表与 LSM

• B-Tree 特点
• LSM 特点
• 读写权衡

B-Tree 与 LSM 的取舍：B-Tree 就地更新、读快（点查 O(log n)），但随机写需多次页 IO 与页分裂，写放大高，适合"读多写少"（如 OLTP、关系库）。LSM（Log-Structured Merge Tree）顺序写、写快（append 到 WAL + MemTable），但读需合并多级，读放大，适合"写多读少"（如时序、日志、KV 存储）。取舍：写少读多（点查多）用 B-Tree，写多读多（写入为主、容忍读成本）用 LSM。现代系统按负载选择。

B-Tree 读优写弱，LSM 写优读弱。选择取决于读写比例与查询模式。

• LSM 结构
• 内存表
• SSTable 合并

LSM 树写优化原理：所有写入先追加到 WAL（预写日志，持久化）与内存表（MemTable，有序结构），随后 MemTable 刷盘成 SSTable（有序字符串表，顺序写）。随着 SSTable 增多，后台进行合并（Compaction），把重叠的 SSTable 合并成更大的有序 SSTable，消除冗余、保持有序。写入是顺序追加（不随机写），因此写放大低、写吞吐高。读需查内存表 + 各级 SSTable（可能与 Bloom Filter 过滤）。LSM 用"先写内存、顺序刷盘、后台合并"优化写。

LSM 写优化核心：顺序写 + 内存缓冲 + 后台合并。写入快，读需合并多级。

• 跳表
• Redis SortedSet
• 有序集合

Redis 的 SortedSet（有序集合，ZSET）使用跳表（Skip List）作为底层实现之一（另一实现是 ziplist/紧凑编码）。跳表提供有序的键值存储，支持：按分数范围查询（ZRANGEBYSCORE）、按排名查询（ZRANGE）、插入/删除 O(log n)。跳表结构在 Redis 中用于 SortedSet 的高效有序操作，比平衡树实现简单、缓存友好。Redis 用跳表 + 哈希表组合：哈希表按成员 O(1) 查找，跳表按分数有序。跳表是 Redis SortedSet 的核心数据结构。

Redis SortedSet 用跳表实现有序、按分数范围查询，O(log n) 操作，实现简单。

• LevelDB
• RocksDB
• Cassandra

LSM 的典型实现：①LevelDB：Google 的嵌入式 KV 存储，LSM 结构，简单，单机；②RocksDB：Facebook 基于 LevelDB 优化，支持多列族、并发、性能强，是流行的嵌入式 LSM 引擎；③Cassandra：分布式 NoSQL，使用 LSM（SSTable + 合并），写优化、水平扩展；④HBase：基于 Hadoop 的分布式列数据库，LSM（HLog + MemStore + HFile/StoreFile），写优化。这些系统以 LSM 为核心实现高写入吞吐，适合写入密集场景。

LSM 被广泛用于写密集的 KV/NoSQL 系统。LevelDB/RocksDB 嵌入式，Cassandra/HBase 分布式。

• 写放大
• 读放大
• LSM

LSM 的写放大（Write Amplification）：实际写入磁盘的数据量 / 应用写入的数据量，因 Compaction 会重复读写数据（合并、重写），写放大 > 1。读放大（Read Amplification）：一次点查需读取的数据量/数据块数，因需查内存表 + 多级 SSTable，读放大随层级增加。LSM 以写放大与读放大为代价换取顺序写的高吞吐。写放大的主要来源是 Compaction，读放大靠 Bloom Filter 与缓存缓解。权衡写放大（压缩频率）与读放大（层级数）。

LSM 写放大源于 Compaction，读放大源于多级查询。需在压缩策略与 Bloom Filter 间权衡。

• Size-Tiered
• Leveled
• Universal

LSM 的 Compaction 策略：①Size-Tiered Compaction（大小分层）：把大小相近的 SSTable 合并成更大的，写放大低、读放大高，简单，适合写多读少（Cassandra 默认）；②Leveled Compaction（分层）：SSTable 分层（L0、L1...），每层大小固定增长，跨层合并，读放大低、写放大高，适合读多写少（RocksDB 默认）；③Universal Compaction：RocksDB 的优化，类似大小分层但合并更高效（合并全层），写放大低、空间放大低。选择权衡读放大、写放大、空间放大与实现复杂度。

Compaction 策略在"写放大 vs 读放大"间权衡：Size-Tiered 写优读弱，Leveled 读优写弱。

• 跳表原理
• 多层链表
• O(log n)

跳表（Skip List）由多层有序链表组成：底层包含所有元素，上层是稀疏的"跳跃"层（随机生成）。查找时从顶层开始，若当前节点值小于目标则向右，否则向下，逐层下探，平均 O(log n)。插入/删除也通过概率（抛硬币）决定层数，保持概率平衡。跳表实现简单、无需旋转（相比红黑树），且对缓存友好（更少指针跳跃）。平均 O(log n)，最坏 O(n)。Redis SortedSet 用它。跳表是概率性数据结构，用层级加速查找。

跳表用多层有序链表 + 概率层数实现 O(log n) 查找，实现简单、缓存友好。

• MemTable
• SSTable
• 架构

LSM 架构由内存与磁盘两层组成：①MemTable（内存表）：内存中的有序结构（如跳表），新写入先进入 MemTable，速度快；②SSTable（磁盘有序字符串表）：MemTable 满后刷盘成 SSTable，磁盘按序存储，不可变；③WAL：写入前先写 WAL 保证持久性。多个 SSTable 分层（L0、L1...），后台 Compaction 合并。查询先查 MemTable，再查各级 SSTable（配合 Bloom Filter）。架构核心是"写内存、刷磁盘、合并"。

MemTable 缓冲写入、SSTable 持久化有序存储，WAL 保证崩溃恢复，Compaction 合并。

• 抛硬币层数
• 概率平衡
• 平均/最坏复杂度

跳表插入时通过"抛硬币"（随机）决定新节点层数：每次 50% 概率升一层，形成高度为 k 的概率为 1/2^k。这种概率层数使期望层数 O(log n)，实现概率平衡（无需像红黑树那样旋转/着色）。查找/插入/删除平均 O(log n)（因层级稀疏性），最坏 O(n)（所有节点同层，退化为单链表，概率极低）。与红黑树相比：跳表实现更简单（无需旋转/父指针）、更易调试、对缓存更友好（插入时局部更新、指针更少）；红黑树最坏 O(log n) 保证但实现复杂。跳表是概率算法，红黑树是确定性算法。

抛硬币决定层数实现概率平衡，平均 O(log n)、最坏 O(n)。跳表实现简单、缓存友好，红黑树最坏有界但复杂。

• Compaction 触发
• 写入路径
• 写放大与延迟尖刺

LSM 的写入路径与 Compaction 需协同控制写放大与延迟尖刺：①WAL 组提交（group commit）：多个写入批量提交 WAL，减少 fsync 次数，降低写入延迟；②MemTable flush：MemTable 满后刷盘成 SSTable，flush 是写入路径的一部分，若 flush 频繁造成延迟尖刺，可调整 MemTable 大小；③Compaction 触发：当 SSTable 数量/层级达到阈值触发，Compaction 在后台进行，但可能占用 IO 导致延迟尖刺。协同：用更大 MemTable 减少 flush、用后台限流 Compaction（如 RocksDB 的 rate limiter）平滑 IO、规避 Compaction 与写入竞争。目标是平衡写放大与延迟稳定性。

WAL 组提交减少 fsync、MemTable 大小控制 flush、Compaction 限流平滑 IO，协同控制写放大与延迟尖刺。

• Bloom Filter
• Block Cache
• 点查与范围扫描

LSM 读路径用 Bloom Filter 与 Block Cache 控制读放大：①Bloom Filter：每个 SSTable 带一个布隆过滤器，点查某 key 时，先判断该 SSTable 是否能包含该 key，若否跳过该 SSTable，避免不必要的磁盘 IO（把不存在的 key 的磁盘访问降到零）；②Block Cache：缓存热数据块，减少重复读盘。点查（Point Lookup）：用 Bloom Filter 过滤 + 逐级查找，快；范围扫描（Range Scan）：需顺序扫描多个 SSTable 并合并，无法用 Bloom Filter 跳过，读放大高。因此 LSM 点查优、范围扫描弱。

Bloom Filter 过滤不存在的 key 优化点查，Block Cache 缓存热块；范围扫描需合并多级、读放大高。

• Cassandra
• SSTable
• Compaction

Cassandra 使用 LSM 结构，SSTable 是磁盘上的有序不可变存储。SSTable 合并（Compaction）把多个重叠的 SSTable 合并成更少的、更大的 SSTable，消除冗余（相同 key 保留最新版本）、清理墓碑（删除标记）。Cassandra 的 Compaction 策略：默认 Size-Tiered Compaction（STCS），把大小相近的 SSTable 合并；也可用 Leveled Compaction（LCS，读优化）。合并后台进行，减少读放大、回收空间。合并会占用资源，需配置控制。

Cassandra 的 Compaction 合并 SSTable、清理冗余与墓碑，STCS 是默认策略。

• tombstone
• 删除标记
• LSM

LSM 中删除操作不立即删除数据，而是写入一个"删除标记"（tombstone），表示该 key 已删除。因为 SSTable 是不可变的，不能直接删除，只能标记。查询时若遇到 tombstone，则视为 key 不存在。tombstone 在 Compaction 时被清理（该 key 过去版本被丢弃）。tombstone 会占用空间、（范围删除会产生大量 tombstone），需在 Compaction 中及时清理，否则积累导致空间浪费与查询变慢。Cassandra 的 gc_grace_seconds 控制 tombstone 保留时间。

tombstone 是 LSM 的删除标记，Compaction 清理，需及时处理避免空间浪费。

• LevelDB
• RocksDB
• 差异

RocksDB 是 Facebook 基于 LevelDB 的优化版本，差异：①性能：RocksDB 优化并发、多线程 Compaction、Bloom Filter 优化，性能更强；②功能：RocksDB 支持 Column Family（列族）、事务、Merge 操作、更丰富的 Compaction 策略（Leveled/Universal/STCS）、统计、压缩算法（LZ4、ZSTD）；③LevelDB 单线程 Compaction、单列族、功能简单；④RocksDB 更活跃维护、更广泛用于生产（TiKV、MongoDB 等）。RocksDB 是 LevelDB 的增强，兼容性更好。

RocksDB 是 LevelDB 的优化版，功能（列族、事务、Compaction 策略）与性能更强。

• Leveled Compaction
• RocksDB
• 分层

RocksDB 的 Leveled Compaction（分层压缩）把 SSTable 组织成多层（L0、L1、L2...），每层大小递增（如 L1 是 L0 的 10 倍），同一层内 key 不重叠。L0 由 MemTable flush 而来（key 可能重叠），L1 及以下相邻层间合并（每层 key 有序）。特点：读放大低（每层最多一个 SSTable 需查）、空间放大低，但写放大高（数据多次跨层合并）。RocksDB 默认策略，适合读多写少。Leveled 权衡写放大的高来换取读与空间优化。

Leveled Compaction 分层、层内有序，读放大低但写放大高，RocksDB 默认。

• Bloom Filter
• 误判率
• 空间权衡

Bloom Filter 在 LSM 读路径中的作用：每个 SSTable 带一个 Bloom Filter，判断某 key 是否可能存在于该 SSTable。点查时先查 Bloom Filter，若返回"不存在"（无假阴性），则跳过该 SSTable，避免磁盘 IO。因此不存在的 key 的磁盘访问降到零（其 Bloom Filter 可准确判断不存在）。Bloom Filter 有假阳性（误判存在但实际上不存在），用多个哈希函数 + 位数组；误判率与位数组大小/哈希函数数相关：位数组越大、哈希函数越多，误判率越低，但空间越大。权衡：误判率 ∝ 空间（bits per key）。替代结构：Cuckoo Filter（可删除、误判率更低）、Quotient Filter、Xor Filter（更小更快）。它们以空间换误判率。

Bloom Filter 无假阴性，可准确跳过不存在的 key 的 SSTable（磁盘访问为零）；误判率与空间成正比；替代有 Cuckoo/Xor Filter。

• 空间放大
• SSTable 冗余
• Compaction 权衡

LSM 的空间放大（Space Amplification）：磁盘上实际数据量 / 逻辑数据量。因同一 key 的多个版本可能分布在多个 SSTable，未 Compaction 前存在冗余，占额外空间。量化：空间放大 = SSTable 总大小 / 唯一数据大小。分层（Leveled）空间放大低（层内合并、冗余少），大小分层（Size-Tiered）空间放大高（大量重叠 SSTable）。Compaction 策略权衡：Leveled 用更高写放大换低空间放大与低读放大；Size-Tiered 用低写放大换高空间放大与高读放大。需按存储与读写需求权衡。

空间放大反映 SSTable 冗余，Leveled 空间放大低、写放大高，Size-Tiered 相反。

• Column Family
• WAL
• 崩溃一致性

RocksDB 的 Column Family（列族）是独立的数据集合，各有 MemTable 与 SSTable，可选共享 WAL。多 CF 共享 WAL：一次写入跨多个 CF 时，WAL 记录包含各 CF 的变更，崩溃后通过 WAL 统一恢复所有 CF，保证跨 CF 一致性（避免部分 CF 成功部分失败）。WAL 必须先于 MemTable 持久化：MemTable 在内存，崩溃会丢失；WAL 在磁盘持久化，先写 WAL（fsync）再更新 MemTable，崩溃后从 WAL 重放恢复 MemTable 数据。若先改 MemTable 再写 WAL，崩溃时 MemTable 有数据但 WAL 无，无法恢复。故 WAL 先持久化保证崩溃一致性。

多 CF 共享 WAL 保证跨 CF 崩溃一致；WAL 先于 MemTable 持久化，崩溃后从 WAL 重放恢复。

• Cassandra LSM
• 写入路径
• 结构

Cassandra 使用 LSM 结构：写入先到 Memtable（内存，按分区/排序列有序），写满后刷盘成 SSTable（磁盘，有序不可变），后台 Compaction 合并多个 SSTable。写入前写 Commit Log（WAL，追加顺序写）保证持久性。查询合并 Memtable 与多个 SSTable。Cassandra 的 SSTable 带 Bloom Filter 加速点查。Compaction 策略（STCS/LCS）控制合并。Cassandra 的 LSM 实现使其高写入吞吐、适合时序与日志数据。

Cassandra 用 Memtable + Commit Log + SSTable + Compaction 的 LSM 实现，写优化。

• 读修复
• Compaction
• hint

分布式 LSM（如 Cassandra）中：读修复（read repair）在读取时发现副本数据不一致，对旧副本进行修复（写回最新值），与 Compaction 协作：Compaction 合并 SSTable 清理冗余，读修复保证副本间一致，两者互补（读修复处理副本间、Compaction 处理单副本内）。hint（hinted handoff）：写节点宕机时，把写暂存为 hint，节点恢复后重放，保证最终一致。墓碑清理（gc_grace_seconds）：删除的 tombstone 需保留 gc_grace_seconds（默认 3 天）后才被 Compaction 清理，避免过早清理导致未做读修复的删除被"复活"。hint 与 gc_grace_seconds 都影响一致性：hint 保证写最终送达，gc_grace_seconds 保证删除不被复活。

读修复保证副本一致、Compaction 清理单副本冗余；hint 保证写最终一致；gc_grace_seconds 延迟墓碑清理避免删除复活。