Redis 跳跃表核心要点的实战解析

Redis 跳跃表概述

Redis 中的跳跃表（Skip List）是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而实现快速的查找、插入和删除操作。跳跃表的设计灵感来源于一种概率性的数据结构，它在性能上与平衡树类似，但实现起来更加简单。

跳跃表在 Redis 中主要用于实现有序集合（Sorted Set）数据结构。有序集合允许我们对元素进行排序，并根据分数（score）快速查找元素。跳跃表的这种特性使得 Redis 能够高效地处理大量有序数据。

跳跃表的基本结构

一个跳跃表由多层链表组成，最底层的链表包含所有的元素，并且按升序排列。每一层链表都是下面一层链表的“稀疏”版本，也就是说，每一层链表中的节点是下面一层链表节点的子集。

跳跃表节点

在 Redis 中，跳跃表节点由以下几个部分组成：

1. 分值（score）：用于对节点进行排序的数值。
2. 成员对象（obj）：存储的实际数据。
3. 后退指针（backward）：指向前一个节点，用于从尾到头遍历跳跃表。
4. 层（level）：一个数组，包含多个前进指针（forward）和跨度（span）。前进指针用于指向下一个节点，跨度表示当前节点到下一个节点之间的节点数量。

下面是 Redis 中跳跃表节点的 C 语言结构体定义：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

跳跃表

跳跃表结构体包含以下信息：

1. 表头（header）：指向跳跃表的头节点。
2. 表尾（tail）：指向跳跃表的尾节点。
3. 表中节点数量（length）：跳跃表中包含的节点总数。
4. 目前表内节点的最大层数（level）：跳跃表当前的最大层数。

以下是 Redis 中跳跃表的 C 语言结构体定义：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

跳跃表的创建与初始化

创建跳跃表节点

在创建跳跃表节点时，需要分配内存并初始化节点的各个字段。下面是创建跳跃表节点的 C 语言代码示例：

zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = sdsdup(ele);
    zn->backward = NULL;
    for (int i = 0; i < level; i++) {
        zn->level[i].forward = NULL;
        zn->level[i].span = 0;
    }
    return zn;
}

创建跳跃表

创建跳跃表时，需要初始化跳跃表的表头节点，并设置跳跃表的其他属性。以下是创建跳跃表的 C 语言代码示例：

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

跳跃表的插入操作

插入操作是跳跃表的核心操作之一。在插入节点时，需要找到插入位置，并更新相关节点的指针和跨度。

确定插入层数

跳跃表节点的层数是随机生成的，通过一个随机函数来决定。在 Redis 中，这个随机函数会生成一个介于 1 到 ZSKIPLIST_MAXLEVEL 之间的层数。

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

插入节点

插入节点的步骤如下：

1. 查找插入位置：从表头开始，逐层向下查找，找到插入节点应该在的位置。
2. 更新指针和跨度：插入新节点，并更新相关节点的指针和跨度。
3. 随机确定新节点的层数：使用 zslRandomLevel 函数生成新节点的层数。

以下是插入节点的 C 语言代码示例：

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->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;
    }
    x = x->level[0].forward;
    if (x && x->score == score && sdscmp(x->ele,ele) == 0) {
        sdsfree(x->ele);
        x->ele = sdsdup(ele);
        return x;
    } else {
        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);
        for (i = 0; i < level; i++) {
            x->level[i].forward = update[i]->level[i].forward;
            update[i]->level[i].forward = x;
            x->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 < zsl->level; i++) {
            update[i]->level[i].span++;
        }
        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. 调整跳跃表的层数：如果跳跃表的最大层数过高，且没有节点使用该层，则降低跳跃表的最大层数。

以下是删除节点的 C 语言代码示例：

int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;

    x = zsl->header;
    for (i = zsl->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(zsl, x, update);
        if (!zsl->header->level[0].forward)
            zsl->tail = zsl->header;
        else {
            while (zsl->level > 1 &&
                   zsl->header->level[zsl->level-1].forward == NULL)
            {
                zsl->level--;
            }
        }
        zsl->length--;
        if (node)
            *node = x;
        sdsfree(x->ele);
        zfree(x);
        return 1;
    } else {
        if (node)
            *node = NULL;
        return 0;
    }
}

其中 zslDeleteNode 函数用于实际删除节点并更新指针和跨度：

void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
    int i;
    for (i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            update[i]->level[i].span += x->level[i].span - 1;
            update[i]->level[i].forward = x->level[i].forward;
        } else {
            update[i]->level[i].span -= 1;
        }
    }
    if (x->level[0].forward) {
        x->level[0].forward->backward = x->backward;
    } else {
        zsl->tail = x->backward;
    }
}

跳跃表的查找操作

查找操作是跳跃表的基本操作之一。通过跳跃表的多层结构，可以快速定位到目标节点。

查找节点

查找节点的步骤如下：

1. 从表头开始，逐层向下查找。
2. 比较当前节点的分值和目标分值，如果当前节点的分值小于目标分值，则继续沿着当前层的前进指针查找；如果当前节点的分值等于目标分值，再比较成员对象。
3. 如果找到目标节点，则返回该节点；否则返回 NULL。

