跳跃表原理

🔴 困难

题目描述

解释 Redis ZSet 底层的跳跃表（Skip List）实现原理。为什么使用跳跃表而不是平衡树？

示例场景

# ZSet 操作
ZADD leaderboard 100 "Alice" 95 "Bob" 120 "Charlie" 85 "David"
ZRANGE leaderboard 0 -1 WITHSCORES
# 1) "David"
# 2) "85"
# 3) "Bob"
# 4) "95"
# 5) "Alice"
# 6) "100"
# 7) "Charlie"
# 8) "120"

ZSCORE leaderboard "Alice"
# "100"

ZRANK leaderboard "Alice"
# 2 (从 0 开始)

提示

跳跃表是一种概率数据结构
通过多层链表实现快速查找
时间复杂度 O(log N)
空间换时间

解法

参考答案 (3 个标签)

跳跃表 ZSet 数据结构

跳跃表结构

跳跃表示例（4 层）：

Level 3:  NULL  →  Alice  →  NULL
Level 2:  NULL  →  Alice  →  Charlie  →  NULL
Level 1:  NULL  →  Alice  →  Bob  →  Charlie  →  NULL
Level 0:  NULL  →  Alice  →  Bob  →  Charlie  →  David  →  NULL

节点结构：
- Alice: score=100
- Bob: score=95
- Charlie: score=120
- David: score=85

节点定义

// 跳跃表节点
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;

插入过程

// 插入新节点
void zslInsert(zskiplist *zsl, double score, sds ele) {
    // 1. 查找插入位置
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    
    zskiplistNode *x = zsl->header;
    for (int i = zsl->level - 1; i >= 0; i--) {
        // 记录每层需要更新的节点
        while (x->level[i].forward &&
               (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                 sdscmp(x->level[i].forward->ele, ele) < 0))) {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    
    // 2. 随机生成层数
    int level = randomLevel();
    if (level > zsl->level) {
        for (int i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    
    // 3. 创建新节点
    zskiplistNode *node = zslCreateNode(level, score, ele);
    
    // 4. 插入节点并更新指针
    for (int i = 0; i < level; i++) {
        node->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = node;
        
        node->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    
    // 5. 更新其他层的 span
    for (int i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    
    zsl->length++;
}

// 随机层数生成
int randomLevel() {
    int level = 1;
    // 25% 概率增加一层
    while (random() & 0xFFFF < (0.25 * 0xFFFF)) {
        level++;
    }
    return level < ZSKIPLIST_MAXLEVEL ? level : ZSKIPLIST_MAXLEVEL;
}

查找过程

// 查找 score 对应的节点
zskiplistNode* zslGetElementByScore(zskiplist *zsl, double score) {
    zskiplistNode *x = zsl->header;
    
    // 从最高层开始查找
    for (int i = zsl->level - 1; i >= 0; i--) {
        // 在当前层向右查找
        while (x->level[i].forward &&
               x->level[i].forward->score < score) {
            x = x->level[i].forward;
        }
    }
    
    // 到达第 0 层，检查下一个节点
    x = x->level[0].forward;
    if (x && x->score == score) {
        return x;
    }
    return NULL;
}

为什么不用平衡树

特性	跳跃表	平衡树（AVL/红黑树）
查找	O(log N)	O(log N)
插入	O(log N)	O(log N)
删除	O(log N)	O(log N)
实现	简单	复杂
范围查询	高效（遍历第 0 层）	中序遍历
内存占用	较大（多层指针）	较小
平衡调整	无需调整	需要旋转

跳跃表的优势：

实现简单：不需要复杂的旋转操作
范围查询：第 0 层是有序链表，范围查询高效
无锁友好：插入删除不需要全局平衡
内存局部性：第 0 层连续内存，缓存友好

扩展：ZSet 的编码转换

ziplist vs skiplist

# ziplist 条件
zset-max-ziplist-entries 128    # 元素数量
zset-max-ziplist-value 64       # 元素字节数

# 查看 encoding
OBJECT encoding leaderboard
# "ziplist" 或 "skiplist"

# ziplist 转换为 skiplist
ZADD myzset 1 "a" 2 "b" 3 "c"
# 当元素数量或大小超过阈值时
# 自动转换为 skiplist + dict

编码对比

编码	条件	底层结构	优缺点
ziplist	元素少且小	压缩表	✓ 节省内存，✗ 性能低
skiplist	元素多或大	跳跃表 + 字典	✓ 性能高，✗ 内存大

为什么是 skiplist + dict

// ZSet 的底层实现
typedef struct zset {
    dict *dict;        // 字典：member → score
    zskiplist *zsl;    // 跳跃表：score + member
} zset;

// dict：快速查找 member 的 score
// zsl：按 score 排序，支持范围查询

// 示例
ZADD myzset 100 "Alice"
// dict: {"Alice" → 100}
// zsl: [Alice(100)]

ZSCORE myzset "Alice"
// 从 dict 查找：O(1)

ZRANGE myzset 0 -1
// 从 zsl 查找：O(log N)

时间复杂度分析

ZSet 操作

操作	ziplist	skiplist
ZADD	O(N)	O(log N)
ZREM	O(N)	O(log N)
ZSCORE	O(N)	O(1)（dict）
ZRANK	O(N)	O(log N)
ZRANGE	O(N log N)	O(log N + M)

范围查询

# 查询 score 在 [90, 110] 范围内的元素
ZRANGEBYSCORE leaderboard 90 110

# skiplist：
# 1. 查找 score >= 90 的第一个节点：O(log N)
# 2. 遍历第 0 层，直到 score > 110：O(M)
# 总时间复杂度：O(log N + M)

上一章节 String vs Hash 存储对象