LevelDBMemTable为何选择跳表，从结构设计看内存键值存储的权衡

在 LevelDB 的数据写入流程中，所有用户写入最终都会汇聚到一个关键内存结构——MemTable。它既是 DBImpl::Write 路径的终点, 也是系统崩溃后恢复数据的起点。尽管其代码量仅占整个库的极小部分（db/skiplist.h、db/memtable.h 与 db/memtable.cc 合计不足 600 行），却承载着高频写入、点查、顺序遍历与无锁并发读等多重严苛需求。其核心骨架——跳表（SkipList），正是为这些特定场景量身定制的结构选择。

MemTable 的核心操作可归纳为三类：插入（每次写入新增一条记录）、点查（Get 操作查找指定 key）、顺序遍历（Iterator 与 flush 时全量扫描）。附加硬约束是：写入过程中读操作不能阻塞，即需支持“单线程写、多线程无锁读”。这一组合排除了若干常见数据结构。

哈希表虽在点查上达到 O(1) 时间复杂度，但天然无序。而 flush 是 LevelDB 的常态化后台任务，若依赖哈希表，则每次落盘前必须对全部数据排序，带来 O(n log n) 的额外开销。即便引入“哈希+排序缓存”的混合方案，也会显著增加实现复杂度与维护成本，违背 LevelDB 简洁可靠的设计哲学。

红黑树或 AVL 树看似理想：有序、插入与查询均为 O(log n)。但其平衡机制依赖节点旋转，会修改已有节点的指针关系。当一个无锁遍历线程刚获取某节点引用，该节点却因插入触发旋转而被重构，将导致读取异常。要规避此问题，要么加读写锁（牺牲并发性），要么引入复杂的版本控制机制（如 RCU），均与“无锁读”目标冲突。此外，MemTable 中的 key 为变长字节串（const char*），若直接嵌入树节点，需预留定长空间造成浪费；若采用指针间接访问，则每节点多一次内存访问，降低缓存效率。

B 树虽为磁盘优化设计，强调扇出大以减少 IO，但在纯内存场景下并无优势。其节点分裂涉及大量数据搬运，且“一页一节点”的设计前提在内存中不成立，反而增加了实现负担。

跳表则巧妙绕过上述痛点。其平衡性不依赖确定性旋转，而是通过“抛硬币”概率机制决定新节点层数：每次插入时独立生成高度 h，分配新节点并预设各层 next 指针，最后仅修改各层前驱节点的 next 指针指向新节点。这一过程对已有节点内容零修改，确保无锁读者看到的始终是完整或不可见的状态，无中间态风险。底层 L1 链表天然有序，迭代无需额外排序；实现简洁，核心逻辑不足 300 行。

LevelDB 的跳表实现中，key 并非直接存储于节点内，而是以 const char 类型指针形式存在（见 db/memtable.h 第 75 行：typedef SkipList, KeyComparator> Table）。实际 key 数据被编码后存入 Arena 内存池，节点仅保存指向该编码段的指针。这种设计既避免了变长 key 的内存碎片问题，又保证了节点结构紧凑固定——每个节点包含 key 指针（8 字节）与 next 指针数组，后者长度由随机生成的高度 h 决定，总大小为 sizeof(Node) + 8 × (h−1)。

跳表的查找效率源于其分层抽样结构。以 9 个 key 的示例为例（图1），L1 为完整有序链表；L2 包含约 1/4 节点（如 9、21、45）；L3 则为 L2 的再抽样（如 21）。查找 key=33 时，从最高层 L3 出发，一步至 21；降层至 L2，发现下一节点 45 过大，遂再降层至 L1，精确定位。理论上，若每层节点数为下一层的 1/4，则总层数约为 log₄n，每层平均步数 ≤ 4，期望时间复杂度为 O(log n)。

值得注意的是，MemTable 的生命周期为“一代而终”：一旦达到阈值即整体 flush 至 SSTable，原 MemTable 被废弃，不再进行单节点删除或更新。这一特性进一步强化了跳表的优势——无需支持删除操作，简化了节点回收逻辑；且因结构一次性构建、一次性销毁，无需长期维持复杂平衡状态。

对比其他数据库实现，RocksDB 延续了 LevelDB 的跳表设计；而 WiredTiger 在内存表中采用 B-Tree，因其支持更复杂的事务与原地更新；SQLite 的内存模式则使用普通 B-Tree。可见，数据结构选择高度依赖上层语义约束。LevelDB 的设计者 Jeff Dean 与 Sanjay Ghemawat 显然经过深思熟虑：在“写入频繁、读取并发、key 变长、无删除、短生命周期”这一画像下，跳表是最轻量、最可靠、最符合工程直觉的解。

跳表并非万能。在需要范围删除、高密度更新或严格最坏时间保障的场景中，其概率性平衡可能带来性能抖动。但对 LevelDB 的 MemTable 而言，它用极小的代码代价，换来了清晰的并发模型与稳定的平均性能，体现了“合适优于先进”的系统设计智慧。

补充说明：部分资料误将跳表与“骨架”概念混淆于计算机视觉中的骨骼动作识别（如 Pattern Recognition Letters 中的 Stage-Aware Spatial-Temporal Placement），二者领域迥异，无技术关联。本文聚焦数据库内核实现，不涉及 CV 或结构体封装等无关内容。