以下是查找节点的 C 语言代码示例：

zskiplistNode *zslSearch(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x = zsl->header;
    int i;

    for (i = zsl->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;
        }
    }
    x = x->level[0].forward;
    if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
        return x;
    } else {
        return NULL;
    }
}

跳跃表的遍历操作

遍历操作可以按顺序访问跳跃表中的所有节点。由于跳跃表是有序的，遍历操作可以从表头开始，通过前进指针依次访问每个节点。

正向遍历

正向遍历跳跃表的代码示例如下：

void zslForwardTraversal(zskiplist *zsl) {
    zskiplistNode *x = zsl->header->level[0].forward;
    while (x) {
        printf("score: %f, ele: %s\n", x->score, x->ele);
        x = x->level[0].forward;
    }
}

反向遍历

反向遍历跳跃表可以通过节点的后退指针来实现，代码示例如下：

void zslBackwardTraversal(zskiplist *zsl) {
    zskiplistNode *x = zsl->tail;
    while (x && x != zsl->header) {
        printf("score: %f, ele: %s\n", x->score, x->ele);
        x = x->backward;
    }
}

跳跃表在 Redis 有序集合中的应用

在 Redis 中，有序集合是通过跳跃表和哈希表两种数据结构来实现的。跳跃表用于按分值排序，哈希表用于快速查找成员对象。

有序集合的实现

Redis 中有序集合的结构体定义如下：

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

其中，dict 是一个哈希表，用于存储成员对象到分值的映射，以便快速查找成员对象的分值；zsl 是一个跳跃表，用于按分值对成员对象进行排序。

操作示例

下面是一些 Redis 有序集合操作的示例代码，使用 Redis 提供的 API 来操作有序集合：

#include <stdio.h>
#include <hiredis/hiredis.h>

int main() {
    redisContext *c = redisConnect("127.0.0.1", 6379);
    if (c == NULL || c->err) {
        if (c) {
            printf("Connection error: %s\n", c->errstr);
            redisFree(c);
        } else {
            printf("Connection error: can't allocate redis context\n");
        }
        return 1;
    }

    // 添加成员到有序集合
    redisReply *reply = (redisReply *)redisCommand(c, "ZADD myzset 1 \"one\"");
    freeReplyObject(reply);

    reply = (redisReply *)redisCommand(c, "ZADD myzset 2 \"two\"");
    freeReplyObject(reply);

    // 获取有序集合的成员数量
    reply = (redisReply *)redisCommand(c, "ZCARD myzset");
    printf("Number of members in myzset: %lld\n", reply->integer);
    freeReplyObject(reply);

    // 按分值范围获取成员
    reply = (redisReply *)redisCommand(c, "ZRANGEBYSCORE myzset 0 2");
    for (int i = 0; i < reply->elements; i++) {
        printf("Member: %s\n", reply->element[i]->str);
    }
    freeReplyObject(reply);

    redisFree(c);
    return 0;
}

跳跃表的性能分析

跳跃表的时间复杂度在平均情况下，查找、插入和删除操作的时间复杂度均为 O(log n)，其中 n 是跳跃表中节点的数量。这是因为跳跃表通过多层结构，能够快速跳过大量节点，减少查找次数。

在最坏情况下，跳跃表的查找、插入和删除操作的时间复杂度为 O(n)，这种情况发生在跳跃表的层数退化为 1 层时，此时跳跃表退化为普通的有序链表。

空间复杂度方面，跳跃表的空间复杂度为 O(n log n)，因为每个节点平均需要 O(log n) 个指针。然而，在实际应用中，跳跃表的空间开销通常是可以接受的，并且相对于其他平衡树结构，跳跃表的实现更加简单。

总结跳跃表的优势与不足

优势

1. 实现简单：相比平衡树等复杂的数据结构，跳跃表的实现相对简单，代码量少，易于理解和维护。
2. 性能高效：在平均情况下，跳跃表的查找、插入和删除操作的时间复杂度与平衡树相当，均为 O(log n)。
3. 灵活性高：跳跃表的节点层数是随机生成的，这使得跳跃表在不同数据分布下都能保持较好的性能。

不足

1. 空间开销较大：由于每个节点需要额外存储多个指针，跳跃表的空间复杂度为 O(n log n)，相比一些其他数据结构，空间开销较大。
2. 最坏情况性能较差：在最坏情况下，跳跃表的层数可能退化为 1 层，此时查找、插入和删除操作的时间复杂度会退化为 O(n)。

跳跃表在其他场景中的应用

除了 Redis 有序集合外，跳跃表还可以应用于其他需要有序数据结构的场景，例如：

1. 数据库索引：可以作为数据库索引的数据结构，提高查询效率。
2. 操作系统调度：在操作系统的调度算法中，可以使用跳跃表来管理任务队列，根据任务的优先级进行快速调度。
3. 网络路由：在网络路由算法中，跳跃表可以用于快速查找路由表中的条目。

通过深入理解跳跃表的核心要点，并结合实际应用场景，我们可以更好地利用跳跃表这种数据结构，提高程序的性能和效率。在实际开发中，根据具体需求和数据规模，合理选择数据结构是优化程序性能的关键步骤之一。