Redis 源码硬核解析系列专题 - 第四篇：核心数据结构之跳表（Skip List）

第四篇：核心数据结构之跳表（Skip List）

1. 引言

跳表（Skip List）是一种高效的动态数据结构，在Redis中用于实现有序集合（ZSET），支持快速的范围查询和插入删除操作。相比传统平衡树（如AVL或红黑树），跳表的实现更简单且性能优异。本篇将深入剖析Redis跳表的源码实现，包括结构定义、插入删除逻辑和随机层高生成。

2. 跳表在Redis中的应用

用途：ZSET的核心数据结构，存储元素和分数（score），支持按分数排序。
特性：结合链表的简单性和二分查找的高效性，平均时间复杂度为O(log n)。

3. 跳表的结构体定义

跳表的实现位于src/server.h和src/t_zset.c中。以下是核心结构：

代码片段（server.h）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
typedef struct zskiplistNode {
    sds ele;                  // 元素（SDS字符串）
    double score;             // 分数
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span;     // 跨度（到下个节点的距离）
    } level[];                // 层数组（柔性数组）
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header; // 头节点
    struct zskiplistNode *tail;   // 尾节点
    unsigned long length;         // 节点数
    int level;                   // 最大层数
} zskiplist;

硬核解析：

zskiplistNode：每个节点包含元素、分数和多层前进指针（level[]）。
level[i].forward：指向该层下一个节点。
span：记录跨越的节点数，用于范围查询。
backward：后退指针，便于双向遍历。
zskiplist：管理整个跳表，header不存储数据，仅作为起点。

Mermaid结构图：

classDiagram
    class zskiplist {
        -header: zskiplistNode*
        -tail: zskiplistNode*
        -length: ulong
        -level: int
    }
    class zskiplistNode {
        -ele: sds
        -score: double
        -backward: zskiplistNode*
        -level[]: zskiplistLevel
    }
    class zskiplistLevel {
        -forward: zskiplistNode*
        -span: ulong
    }
    zskiplist o--> "1" zskiplistNode : "header"
    zskiplistNode o--> "n" zskiplistLevel : "level[]"
    zskiplistNode o--> "1" zskiplistNode : "backward"
    zskiplistLevel o--> "1" zskiplistNode : "forward"

4. 核心操作解析

4.1 随机层高生成（`zslRandomLevel()`）

代码片段（t_zset.c）：

1
2
3
4
5
6
7
8
9
#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;
}

硬核解析：

随机性：基于概率P=0.25，每层概率递减（1/4, 1/16...）。
上限：最大层数32，避免过高开销。
意义：层高决定查找效率，平均O(log n)。

4.2 插入节点（`zslInsert()`）

代码片段（t_zset.c）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
zskiplistNode *zslInsert(zskiplist *zl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level = zslRandomLevel();

    x = zl->header;
    for (i = zl->level - 1; i >= 0; i--) {
        rank[i] = i == (zl->level - 1) ? 0 : rank[i + 1];
        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;
    }

    zskiplistNode *node = zslCreateNode(level, score, ele);
    for (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;
    }
    for (i = level; i < zl->level; i++) {
        update[i]->level[i].span++;
    }
    node->backward = (update[0] == zl->header) ? NULL : update[0];
    if (node->level[0].forward)
        node->level[0].forward->backward = node;
    else
        zl->tail = node;
    zl->length++;
    if (level > zl->level) zl->level = level;
    return node;
}

硬核解析：

查找路径：从最高层向下，记录每层的前驱节点（update[]）和累计跨度（rank[]）。
插入逻辑：更新前驱的forward和span，设置新节点的backward。
跨度调整：确保范围查询的正确性。

Mermaid插入流程：

graph TD
    A["zslInsert()"] --> B["zslRandomLevel()"]
    B --> C["创建新节点"]
    C --> D["从顶层查找插入位置"]
    D --> E{"找到前驱节点?"}
    E -->|Yes| F["更新forward和span"]
    F --> G["设置backward"]
    G --> H["更新length和level"]
    H --> I["返回节点"]

4.3 删除节点（`zslDelete()`）

代码片段（t_zset.c）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
int zslDelete(zskiplist *zl, double score, sds ele, zskiplistNode **node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;

    x = zl->header;
    for (i = zl->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)))
            x = x->level[i].forward;
        update[i] = x;
    }
    x = x->level[0].forward;
    if (x && score == x->score && sdscmp(x->ele, ele) == 0) {
        zslDeleteNode(zl, x, update);
        if (node) *node = x; else zslFreeNode(x);
        return 1;
    }
    return 0;
}

硬核解析：

查找：类似插入，找到目标节点。
删除：调整前驱的forward和span，更新backward和tail。

5. 性能分析与优化

时间复杂度：插入、删除、查找平均O(log n)，最坏O(n)。
空间复杂度：O(n)，每节点平均层数约为1/(1-P) ≈ 1.33。
优化：随机层高避免确定性失衡。

6. 总结与调试建议

收获：掌握跳表的实现及其在ZSET中的应用。
调试技巧：用gdb打印跳表层结构（如p zl->header->level[0].forward）。
下一步：探索事件驱动模型。

Redis 源码硬核解析系列专题 - 第四篇：核心数据结构之跳表（Skip List）

相关文章：