Redis 跳跃表的性能提升关键因素

Redis 跳跃表简介

在 Redis 中，跳跃表（Skip List）是一种数据结构，用于实现有序集合（Sorted Set）。跳跃表提供了一种平衡时间复杂度和空间复杂度的数据存储与查找方式。

跳跃表的基本思想是通过在不同层次上构建链表来加速查找操作。普通链表在查找元素时，平均时间复杂度为 O(n)，因为需要从头遍历到目标元素。而跳跃表通过引入多层链表结构，使得在查找时可以跳过一些节点，从而提高查找效率。

一个跳跃表由多条链表组成，最底层的链表包含所有元素，而上层链表是下层链表的子集。例如，假设有一个包含元素 [1, 3, 5, 7, 9] 的跳跃表，最底层链表包含所有这些元素。上一层链表可能只包含 [1, 5, 9]，再上一层可能只包含 [1, 9]。这样，在查找元素时，就可以先在高层链表中快速定位大致范围，然后再在低层链表中精确查找。

跳跃表的节点结构

在 Redis 中，跳跃表节点的结构体定义如下：

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

ele：存储元素的成员，是一个 SDS（Simple Dynamic String）类型，用于保存字符串值。
score：存储元素的分值，用于排序。当多个元素的分值相同时，会按照 ele 的字典序进行排序。
backward：指向前一个节点的指针，用于反向遍历。
level：这是一个柔性数组（Flexible Array Member），表示节点的不同层次。每个层次包含一个指向下一个节点的 forward 指针和一个 span，span 记录了从当前节点到 forward 指向节点之间的距离，用于计算排名。

跳跃表的结构

跳跃表本身也有一个结构体来表示：

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

header：指向跳跃表的头节点，头节点的层次比较特殊，它的层次数在初始化时被设置为一个较大的值（如 32），并且头节点不存储实际元素。
tail：指向跳跃表的尾节点，方便快速找到链表末尾。
length：记录跳跃表中包含的节点数量（不包括头节点）。
level：记录当前跳跃表的最高层次。

性能提升关键因素

多层链表结构

跳跃表性能提升的核心在于多层链表结构。通过构建多层链表，查找操作可以在高层链表中快速跳过大量节点。例如，在一个包含 1000 个元素的跳跃表中，如果最高层链表只有 10 个元素，那么在查找时，首先在高层链表中查找，平均只需要遍历 5 次（假设均匀分布），就可以确定目标元素大致所在的范围。然后再在低层链表中进行精确查找，这样大大减少了总的查找次数。

假设跳跃表的高度为 h，每层链表的节点数为 n1, n2, ..., nh，且每层链表的节点数大致满足 ni = ni+1 * 2（理想情况下）。那么查找一个元素的时间复杂度可以分析如下：在最高层链表查找的时间复杂度为 O(log n)，因为节点数大致以 2 的倍数递减。然后在底层链表中精确查找的时间复杂度为 O(1)（假设已经在高层链表中定位到大致范围）。所以总的查找时间复杂度为 O(log n)。

随机化层次生成

在 Redis 跳跃表中，每个节点的层次是随机生成的。这是保证跳跃表性能的另一个关键因素。生成节点层次的函数如下：

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，即每个节点有 25% 的概率增加一个层次。通过这种随机化的层次生成方式，可以使得跳跃表的结构更加平衡，避免出现某一层链表过长或过短的情况。如果层次生成不是随机的，可能会导致某些高层链表节点分布不均匀，从而影响查找性能。

例如，如果所有节点都集中在某一层链表，那么跳跃表就退化为普通链表，查找性能将从 O(log n) 退化为 O(n)。而随机化层次生成能够在一定程度上保证每层链表的节点分布相对均匀，从而维持较好的查找性能。

跨度（span）的使用

跳跃表节点中的 span 字段记录了从当前节点到 forward 指向节点之间的距离。这个字段在计算元素排名时非常有用。在查找元素时，虽然 span 字段本身不直接参与查找操作，但它对于计算排名是必不可少的。

当需要获取某个元素的排名时，可以从跳跃表的头节点开始，沿着不同层次的链表遍历。在遍历过程中，通过累加经过节点的 span 值，就可以得到目标元素的排名。例如，在查找元素 x 的排名时，从最高层链表开始，当在某一层链表中从节点 A 移动到节点 B 时，将节点 A 的 span 值累加到排名计数器中。这样，当找到目标元素时，排名计数器中的值就是该元素的排名。

这种通过 span 计算排名的方式，使得获取元素排名的操作时间复杂度也为 O(log n)，与查找操作的时间复杂度相同，进一步提升了跳跃表在有序集合中的整体性能。

