Redis 中跳表的实现原理是什么？

Redis 跳表（Skip List）实现原理详解

【核心定义】

跳表是一种基于有序链表、通过添加多级索引实现快速查找、插入和删除的概率平衡数据结构，在Redis中主要用于实现有序集合（Sorted Set）的底层存储。

【关键要点】

数据结构分层：跳表由多层链表组成，底层（L0）包含所有元素，上层每层都是下层的“快速通道”，节点随机确定层高。
时间复杂度O(log n)：通过多级索引，将查找复杂度从链表的O(n)优化到近似平衡树的O(log n)，平均查找路径长度显著减少。
空间换时间：额外存储索引节点（约n/2个节点），空间复杂度O(n)，但实际内存占用远低于平衡树。
概率平衡机制：节点层数由随机算法决定（幂次定律），避免严格平衡的开销，实现简单高效。
支持范围查询：利用有序链表特性，可以高效实现ZRANGE、ZREVRANGE等范围操作。

【深度推导/细节】

节点结构与随机层高算法

// Redis 7.0 跳表节点结构（简化）
typedef struct zskiplistNode {
    sds ele;                      // 成员对象（字符串）
    double score;                 // 分值（排序依据）
    struct zskiplistNode *backward; // 后退指针（双向链表）
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 前进指针
        unsigned long span;             // 跨度（到下一个节点的距离）
    } level[];                     // 柔性数组，层高随机
} zskiplistNode;

// 跳表结构
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;         // 节点数量
    int level;                    // 当前最大层数
} zskiplist;

核心算法逻辑拆解

Step 1 - 随机层高生成（核心概率机制）

// Redis 跳表层数随机算法
int zslRandomLevel(void) {
    int level = 1;
    // 0xFFFF = 65535，每次有1/4概率增加层数
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

设计原理：每增加一层的概率为1/4（ZSKIPLIST_P = 0.25）
层数分布：L1层100%，L2层25%，L3层6.25%，L4层1.56%…
最大层数：Redis 7.0中ZSKIPLIST_MAXLEVEL = 32，可容纳2^64个元素

Step 2 - 查找过程（ZRANK/ZSCORE）

从最高层header开始，向右遍历找到最后一个小于目标score的节点
下降一层继续查找，重复直到L0层
平均查找路径长度：1/p * log_{1/p}(n) ≈ 1.33 * log(n)

Step 3 - 插入过程（ZADD）

查找插入位置，记录每层的前驱节点update[]和跨度rank[]
随机生成新节点层高level
调整前后指针，更新跨度信息
如果新层高>当前跳表层数，更新跳表level字段

Step 4 - 删除过程（ZREM）

查找要删除的节点，记录每层的前驱节点
调整前驱节点的forward指针，跳过被删除节点
更新跨度信息
释放节点内存

性能优化细节

跨度（span）字段：记录每层两个节点之间的距离，实现O(log n)的排名查询（ZRANK）
后退指针（backward）：构成双向链表，支持逆序遍历和范围查询
分数相同处理：score相同时按成员字典序排序，保证确定性

【关联/对比】

Redis跳表 vs 平衡树（AVL/红黑树）

维度	Redis跳表	平衡树（红黑树）
实现复杂度	简单（约200行代码）	复杂（插入删除需旋转）
范围查询	天然有序，双向链表支持	需要中序遍历
并发友好度	更容易实现无锁并发	需要复杂锁机制
内存占用	每个节点1.33个指针（平均）	每个节点2个指针+颜色位
性能稳定性	概率平衡，最坏情况O(n)	严格平衡，稳定O(log n)