skiplist实现

Redis 跳跃表（Skiplist）实现详解（基于 6.0.10 版本）

跳跃表（Skiplist）是一种高效的有序数据结构，通过在节点中维护多层指针，实现快速查找、插入和删除操作（平均时间复杂度 O (logN)）。Redis 中，跳跃表是有序集合（ZSet）的底层实现之一（当 ZSet 元素数量多或元素较大时使用，替代 ziplist）。本文结合 Redis 源码中的结构体，详解跳跃表的设计与工作原理。

跳跃表的核心作用

ZSet 需要支持按分值（score）排序和快速范围查询（如 ZRANGE、ZREVRANGE），跳跃表相比其他结构（如平衡树）的优势：

• 实现简单：无需像红黑树那样维护复杂的旋转平衡逻辑。
• 性能均衡：查找、插入、删除的平均时间复杂度均为 O (logN)，且常数因子小。
• 适合范围查询：通过层级指针可直接定位到范围起点，高效遍历区间元素。

跳跃表的结构体设计

Redis 中跳跃表由两个核心结构体组成：zskiplistNode（节点）和 zskiplist（表本身），定义如下（简化自源码）：

跳跃表节点（zskiplistNode）

typedef struct zskiplistNode {
    sds ele;                  // 存储的元素（字符串，ZSet 中的 member）
    double score;             // 分值，用于排序（ZSet 中按 score 排序）
    struct zskiplistNode *backward;  // 后退指针（仅指向当前节点的前一个节点，用于反向遍历）
    struct zskiplistLevel {   // 层级数组（每个层级包含前进指针和跨度）
        struct zskiplistNode *forward;  // 前进指针（指向同一层级的下一个节点）
        unsigned long span;             // 跨度（当前节点到 forward 指向节点的"距离"，用于计算排名）
    } level[];                // 柔性数组（层级数量动态分配，每层独立维护指针）
} zskiplistNode;

关键字段解析：

• ele：ZSet 中的成员（member），是一个字符串（sds 类型），具有唯一性（ZSet 不允许重复 member）。
• score：成员对应的分值，ZSet 按 score 升序排序（相同 score 的节点按 ele 字典序排序）。
• backward：后退指针，仅用于反向遍历（如 ZREVRANGE），指向当前节点的前一个节点（类似双向链表的 prev 指针），但仅在最底层有效。
• level[]：层级数组，是跳跃表 “跳跃” 特性的核心：
  • 每个节点的层级数量是随机生成的（通常 1-64 层，Redis 中最大层级为 64）。
  • 层级越高，前进指针跨越的节点越多，查询时可快速 “跳过” 无关节点。

跳跃表本身（zskiplist）

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  // 表头、表尾节点（方便快速定位首尾）
    unsigned long length;                 // 跳跃表中的节点总数（ZSet 的元素个数）
    int level;                            // 跳跃表当前的最大层级（不包含表头节点的层级）
} zskiplist;

关键字段解析：

• header：表头节点（哨兵节点），不存储实际数据（ele 为 NULL，score 为 0），仅用于简化查询逻辑。
• tail：表尾节点，快速定位最后一个节点（如 ZREVRANGE 从尾部开始遍历）。
• length：记录节点总数，可直接返回 ZSet 的元素个数（ZCARD 命令直接使用此值）。
• level：当前跳跃表中所有节点的最大层级（不包含表头），用于优化查询时的起始层级。

跳跃表的整体结构示意图

一个包含 3 个节点的跳跃表示例（层级简化）：

level 3:  header -> [node1] -----------------------> [node3] (tail)
                    (score=1)                       (score=3)
level 2:  header -> [node1] ---------> [node2] -> [node3]
                    (score=1)         (score=2)   (score=3)
level 1:  header -> [node1] -> [node2] -> [node3]
                    (score=1)         (score=2)   (score=3)
                    backward <---- backward <---- backward

