Redis 跳跃表的构建与维护技巧

Redis 跳跃表简介

在 Redis 中，跳跃表（Skip List）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表在 Redis 中主要用于实现有序集合（Sorted Set）数据结构，它提供了一种可以在平均 O(log n)、最坏 O(n) 的时间复杂度下完成查找、插入和删除操作的数据结构，性能上与平衡树相近，但是实现相对简单，更易于理解和维护。

跳跃表的基本思想是通过建立多层次的链表结构，每一层链表都是上一层链表的子集。高层链表中的节点稀疏，而底层链表中的节点密集。这样，在查找元素时，可以从高层链表开始，快速跳过大量不需要的节点，逐渐降低层次，直到找到目标节点，从而提高查找效率。

跳跃表的构建

跳跃表节点结构

在 Redis 中，跳跃表节点由 zskiplistNode 结构体表示，其定义如下：

typedef struct zskiplistNode {
    sds ele; // 成员对象，这里是字符串
    double score; // 分值，用于排序
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span; // 跨度，表示当前节点到下一个节点之间的距离
    } level[]; // 层，柔性数组，实际的层数根据需要动态分配
} zskiplistNode;

ele 字段存储节点的值，score 字段用于节点的排序。backward 指针指向前一个节点，方便在遍历跳跃表时反向移动。level 是一个柔性数组，其实际大小在运行时确定，每个 zskiplistLevel 结构体包含一个 forward 指针和一个 span 跨度。

跳跃表结构

跳跃表整体由 zskiplist 结构体表示，定义如下：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 表头和表尾节点
    unsigned long length; // 跳跃表的节点数量
    int level; // 跳跃表的当前层数
} zskiplist;

header 是跳跃表的表头节点，tail 是表尾节点。length 记录跳跃表中节点的总数，level 表示当前跳跃表的层数。

创建跳跃表

下面是创建一个新的跳跃表的代码示例：

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;
}

在这个函数中，首先分配了跳跃表结构体 zskiplist 的内存，然后初始化其层数为 1，长度为 0。接着创建了表头节点 zslCreateNode，并初始化表头节点的每一层的前进指针和跨度。最后将表尾节点初始化为 NULL。

随机层数生成

跳跃表在插入节点时，需要为新节点随机生成层数。这个随机层数的生成决定了节点在跳跃表中的层次结构，对跳跃表的性能有重要影响。在 Redis 中，使用如下方法生成随机层数：

int zslRandomLevel(void) {
    int level = 1;
    // 以 1/4 的概率增加层数
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

这里的 ZSKIPLIST_P 定义为 0.25，意味着节点层数有 25% 的概率增加一层。通过这种随机化的方式，可以使跳跃表的结构在平均情况下接近理想的平衡状态，从而保证较好的查找性能。

插入节点

插入节点是跳跃表构建过程中的关键操作。下面是插入节点的代码示例：

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 && score == x->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;
    }
}

在插入节点时，首先通过 update 数组记录从高层到低层需要修改指针的节点，通过 rank 数组记录从表头到当前节点的跨度。然后查找插入位置，如果找到相同分值和元素的节点，则更新元素值。否则，生成随机层数，创建新节点并插入到跳跃表中，同时更新相关指针和跨度信息。

跳跃表的维护

删除节点

删除节点是跳跃表维护操作中的重要部分。下面是删除节点的代码示例：

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) {
        // 调整指针
        if (node != NULL) *node = x;
        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;
        // 调整跳跃表的层数
        while (zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
            zsl->level--;
        // 释放节点内存
        zslFreeNode(x);
        // 更新跳跃表的长度
        zsl->length--;
        return 1;
    }
    return 0;
}

在删除节点时，同样通过 update 数组记录需要修改指针的节点。找到要删除的节点后，调整相关指针和跨度信息，更新后退指针，并根据情况调整跳跃表的层数，最后释放节点内存并更新跳跃表的长度。

查找节点

查找节点是跳跃表的基本操作之一，通过从高层链表开始逐步查找，可以快速定位到目标节点。下面是查找节点的代码示例：

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;
    }
    return NULL;
}

查找节点时，从跳跃表的表头开始，在每一层链表中根据分值和元素值进行比较，逐步移动到下一个节点，直到找到目标节点或者确定目标节点不存在。

遍历跳跃表

遍历跳跃表可以从表头开始，通过前进指针依次访问每个节点。下面是正向遍历跳跃表的代码示例：

void zslTraverseForward(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;
    }
}

通过 zsl->header->level[0].forward 获取第一个实际节点，然后通过 x->level[0].forward 不断移动到下一个节点，直到节点为 NULL，从而完成正向遍历。

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

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

从表尾节点 zsl->tail 开始，通过 x->backward 不断移动到前一个节点，直到回到表头节点，完成反向遍历。

跳跃表性能分析

查找性能

在平均情况下，跳跃表的查找操作时间复杂度为 O(log n)。这是因为在每一层链表中，平均可以跳过一半的节点。例如，假设有 n 个节点的跳跃表，第一层链表有 n 个节点，第二层链表大约有 n/2 个节点，第三层链表大约有 n/4 个节点，以此类推。在查找时，从最高层链表开始，每下降一层，需要遍历的节点数大致减半。

然而，在最坏情况下，跳跃表的查找时间复杂度为 O(n)。例如，当所有节点的层数都为 1 时，跳跃表退化为普通链表，查找操作就需要遍历所有节点。

插入和删除性能

插入和删除操作的时间复杂度与查找操作类似。插入节点时，首先需要查找插入位置，然后调整指针和跨度信息。删除节点时，同样需要先查找节点，再调整指针和跨度。在平均情况下，插入和删除操作的时间复杂度也为 O(log n)，最坏情况下为 O(n)。

跳跃表与其他数据结构的比较

与平衡树比较

平衡树（如 AVL 树、红黑树）也可以在 O(log n) 的时间复杂度下完成查找、插入和删除操作。但是平衡树的实现相对复杂，需要维护节点的平衡因子或者颜色等额外信息，并且在插入和删除节点后需要进行复杂的旋转操作来保持平衡。而跳跃表通过随机化的层数生成，在平均情况下能够达到与平衡树相近的性能，且实现相对简单，代码量更少，更易于理解和维护。

与普通链表比较

普通链表在查找操作上的时间复杂度为 O(n)，因为需要依次遍历每个节点。而跳跃表通过多层次的链表结构，可以在平均 O(log n) 的时间复杂度下完成查找，大大提高了查找效率。在插入和删除操作上，虽然普通链表的插入和删除操作在已知位置时时间复杂度为 O(1)，但在实际应用中，往往需要先查找位置，整体时间复杂度仍为 O(n)，而跳跃表在平均情况下插入和删除的时间复杂度为 O(log n)，具有明显优势。

总结

Redis 跳跃表作为一种高效的有序数据结构，在 Redis 的有序集合实现中发挥了重要作用。通过合理的节点结构设计、随机层数生成以及插入、删除、查找等操作的优化，跳跃表在平均情况下能够提供接近平衡树的性能，同时保持了相对简单的实现。了解跳跃表的构建与维护技巧，对于深入理解 Redis 的有序集合以及优化相关应用具有重要意义。无论是在大数据存储、排序还是其他需要有序数据结构的场景中，跳跃表都能展现出其独特的优势。