Redis 跳跃表 Redis跳跃表推导技术概述与实现原理解析

Redis跳跃表：高效有序数据结构的实现原理解析

——2025年8月最新动态：Redis 7.4版本对跳跃表内存布局进行优化，在保持O(logN)查询效率的同时，进一步减少了约15%的内存占用

为什么Redis需要跳跃表？

想象你在一个拥有百万级成员的在线游戏排行榜中,需要实时维护玩家分数排名，如果用普通链表，查找第1000名的玩家需要遍历1000次；如果用数组，插入新数据又需要移动大量元素，这时跳跃表（Skip List）就派上用场了——它能在O(logN)时间复杂度内完成查找、插入和删除，实现原理却比红黑树简单得多。

Redis选择跳跃表作为有序集合（ZSET）的底层实现，正是因为它在性能和实现复杂度之间取得了完美平衡。

跳跃表的核心设计思想

多层链表的巧妙组合

跳跃表的本质是一个多层级的有序链表：

• 第0层：完整的原始链表，包含所有元素
• 第1层：约1/2元素会被"提升"，作为快速通道
• 第2层：在第1层基础上再提升约1/2元素
• 第N层：通常只有头尾节点

比如存储数据 [1, 3, 5, 7, 9] 的跳跃表可能长这样：

第3层：1 ---------------------------> 9  
第2层：1 --------> 5 --------> 9  
第1层：1 -> 3 -> 5 -> 7 -> 9  
第0层：1, 3, 5, 7, 9（完整数据）

随机化的层次决策

Redis通过抛硬币算法决定节点高度：

// Redis 源码片段（简化版）
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (0.25 * 0xFFFF))  // 25%概率升级
        level += 1;
    return level < ZSKIPLIST_MAXLEVEL ? level : ZSKIPLIST_MAXLEVEL;
}

这种随机化设计使得高层节点自然分布,无需复杂重平衡。

Redis中的具体实现

关键数据结构

typedef struct zskiplistNode {
    sds ele;                          // 成员对象（如玩家ID）
    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;

查询过程演示

假设要查找score=7的节点：

1. 从最高层（第3层）开始，发现1→9跨度太大
2. 降级到第2层,1→5→9，发现5 < 7 < 9
3. 从5节点降级到第1层,5→7→9，找到目标

插入与删除的平衡艺术

插入新节点时：

• 随机生成节点高度（如3层）
• 逐层更新指针（类似链表插入）
• 更新沿途节点的span值

删除操作类似,但需注意内存回收，Redis通过惰性删除策略优化性能。

为什么不用红黑树？

尽管红黑树也能实现O(logN)操作，但Redis选择跳跃表因为：

1. 实现简单：调试和维护成本低
2. 范围查询高效：ZRANGE等操作只需遍历底层链表
3. 并发友好：部分场景更容易实现无锁并发

性能实测对比

在2025年Redis实验室的基准测试中（100万数据）：

跳跃表在写入和范围查询上表现更优,而红黑树内存稍省但实现复杂。

最佳实践建议

1. 控制ZSET大小：单集合超过10万成员时考虑分片
2. 善用ZSCAN代替大范围ZRANGE
3. 对于频繁更新的分数,优先使用ZINCRBY

注：本文实现原理基于Redis 7.4源码分析，部分细节可能随版本迭代调整。