LevelDB 源码阅读：SkipList 跳表索引
Arena 那篇讲了 MemTable 的节点从哪来（内存层面）。这一篇看它们被编织成的索引结构：LevelDB 的跳表（db/skiplist.h）。这是工业界里最干净的单写多读无锁数据结构范例之一，几乎每一行都是同一条规则的推论——写操作由外部加锁，读操作不加锁。
如果还没读过 Arena 那篇，它是天然的前置阅读：这里的节点都是通过 arena_->AllocateAligned(...) 分配的。→ LevelDB 源码阅读：Arena 区域分配器
1. 线程安全契约
文件头把契约说得很直白（db/skiplist.h:11-14）：
// Writes require external synchronization, most likely a mutex.
// Reads require a guarantee that the SkipList will not be destroyed
// while the read is in progress. Apart from that, reads progress
// without any internal locking or synchronization.两条推论：
- 写（
Insert） 内部无锁，完全靠外部 mutex（MemTable / DB 写锁）保护。 - 读（
Contains、迭代器 seek）完全不加锁，可多读并发——唯一要求是读期间跳表对象不被销毁。
这之所以成立，靠的是代码坚持的两个不变式：
- 节点在跳表存活期间绝不删除（§2）。
- 节点内容（除
next指针外）不可变，新插入的节点用 release store 发布（§4）。
2. 节点常驻内存与生命周期
// (1) Allocated nodes are never deleted until the SkipList is
// destroyed. This is trivially guaranteed by the code since we
// never delete any skip list nodes.节点一旦分配，在跳表（也就在它的 MemTable）存活期间常驻内存、绝不单独释放；MemTable 写满刷盘（minor compaction）后，整个 Arena——连同其中的每个节点——一次性释放。
在 LevelDB 里这是自然契合：
- 删除也是插入——写入一个”墓碑标记”键，而非移除旧节点。
- 结构用”细粒度回收单个节点”的代价，换来了”刷盘时整体回收”，正好匹配 MemTable”攒批落盘”的生命周期。
3. 节点分配：NewNode + placement new
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode(
const Key& key, int height) {
char* const node_memory = arena_->AllocateAligned(
sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1));
return new (node_memory) Node(key);
}逐段拆解：
height：该节点带几个前向（next）指针，由RandomHeight()随机生成，受kMaxHeight约束。- 大小计算：
sizeof(Node)已含next_[0]（一个指针），所以补(height - 1)个指针槽，凑成height个前向指针。这就是经典柔性数组技巧（§5）。 char* const：AllocateAligned返回原始、未类型化、已对齐的字节。const只是把这个局部指针钉死不被重新赋值，内存是可写的。- placement new
new (node_memory) Node(key)：在已分配好的内存上构造对象——不申请新内存。内存始终归 Arena 所有（整体释放），大小与对齐都被精确控制。 - 一个 Arena 块装多个节点：
kBlockSize = 4096（4 KB）是块粒度，非每节点一块；几十字节的小节点背靠背打包进同一 4 KB 块，只有超过 1 KB 的大对象才单独占块。
4. 内存屏障：acquire/release 配对
这是无锁读的核心。Node 暴露四个访问器（db/skiplist.h:151-172）：
Node* Next(int n) { // acquire 读
return next_[n].load(std::memory_order_acquire);
}
void SetNext(int n, Node* x) { // release 写
next_[n].store(x, std::memory_order_release);
}
Node* NoBarrier_Next(int n) {
return next_[n].load(std::memory_order_relaxed);
}
void NoBarrier_SetNext(int n, Node* x) {
next_[n].store(x, std::memory_order_relaxed);
}为何要配对：
- release（写端）：保证本次存储之前的一切（节点完整初始化——key、value、低层指针）都不重排到其之后。指针只有等节点构造完才发布。
- acquire（读端）：保证本次加载之后的一切都能看到那份完整初始化。
- release + acquire ⇒ synchronizes-with：写线程在 release 前做的初始化，对读线程在 acquire 后保证可见。这个配对（而非 mutex）才让并发无锁遍历安全。
relaxed 只用在顺序无关处：单线程自己的指针游走，或”陈旧值无所谓”的读（如 max_height_ 的 racy 读，§10）。
5. next_[1] —— 柔性数组
std::atomic<Node*> next_[1];尽管写成 [1]，它不是单个指针，而是长度为 1 的数组充当柔性数组占位符：NewNode 按 height 超分配内存（§3），把 next_[0 .. height-1] 当作各层前向指针。Next(n) / SetNext(n, x) 读写的正好是第 n 层的后继。
6. 越界安全靠”纪律”而非检查
void SetNext(int n, Node* x) {
assert(n >= 0); // 只有下界检查，无上界检查SetNext / Next 无上界检查，标准 C++ 下读 next_[n]（n ≥ 1）属未定义行为，仅靠 §3 的超分配兜住物理内存。防止真正越界的两道纪律：
Insert中for (int i = 0; i < height; i++)上界 = 节点自身height，而NewNode恰好分配了height个槽；- 被链接在第
i层的节点必位于第i层之上 ⇒ 其height > i⇒ 必有next_[i]。
结论：store 本身不保证不越界，物理安全靠超分配、逻辑安全靠调用纪律，二者缺一不可。
7. kMaxHeight = 12 的由来
enum { kMaxHeight = 12 };配合分支因子 kBranching = 4（§9），节点高度 ≥ h 的概率为 (1/4)^(h-1)。第 i 层跨度期望 4^i，覆盖 N 节点需层数 ≈ log_4(N)。
4^12 ≈ 16,777,216≈ 1600 万：12 层足以高效索引约 1600 万节点。- 这远超任何现实 MemTable：
write_buffer_size默认 4 MB（上限 1 GB），根本到不了 1600 万节点。 - 12 是”覆盖足够 + 不浪费指针内存”的平衡点。实际层数
max_height_从 1 起，仅当RandomHeight更高时才增长。
8. 驳”64 GB”误区
常见误区：“16 M 节点 × 4 KB = 64 GB”——错把 Arena 的 4 KB 块粒度当成每节点大小。
实际：
- 节点结构极小（key
const char*指针 8B +next_平均 ~1.33 层 × 8B ≈ 19B，加对齐约 24B）。 - 多个节点打包进同一 4 KB 块。
- MemTable 受
write_buffer_size封顶，到不了 1600 万节点；4^12只是 12 层的理论覆盖能力，非真实节点数。
9. RandomHeight —— 几何分布高度
int SkipList<Key, Comparator>::RandomHeight() {
static const unsigned int kBranching = 4;
int height = 1;
while (height < kMaxHeight && rnd_.OneIn(kBranching)) {
height++;
}
return height;
}OneIn(4) 每次 1/4 概率返回 true（继续加层）、3/4 概率停止。于是绝大多数节点 1 层，越高越稀有——经典”底层密、高层疏”结构。
期望高度推导。设 K = 加层次数，P(K = k) = (1/4)^k · (3/4)，height = 1 + K：
E[K] = Σ k·(1/4)^k·(3/4)
= (3/4) · (1/4) / (3/4)²
= 1/3
E[height] = 1 + 1/3 = 4/3 ≈ 1.33- 触达 12 层封顶的概率极低：
(1/4)^11 ≈ 2.4×10⁻⁷。
10. FindGreaterOrEqual —— 核心查找
bool KeyIsAfterNode(const Key& key, Node* n) const {
return (n != nullptr) && (compare_(n->key, key) < 0); // n->key < key？
}
Node* FindGreaterOrEqual(const Key& key, Node** prev) const {
Node* x = head_;
int level = GetMaxHeight() - 1;
while (true) {
Node* next = x->Next(level);
if (KeyIsAfterNode(key, next)) {
x = next; // 还能往右：前进
} else {
if (prev != nullptr) prev[level] = x; // 记下本层前驱
if (level == 0) return next; // 到底层：返回第一个 ≥ key 的节点
else level--; // 下沉一层
}
}
}算法：
- 从最高层出发。若
next仍在目标之前（KeyIsAfterNode为真），往右移。 - 否则把当前节点记为本层前驱（
prev[level]）并下沉。 - 到 level 0 时，
next即第一个≥ key的节点；无则nullptr。
KeyIsAfterNode 把 n == nullptr 当 +∞（尾哨兵）；对真实节点只判断 n->key < key。
prev[] 是什么
prev 是每层一个槽的数组，存”在第 level 层，新节点应插在谁后面”。查找从最高层下沉，顺手把每层前驱记进 prev[]；Insert 随后用标准链表链接把新节点挂到各层（new->next = prev[i].next; prev[i].next = new），省去重复查找。
示例（插入 15，高度 2）：查找得 prev = {14, 10, 10}（level0/1/2），插入时把 15 挂入 level0、level1。
prev 是可选参数 —— 一个函数，两条调用路径
FindGreaterOrEqual 在单个 if (prev != nullptr) 守卫下服务两条路径：
Insert调用FindGreaterOrEqual(key, prev)—— 传数组，收集前驱；- 读操作（
Contains、Iterator::Seek）调用FindGreaterOrEqual(key, nullptr)—— 纯查找，前驱记录段整段跳过。
一个搜索函数同时服务插入与读取。注意 Insert 本身无”key 已存在就跳过”分支——去重是 MemTable 的职责，不是跳表的。一旦调用 Insert，就假定前驱数组必被使用。
11. 后续阅读方向
跳表是 MemTable 的内存索引。自然后续：
- LevelDB 源码阅读：MemTable —— internal key（user key + sequence + type）如何编码进节点，以及
Add/Get实现； - LevelDB 源码阅读：MemTable 刷盘与 SSTable 格式 ——
mem_写满后发生什么、SSTable 如何落盘布局； - 回到主线：
MemTable → WAL (log) → SSTable (table/block) → Compaction (version_set)。
Arena 那篇是这一切的地板——LevelDB 源码阅读：Arena 区域分配器。
关键结论速记
| 主题 | 要点 |
|---|---|
| 线程安全 | 写加锁、读无锁；读只怕对象被销毁 |
| 节点生命周期 | 常驻至 SkipList/MemTable 销毁，整体释放 |
| 分配 | Arena 超分配 + placement new；柔性数组 next_[1] |
| 内存序 | release 写 + acquire 读配对，支撑无锁读 |
| 层数 | kMaxHeight=12，log_4(N) 覆盖 ~1600 万 |
| 期望高度 | 4/3 ≈ 1.33 层 |
| 查找 | 高层下沉、右移 + 记录 prev[] |
prev | 插入用各层前驱；读调用传 null 不用 |