用 Rust 从零实现跳表:Redis 为什么用它替代平衡树
如果让你实现一个有序集合,第一反应大概是红黑树。但 Redis 的 ZSet 用的是跳表。
这个选择当年被问过很多次。Antirez 的回答很实在:跳表实现简单,范围查询好写,并发版本更容易做。红黑树当然也 O(log n),但你要在插入删除时处理一堆旋转和染色,代码量和出错概率都高一个数量级。
这篇从零写一个跳表。核心只有一个问题:怎么用随机性换掉那些复杂的平衡操作。
跳表到底"跳"在哪
先看一个有序链表:
1 -> 3 -> 5 -> 7 -> 9 -> 12 -> 20 -> NULL查 20 要从头走 7 步,复杂度 O(n)。跳表的想法是:在链表之上再叠几层"快速通道",每层都是下层的一个子集。
L3: 1 -----------------> 20 -> NULL
L2: 1 --------> 9 ------> 20 -> NULL
L1: 1 --> 5 --> 9 --> 12 20 -> NULL
L0: 1 -> 3 -> 5 -> 7 -> 9 -> 12 -> 20 -> NULL查找从最高层开始,能往前就往前,不能往前就下一层。查 20 只需要:L3 从 1 直接跳到 20,两次比较搞定。
这就是跳表名字的来源——用"跳跃"把线性查找变成对数查找。
节点设计:向后指针的数组
跳表节点的关键设计是:一个节点持有多个向后的指针,数量等于它的层数。
因为层数是运行时决定的,用定长数组会浪费,用 Vec 又太散。工程上通常用一个动态数组:
#[derive(Debug)]
struct Node<K, V> {
key: K,
value: V,
// next[i] 指向第 i 层的下一个节点
next: Vec<Option<*mut Node<K, V>>>,
}
impl<K, V> Node<K, V> {
fn new(key: K, value: V, level: usize) -> Box<Self> {
Box::new(Node {
key,
value,
next: vec![None; level],
})
}
}这里用了裸指针 *mut Node。原因后面会讲——Rust 的所有权系统对"多个前驱共享同一个后继"这种图结构很别扭,跳表恰好属于这种结构。
关键问题:新节点该建几层
跳表最巧的地方在这里。不做任何平衡操作,而是抛硬币决定层数。
const MAX_LEVEL: usize = 32;
const P: f64 = 0.25;
fn random_level() -> usize {
let mut level = 1;
// 用一个廉价但够用的伪随机
while level < MAX_LEVEL && rand_bool(P) {
level += 1;
}
level
}用标准库的随机数:
use std::cell::Cell;
thread_local! {
static RNG_STATE: Cell<u64> = const { Cell::new(0x2545F4914F6CDD1D) };
}
fn rand_bool(p: f64) -> bool {
RNG_STATE.with(|s| {
// xorshift64
let mut x = s.get();
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
s.set(x);
(x as f64 / u64::MAX as f64) < p
})
}每个节点有 1/4 的概率再往上升一层。这意味着:
- 第 1 层有全部 n 个节点
- 第 2 层期望有 n/4 个
- 第 3 层期望有 n/16 个
期望层数是 1/(1-p) = 1.33,空间开销是线性的。 这就是跳表的全部"魔法"——不用平衡,靠概率保证树的形状。
跳表把"平衡"从确定性算法变成了概率性质。它不保证每次都是最优结构,但期望上一定是 O(log n)。
查找:从顶层往下压
查找的逻辑只有四行描述:从最高层开始,能往右就往右,不能往右就往下。
impl<K: Ord, V> SkipList<K, V> {
fn find_predecessors(&self, key: &K) -> Vec<*mut Node<K, V>> {
let mut prev = vec![self.head; self.level];
let mut x = self.head;
for i in (0..self.level).rev() {
unsafe {
while let Some(next) = (*x).next[i] {
if (*next).key < *key {
x = next;
} else {
break;
}
}
}
prev[i] = x;
}
prev
}
}这段代码值得逐行看。for i in (0..self.level).rev() 就是"从顶层往下"。内层 while 是"在当前层尽量往右"。
返回的 prev 数组是关键:它记录了每一层里,key 应该插在谁后面。插入和删除都复用它。
插入:先找位置,再逐层接链
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
let prev = self.find_predecessors(&key);
// 如果已存在,只更新 value
unsafe {
if let Some(next) = (*prev[0]).next[0] {
if (*next).key == key {
return Some(std::mem::replace(&mut (*next).value, value));
}
}
}
let level = random_level().min(MAX_LEVEL);
if level > self.level {
// 新层只有 head 作为前驱
for i in self.level..level {
prev[i] = self.head;
}
self.level = level;
}
let node = Node::new(key, value, level);
let raw = Box::into_raw(node);
unsafe {
for i in 0..level {
// 头插法接链:new -> prev.next, prev.next -> new
(*raw).next[i] = (*prev[i]).next[i];
(*prev[i]).next[i] = Some(raw);
}
}
self.len += 1;
None
}注意 Box::into_raw。节点的所有权被交出去,由跳表自己管理生命周期。这是链表类数据结构在 Rust 里的常见做法——用 Box 分配保证地址稳定,再用裸指针串起来。
为什么这里"不得不"用 unsafe
初学者会问:Rust 不是内存安全吗,怎么写了一堆 unsafe?
因为跳表的结构天然违反所有权规则。看这个图:
L2: head ------> n5 ------> NULL
L1: head -> n1 -> n5 ------> NULL
L0: head -> n1 -> n2 -> n5 -> NULLn5 同时被 n1.next[1] 和 head.next[2] 指着。用 Rc<RefCell<>> 能表达,但每次访问都要检查引用计数,性能掉一大截。用 Box 加索引(arena)也行,但要额外维护一个容器。
标准做法是:在一个受控的小范围内用 unsafe,把安全边界用注释写清楚。
// SAFETY: prev 里的指针要么是 head,要么来自 find_predecessors 返回的链表节点,
// 它们都在 self 的生命周期内有效,且不会被并发修改(&mut self 独占)。再配合 Drop 手动释放,就不会漏内存:
impl<K, V> Drop for SkipList<K, V> {
fn drop(&mut self) {
unsafe {
let mut node = (*self.head).next[0];
while let Some(cur) = node {
let next = (*cur).next[0];
drop(Box::from_raw(cur)); // 重新接管所有权并释放
node = next;
}
drop(Box::from_raw(self.head));
}
}
}范围查询:跳表的主场
跳表真正比平衡树舒服的地方是范围查询。比如"返回 [10, 50) 之间的所有元素":
pub fn range(&self, start: &K, end: &K) -> Vec<(&K, &V)> {
let mut result = Vec::new();
let prev = self.find_predecessors(start);
let mut node = unsafe { (*prev[0]).next[0] };
while let Some(cur) = node {
unsafe {
if &(*cur).key >= end {
break;
}
result.push((&(*cur).key, &(*cur).value));
node = (*cur).next[0];
}
}
result
}定位到起点后,沿着最底层往后走就行。没有中序遍历,没有递归,没有栈。 这就是 Redis 用它做 ZRANGE、ZRANGEBYSCORE 的现实原因。
跳表 vs 平衡树 vs B+ 树
| 维度 | 跳表 | 红黑树 | B+ 树 |
|---|---|---|---|
| 实现难度 | 低 | 高 | 中高 |
| 范围查询 | 很自然 | 需中序遍历 | 很自然(叶子链表) |
| 并发实现 | 相对容易 | 很难 | 中等 |
| 缓存局部性 | 一般 | 一般 | 好(适合磁盘) |
| 最坏复杂度 | O(n)(概率极低) | O(log n) 严格 | O(log n) 严格 |
有一条容易忽略:跳表的最坏复杂度是 O(n),因为随机层数理论上可能一直不升。但概率是 p^k,实际上不可能发生。工程上可以接受"概率保证",因为坏情况的概率低到可以忽略。
结论
跳表是我认为最值得手写一遍的数据结构之一,因为它清楚地展示了"用随机性替代复杂性"这个思路:
层数靠抛硬币决定,空间期望线性;查找从顶层往下压,期望 O(log n);范围查询沿底层扫,天然有序。
写完之后再看 Redis 的 ZSet 实现,那些 zskiplist、zslInsert、zslGetRank 就不再是黑盒了。