Redis 跳跃表重点技术的深入解析

Redis 跳跃表概述

在 Redis 众多的数据结构中，跳跃表（Skip List）是一种独特且高效的数据结构，它主要用于实现有序集合（Sorted Set）。跳跃表以一种巧妙的方式，结合了链表和二分查找的思想，为有序数据的存储和操作提供了一种平衡的解决方案。

与传统的平衡二叉树（如红黑树）相比，跳跃表的实现相对简单，且在平均情况下具有与平衡二叉树相近的时间复杂度。它允许在对数时间内完成插入、删除和查找操作，这种高效性使得它在 Redis 的有序集合实现中扮演着重要角色。

跳跃表的结构

节点结构

跳跃表的基本组成单元是节点（Node）。每个节点包含以下几个关键部分：

分值（Score）：用于对节点进行排序的数值。在 Redis 的有序集合中，每个元素都有一个与之关联的分值，通过分值来确定元素在跳跃表中的位置。
成员对象（Member Object）：存储实际的数据元素，例如在有序集合中可能是字符串等。
层（Level）：节点中的一个数组，用于存储指向其他节点的指针。层数是随机生成的，这也是跳跃表实现高效查找的关键所在。

以下是一个简化的跳跃表节点结构的代码示例（以 C 语言为例，Redis 源码使用 C 实现跳跃表）：

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

在上述代码中，ele 存储成员对象（这里使用 sds 即简单动态字符串来存储），score 是分值，backward 指针用于指向前一个节点，方便逆向遍历。level 数组则存储了不同层的指针信息，span 记录了当前层到下一个节点跨越的节点数。

跳跃表结构

跳跃表整体由多个节点组成，并且有一个表头（Header）和表尾（Tail）。表头是一个特殊的节点，它的层数是跳跃表中最大的层数，且表头不存储实际的数据元素。表尾则为 NULL 指针，表示跳跃表的结束。

除了表头和表尾，跳跃表还维护了一些元数据，例如跳跃表的长度（节点数量，不包括表头）和当前最大层数等信息。以下是跳跃表结构的代码示例：

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

在这个结构中，header 和 tail 分别指向跳跃表的表头和表尾，length 记录跳跃表的长度，level 表示当前跳跃表的最大层数。

跳跃表的工作原理

随机层数生成

跳跃表的高效性很大程度上依赖于节点层数的随机生成。当一个新节点插入到跳跃表中时，需要为其随机生成一个层数。Redis 中采用了一种简单的概率算法来生成层数。

具体来说，在 Redis 的实现中，节点层数的生成是基于一个概率为 1/2 的随机过程。每次生成一个 0 到 1 之间的随机数，如果随机数小于 0.5，则层数加 1，直到达到最大层数限制或者随机数不满足条件为止。这样生成的节点层数大致符合泊松分布，使得跳跃表的结构在平均情况下能够保持较好的平衡性。

以下是生成随机层数的代码示例（简化版）：

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

在这段代码中，ZSKIPLIST_P 是一个概率常数，通常设置为 0.25，ZSKIPLIST_MAXLEVEL 是最大层数限制，Redis 中默认设置为 32。

查找操作

跳跃表的查找操作利用了其多层结构的特性。当进行查找时，从表头的最高层开始，沿着当前层的 forward 指针向前遍历。如果当前节点的下一个节点的分值大于要查找的分值，或者下一个节点为 NULL，则降低一层继续查找。

例如，假设要在跳跃表中查找分值为 targetScore 的节点。从表头的最高层开始，比较当前节点下一个节点的分值与 targetScore。如果下一个节点的分值小于 targetScore，则继续沿着当前层前进；如果下一个节点的分值大于 targetScore，则移动到当前节点下一层的指针位置，继续比较。重复这个过程，直到找到分值等于 targetScore 的节点，或者确定跳跃表中不存在该分值的节点。

以下是查找操作的代码示例：

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

在上述代码中，首先从最高层开始遍历，通过比较分值和成员对象来确定前进方向。最后在最底层检查是否找到目标节点。

插入操作

插入操作需要先找到插入位置，这与查找操作类似。找到插入位置后，根据随机生成的层数为新节点分配空间，并更新相关节点的指针。

具体步骤如下：

