返回文章列表

用 Rust 从零实现跳表:Redis 为什么用它替代平衡树

362 字·3 分钟阅读
Rust从零造轮子数据结构

如果让你实现一个有序集合,第一反应大概是红黑树。但 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 -> NULL

n5 同时被 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 就不再是黑盒了。