插入操作与性能提升

在跳跃表中插入一个新元素时，需要先找到合适的插入位置。这个查找位置的过程与普通查找操作类似，也是从高层链表开始，逐步向下层链表查找。

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

在插入新节点后，需要更新相关节点的 span 值以及链表的结构。由于查找插入位置的时间复杂度为 O(log n)，且更新操作的时间复杂度也与查找相关，所以插入操作的平均时间复杂度也是 O(log n)。

在插入操作中，随机化层次生成同样起到了重要作用。新插入节点的层次随机生成，能够保持跳跃表结构的平衡，避免因连续插入元素导致某一层链表过长或过短，从而保证插入操作以及后续查找等操作的性能。

删除操作与性能提升

跳跃表的删除操作也需要先查找目标节点，然后调整链表结构。

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

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

删除操作首先通过查找找到目标节点及其前驱节点（记录在 update 数组中）。找到目标节点后，通过调整前驱节点的 forward 指针以及相关节点的 span 值来删除节点。如果删除节点后导致某一层链表为空，还需要调整跳跃表的层次。

由于查找目标节点的时间复杂度为 O(log n)，且后续调整链表结构的操作与查找相关，所以删除操作的平均时间复杂度也是 O(log n)。这保证了在删除元素时，跳跃表依然能够保持高效的性能。

与其他数据结构的性能对比

与普通链表对比

普通链表在查找元素时，平均需要遍历链表的一半节点，时间复杂度为 O(n)。而跳跃表通过多层链表结构和随机化层次生成，平均查找时间复杂度为 O(log n)。在元素数量较多时，跳跃表的查找性能远远优于普通链表。

例如，在一个包含 10000 个元素的集合中，普通链表查找一个元素平均需要遍历 5000 次，而跳跃表平均只需要遍历大约 14 次（假设以 2 为底数的对数）。

与平衡树对比

平衡树（如 AVL 树、红黑树）在查找、插入和删除操作上的时间复杂度也是 O(log n)。然而，跳跃表在实现上相对简单，不需要像平衡树那样维护复杂的平衡条件。

在插入和删除操作中，平衡树可能需要进行多次旋转操作来保持平衡，而跳跃表通过随机化层次生成和简单的指针调整即可完成。这使得跳跃表在实现和维护上更加容易，并且在一些场景下性能表现与平衡树相当甚至更好。

例如，在 Redis 的有序集合场景中，跳跃表的简单实现和良好性能使其成为一个非常合适的数据结构选择。

实际应用场景中的性能优化

在实际应用中，为了进一步提升跳跃表的性能，可以考虑以下几点：

预分配内存

在创建跳跃表或插入大量元素时，可以预先分配足够的内存，减少动态内存分配的次数。动态内存分配（如 malloc 和 free）通常有一定的开销，特别是在频繁操作时。通过预分配内存，可以将这些开销分摊到较少的操作中，提高整体性能。

例如，可以在初始化跳跃表时，根据预计的元素数量，预先分配足够的节点内存。这样在插入元素时，只需要使用预先分配的内存，而不需要频繁调用 malloc。

批量操作

对于插入或删除操作，可以采用批量操作的方式。将多个插入或删除操作合并为一次操作，减少链表结构调整的次数。

例如，在需要插入 100 个元素时，如果逐个插入，每次插入都需要调整链表结构和相关节点的 span 值，会有较大的开销。而批量插入时，可以一次性找到所有元素的插入位置，然后统一调整链表结构，这样可以大大减少操作的总开销。

缓存机制

在某些场景下，可以结合缓存机制来提升跳跃表的性能。例如，如果经常查询某些特定元素，可以将这些元素及其相关信息（如排名等）缓存起来。这样在下次查询时，可以直接从缓存中获取，避免在跳跃表中进行查找操作。

缓存可以使用 Redis 自身的缓存机制，也可以采用其他缓存技术（如 Memcached 等）。通过合理设置缓存的过期时间和更新策略，可以在保证数据一致性的前提下，显著提升查询性能。

总结

Redis 跳跃表通过多层链表结构、随机化层次生成以及跨度的使用等关键因素，实现了高效的查找、插入和删除操作，平均时间复杂度为 O(log n)。与其他数据结构相比，跳跃表在实现上相对简单，且在有序集合等场景中有良好的性能表现。

在实际应用中，通过预分配内存、批量操作和缓存机制等优化手段，可以进一步提升跳跃表的性能。理解和掌握这些性能提升关键因素，对于在 Redis 开发以及其他需要有序集合数据结构的场景中优化性能具有重要意义。