与查找操作一样，从表头的最高层开始，找到新节点应该插入的位置。在查找过程中，记录下每一层需要更新指针的节点。
为新节点随机生成层数。
根据生成的层数为新节点分配内存空间，并初始化新节点的分值、成员对象等信息。
更新跳跃表中相关节点的指针，将新节点插入到跳跃表中。同时更新插入位置相关节点的 span 信息。

以下是插入操作的代码示例：

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) {
        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) {
        zslDeleteNode(zsl, x, update);
        if (!node)
            zslFreeNode(x);
        return 1;
    } else {
        return 0;
    }
}

在这个代码中，zslDeleteNode 函数负责实际的节点删除和指针更新操作，zslFreeNode 函数用于释放节点的内存。

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

在 Redis 中，有序集合是通过跳跃表和哈希表两种数据结构来实现的。哈希表用于快速查找成员对象，而跳跃表则用于实现有序性和高效的范围查询。

当对有序集合进行插入、删除或查找操作时，Redis 首先会在哈希表中快速定位成员对象是否存在，然后根据需要在跳跃表中进行相应的操作。这种结合使用两种数据结构的方式，使得 Redis 的有序集合在保持高效查找的同时，还能支持按照分值进行排序和范围查询等操作。

例如，在 ZRANGE 命令中，Redis 会利用跳跃表的有序性，快速定位到指定范围的节点，并返回相应的成员对象。在 ZADD 命令中，首先在哈希表中检查成员是否已存在，然后在跳跃表中插入新节点（如果是新成员）。

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

与平衡二叉树比较

实现复杂度：平衡二叉树（如红黑树）的实现相对复杂，需要维护树的平衡性质，插入和删除操作后可能需要进行多次旋转操作来保持平衡。而跳跃表的实现相对简单，其随机层数生成和节点插入删除操作相对直观。
时间复杂度：在平均情况下，跳跃表和平衡二叉树都能在 O(log n) 的时间复杂度内完成插入、删除和查找操作。但在最坏情况下，平衡二叉树可以保证 O(log n) 的时间复杂度，而跳跃表在极端情况下（如所有节点层数都很低），时间复杂度可能会退化到 O(n)，不过这种情况发生的概率极低。
空间复杂度：跳跃表每个节点需要额外存储多层指针，因此空间复杂度相对较高，为 O(n log n)。平衡二叉树每个节点只需要存储左右子节点指针，空间复杂度为 O(n)。

与普通链表比较

查找效率：普通链表查找操作的时间复杂度为 O(n)，需要从头到尾依次遍历。而跳跃表通过多层结构和随机层数生成，平均情况下查找时间复杂度为 O(log n)，大大提高了查找效率。
插入和删除操作：普通链表插入和删除操作在找到位置后，时间复杂度为 O(1)，但查找位置的时间复杂度较高。跳跃表虽然插入和删除操作本身相对复杂，需要更新多层指针，但由于其高效的查找方式，总体上在平均情况下插入和删除的时间复杂度也为 O(log n)。

跳跃表的优化与扩展

优化

减少内存占用：可以通过一些方式优化跳跃表的内存占用。例如，对于层数较低的节点，可以采用更紧凑的存储方式，减少不必要的指针空间浪费。另外，可以对节点的元数据（如 span）采用更高效的编码方式，以节省内存。
提高查询性能：在某些场景下，可以通过预计算和缓存一些信息来提高查询性能。比如，对于频繁查询的范围，可以提前计算并存储相关的节点位置信息，这样在查询时可以直接定位，减少查找时间。

扩展

多维度跳跃表：传统跳跃表主要基于单一分值进行排序和操作。可以扩展跳跃表结构，使其支持多维度的数据排序和查询。例如，在一个二维空间中，节点可以同时根据两个维度的坐标进行排序，通过多层结构实现高效的二维范围查询。
分布式跳跃表：在分布式系统中，可以将跳跃表进行分布式扩展。每个节点存储部分数据，并通过某种分布式协议进行数据同步和一致性维护。这样可以利用分布式系统的优势，处理大规模的有序数据。

总结

跳跃表作为 Redis 有序集合实现的重要数据结构，以其独特的设计和高效的性能，在 Redis 的数据处理中发挥着关键作用。通过深入理解跳跃表的结构、工作原理以及在 Redis 中的应用，我们可以更好地利用 Redis 的有序集合功能，优化我们的应用程序。同时，对跳跃表的优化和扩展研究，也为解决更多复杂的数据处理问题提供了思路。无论是在单机环境还是分布式系统中，跳跃表都有着广阔的应用前景。