• 表头（header）：每层都有前进指针，作为查询的起点。
• 层级：节点的层级随机生成（如 node1 有 3 层，node2 有 2 层，node3 有 3 层）。
• 前进指针：同一层级的指针串联起节点，高层级指针跨越更多节点（如 level 3 中，node1 直接指向 node3）。
• 跨度（span）：level 3 中 node1 到 node3 的 span 为 2（中间跳过 node2），用于计算节点排名（ZRANK 命令通过累加 span 实现）。

核心特性与操作原理

层级的随机生成（关键设计）

跳跃表的高效性依赖于节点层级的随机分布：层级越高的节点越稀疏，确保查询时能快速跳过大部分节点。

Redis 中节点层级的生成规则：

• 初始层级为 1。
• 以 50% 的概率（p=0.5）提升层级，直到达到最大层级（64）或概率试验失败。
• 示例：约 50% 的节点有 1 层，25% 有 2 层，12.5% 有 3 层，以此类推（符合几何分布）。

这种分布使得跳跃表的平均层级为 2，最大层级为 O (logN)，保证查询效率。

查找操作

查找指定 score 和 ele 的节点步骤：

1. 从表头的最高层级（zskiplist.level）开始遍历。
2. 若当前层级的前进指针指向的节点score 小于目标值，则移动到该节点（利用高层级指针快速跳跃）。
3. 若前进指针指向的节点score 大于目标值或score 相等但 ele 字典序更大，则降低一层继续查找。
4. 重复步骤 2-3，直到降至第 1 层，找到目标节点或确认不存在。

示例：查找 score=2 的节点

• 从 header 的 level 3 开始，发现前进指针指向 score=3 的 node3（大于 2），降至 level 2。
• level 2 中，header 的前进指针指向 score=1 的 node1（小于 2），移动到 node1。
• node1 的 level 2 前进指针指向 score=2 的 node2（匹配），查找结束。

插入操作

插入新节点的核心是确定新节点的层级和更新相关节点的指针与跨度：

1. 随机生成新节点的层级（按上述 50% 概率规则）。
2. 从表头最高层级开始，查找新节点的插入位置，同时记录各层级中需要更新的前驱节点（及对应的跨度）。
3. 创建新节点，设置 score、ele 和层级数组。
4. 调整前驱节点的前进指针（指向新节点），并更新新节点和后续节点的跨度值。
5. 更新跳跃表的 level（若新节点层级大于当前最大层级）和 length（+1）。

删除操作

删除节点需反向调整相关指针和跨度：

1. 查找待删除节点的所有前驱节点（各层级中指向该节点的节点）。
2. 调整前驱节点的前进指针（跳过待删除节点，指向其下一个节点），并更新跨度。
3. 释放待删除节点的内存。
4. 更新跳跃表的 length（-1），若删除的是最高层级节点，需更新 level。

范围查询（ZRANGE 核心实现）

跳跃表的层级结构天然支持高效范围查询：

1. 先定位到范围的起始节点（如 ZRANGE min max 中的 min 节点）。
2. 从起始节点的第 1 层开始，通过 forward 指针依次遍历后续节点，直到超出范围（score > max）。
3. 遍历过程中收集节点的 ele 和 score，形成结果集。

跳跃表与 ZSet 的关系

ZSet 在 Redis 中采用混合存储策略：

• 当元素数量少（≤128 个）且元素小（每个 member 长度 ≤64 字节）时，使用 ziplist 存储（节省内存）。
• 当元素数量多或元素大时，自动转为跳跃表 + 哈希表的组合：
  • 跳跃表：按 score 排序，支持范围查询和排序操作。
  • 哈希表（dict）：映射 member 到 score，支持 O (1) 时间复杂度的 ZSCORE 等命令。

跳跃表的优势与局限性

优势

• 查询高效：平均 O (logN) 时间复杂度，适合 ZSet 的高频查询场景。
• 范围操作友好：无需像数组那样从头遍历，可直接定位范围起点。
• 实现简单：相比红黑树，无需维护平衡，代码可读性高，调试难度低。

局限性

• 内存开销：每个节点需存储多层指针和跨度，内存占用比数组或链表高（但远低于平衡树的指针开销）。
• 随机层级的不确定性：最坏情况下（节点层级全为 1），性能退化为 O (N)，但概率极低（Redis 通过限制最大层级为 64 规避）