Redis Sorted Set 底层跳表实现范围查询的时间复杂度与层级概率

1. 跳表（Skip List）概述

Redis 的 Sorted Set 在元素数量较多或元素长度较大时，底层使用 跳表（skiplist） 作为有序集合的存储结构。跳表是一种基于并行链表的概率性数据结构，通过维护多层索引来加速查找、插入和删除操作。

每个节点包含一个 level 属性，表示该节点拥有的层数。每一层都是一个指向同层下一个节点的指针（forward 数组）。最底层（level 1）是完整的有序链表，向上每层的节点数量按概率递减，从而形成对数级别的搜索复杂度。

以下是跳表节点在 Redis 源码（src/server.h）中的简化定义：

typedef struct zskiplistNode {
    sds ele;                 // 存储实际元素（字符串）
    double score;            // 分值
    struct zskiplistNode *backward; // 后退指针（仅用于反向遍历）
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 同层下一个节点
        unsigned int span;            // 本层到 forward 间的跨度（节点数）
    } level[];
} zskiplistNode;

每个节点的层数 level 在创建时按照幂次定律概率随机生成，这是跳表性能的核心。

2. 层级概率的核心机制

2.1 随机层数生成

Redis 使用 zslRandomLevel(void) 函数生成节点的层数：

#define ZSKIPLIST_MAXLEVEL 32  // 最高层数限制
#define ZSKIPLIST_P 0.25       // 层级概率因子

int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

• 每次有 25% 的概率增加一层。
• 因此，一个节点的层级分布服从几何分布：
  • 层数为 1 的概率：1 - 0.25 = 0.75
  • 层数为 2 的概率：0.75 × 0.25 = 0.1875
  • 层数为 3 的概率：0.75 × 0.25² = 0.046875
  • 层数为 k 的概率：0.75 × 0.25^(k-1)

2.2 层级与节点数量的期望

设总节点数为 N，则：

• 第 1 层（最底层）包含全部 N 个节点
• 第 2 层期望节点数：N × 0.25
• 第 3 层期望节点数：N × 0.25²
• 第 k 层期望节点数：N × 0.25^(k-1)

由于 Redis 的 ZSKIPLIST_P = 0.25，比经典跳表论文中的 0.5 更小，这意味着层数增长更慢，每层节点数减少得更快，从而节省内存，同时仍能保持 O(log N) 的查询复杂度。

2.3 最大层数的理论值

最高层 L_max 满足：

$$ N \times 0.25^{L_{max}-1} \approx 1 $$

解得：

$$ L_{max} \approx \log_{1/0.25} N = \log_4 N = \frac{1}{2} \log_2 N $$

因此期望的最大层数约为 O(log N)。Redis 将最大层数硬限制为 32 层，足以支持 N ≤ 2^64 级别的数据量。

3. 范围查询的实现与时间复杂度

3.1 两种典型范围查询

Redis Sorted Set 支持两种范围查询操作：

• ZRANGEBYSCORE key min max：按分值范围获取元素（有序）
• ZRANGEBYLEX key min max：按字典序范围获取元素

底层均通过跳表的双向遍历能力实现。以 ZRANGEBYSCORE 为例，执行流程如下：

1. 找到下限节点：从跳表的 header 最高层开始，逐层向下查找第一个 score >= min 的节点
2. 顺序遍历：从该节点开始，通过底层链表（level[0].forward）向后遍历，直到 score > max 为止
3. 返回结果：收集遍历到的所有元素

3.2 时间复杂度分析

跳表的查询操作分为两步：

• 定位起始位置：时间复杂度与普通查找一致，为 O(log N)
• 顺序遍历结果：假设匹配的元素个数为 m，则遍历 m 个节点只需 O(m) 时间

因此，ZRANGEBYSCORE 的整体时间复杂度为 O(log N + m)。

同样，ZRANGEBYLEX 的时间复杂度也为 O(log N + m)。

3.3 为什么范围查询如此高效？

跳表的底层链表是完全有序的，且每个节点只存储一个 forward 指针指向下一个元素。遍历 m 个元素仅需访问 m 个连续节点，没有任何回溯或跳跃。

对比平衡树（如红黑树）的范围查询：

• 红黑树需要中序遍历，虽然也是 O(log N + m)，但实际访问的节点数量可能更多（因为需要回溯父节点或使用栈）
• 跳表只需要沿 level[0] 指针单向移动，访问更连续，局部性更好

4. 层级概率对范围查询性能的影响

4.1 影响路径长度

查找起始位置时，跳表从最高层开始，逐层下降。层数越多，每层跳过的节点数越多，从而查找路径越短。

假设当前节点在第 k 层，其 forward 指针指向的节点跨度（span）期望为 1/0.25 = 4 个底层节点。因此从数据库到目标位置，每层平均下降 1 次，水平移动约 4 个底层节点跨度。

总查找路径长度（水平移动+垂直移动）的期望为：

$$ E[path] = O(\log_{1/P} N) = O(\log_4 N) $$

由于 P=0.25，相比 P=0.5 的经典跳表，路径长度变为两倍（因为 log_4 N = (1/2) log_2 N）。但常数因子不影响复杂度，且 Redis 通过硬限制最大层数 32 层，避免了极端情况。

4.2 影响内存占用

每个节点的平均层数为：

$$ E[level] = \frac{1}{1-P} = \frac{1}{0.75} \approx 1.33 $$

即平均每个节点只包含约 1.33 个 forward 指针。相比 P=0.5 时平均 2 个指针，Redis 的 P=0.25 将内存占用降低了约 33%。

4.3 实际性能测试

在 N=10^6 时，跳表的平均最大层数约为 log_4 10^6 ≈ 10。查找任意一个节点平均需要约 20 次指针移动（每层约 4 次水平 + 1 次下降）。范围查询匹配 m=100 个元素时，总操作次数约为 20 + 100 = 120，极快。

5. 跳表与红黑树的对比（在范围查询场景）

Redis 选择跳表而不选红黑树，主要原因是简化实现（无需平衡旋转）和更好的范围查询局部性（底层链表连续，红黑树中序遍历需不断访问左/右子树）。

6. 核心结论

• Redis Sorted Set 底层的跳表使用 P=0.25 的几何分布生成节点层级，平均每个节点仅 1.33 个 forward 指针，节省了约 33% 的内存。
• 范围查询 ZRANGEBYSCORE / ZRANGEBYLEX 的复杂度为 O(log N + m)，其中 m 为返回元素个数。定位起点需要遍历 O(log_4 N) 个指针，后续遍历仅沿底层链表走 m 步。
• P=0.25 使每层节点数减少更快，但路径长度增加为 P=0.5 时的两倍（仍为对数级别），整体性能依然优秀。
• 跳表的结构简单，适合高并发场景，且范围查询的内存局部性优于红黑树。

实际生产环境中，ZRANGEBYSCORE 在百万级数据量下耗时通常在微秒至毫秒级，完全满足实时应用需求。