Redis学习笔记-跳跃表

参考资料

redis设计与实现（第二版）
redis-7.0 源码

1. 跳跃表数据结构

跳跃表底层是一个有层级的有序链表，数据结构如下

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 跳跃表表头、表尾指针
    unsigned long length; // 记录跳跃表中节点数量（表头节点的层数不计算在内）
    int level; // 跳跃表中层级最大节点的层级（表头节点的层数不计算在内）
} zskiplist;
1
2
3
4
5

跳跃表中的每个节点数据结构如下

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele; // 当前节点的值
    double score; // 当前节点的score，用于排序
    struct zskiplistNode *backward; // 后退指针，用于访问上一个节点
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针，用于访问下一个节点
        unsigned long span; // 当前节点与下一个节点的距离
    } level[]; // 前进指针数组
} zskiplistNode;
1
2
3
4
5
6
7
8
9
10

2. 新建跳跃表

注意： 跳跃表表头节点不计入节点总数

3. 向跳跃表插入节点

插入步骤简单描述如下

1. 逐层遍历跳跃表，在每一层中，顺序查找待插入节点的上一个节点指针
2. 为待插入节点随机生成一个level
3. 根据待插入节点的level逐层遍历，将待插入节点插入到跳跃表中，更新相关节点的前进指针和前进步长
4. 如果节点的level低于跳跃表的level，对于第3步中未到达的level，需要更新其中部分节点的前进步长level[i].span
5. 更新第0层中相关节点的后退指针backward
6. 更新跳跃表level、length和tail

详细可以看下面的Redis源码

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    // update数组记录了每一层中，待插入节点的上一个节点指针
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    // rank记录了每一层中，待插入节点的上一个节点指针距离表首指针的距离
    unsigned long rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    // 从跳跃表最上层开始逐层遍历，在每一层中顺序查找待插入元素的插入位置
    serverAssert(!isnan(score));
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        
        /* 如果“x节点前进指针的score大于待插入节点的score”，或者“score相等时，x前进指针的ele字典顺序大于ele”，
         * 则说明待插入节点的插入位置在x后面，此时将x记录到update数组中；否则继续向后遍历
         */
        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;
    }
    /* 为待插入节点随机生成level，范围在1-32之间，从第一层开始，层数加1的概率均为0.25，level=n的概率为0.25^(n-1) */
    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    x = zslCreateNode(level,score,ele);
    
    /* 从待插入节点的level开始逐层遍历，更新信息如下，
     *  1.更新待插入节点的前进指针和前进步长
     *  2.更新插入位置节点的前进指针和前进步长
     */
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;

        /* update span covered by update[i] as x is inserted here */
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* 如果待插入节点的level小于跳跃表level，那么较高层级中节点的步长信息需要额外更新 */
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    /* 更新第0层中，待插入节点及后面节点的后退指针，注意事项如下
     *  1.新插入节点的后退指针如果是表头指针，那么要将新插入节点的后退指针设置为NULL
     *  2.如果新插入节点没有前 vb                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             
     */
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69