Redis 跳跃表在搜索场景中的应用优势

Redis 跳跃表简介

Redis 跳跃表（Skip List）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表可以看成是一种随机化的数据结构，它的平均时间复杂度和平衡树类似，插入、删除、查找操作平均时间复杂度均为 $O(\log n)$，空间复杂度为 $O(n)$。

跳跃表的结构

跳跃表由多层链表组成，最底层的链表包含所有元素，并且按升序排列。每一层链表都是下面一层链表的“稀疏版本”。具体来说，每个节点都有多个“前进”指针，层数越高，指针跨度越大。

例如，假设我们有一个跳跃表存储数字 1, 2, 3, 4, 5。最底层链表是 1 -> 2 -> 3 -> 4 -> 5。在第二层链表，可能只有 1 -> 3 -> 5，在第三层链表，可能只有 1 -> 5。

节点结构

在 Redis 中，跳跃表节点的结构定义如下（简化版 C 语言代码示例）：

typedef struct zskiplistNode {
    sds ele; // 元素
    double score; // 分值，用于排序
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span; // 跨度，表示当前指针到下一个节点的距离
    } level[]; // 层，根据实际需要动态分配
} zskiplistNode;

跳跃表的创建

创建跳跃表时，首先要初始化表头节点。表头节点比较特殊，它的层数是固定的，一般会初始化为一个较大的值（如 32 层），但实际使用的层数会在插入节点时动态调整。

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 跳跃表在搜索场景中的应用优势

快速定位

在搜索场景中，快速定位目标元素至关重要。跳跃表通过多层链表结构，可以快速跳过大量无关节点。例如，当我们要查找一个较大值的元素时，从高层链表开始查找，高层链表的指针跨度大，能够快速定位到一个大致范围，然后再逐层向下查找，逐步缩小范围，最终找到目标元素。

假设我们要在跳跃表中查找元素 4。从高层链表开始，发现 1 之后直接到了 5，于是向下一层查找，发现 1 之后是 3，再向下一层，就找到了 4。这种方式避免了从最底层链表逐个节点遍历，大大提高了查找效率。

范围查询高效

在许多搜索场景中，不仅需要查找单个元素，还经常需要进行范围查询，比如查找分值在某个区间内的所有元素。跳跃表在这方面表现出色。

由于跳跃表是有序结构，我们可以通过从表头开始，利用多层链表快速定位到范围的起始点，然后沿着底层链表顺序遍历，直到超出范围为止。例如，要查找分值在 3 到 5 之间的元素，我们可以先快速定位到 3，然后沿着底层链表依次取出 3、4、5。

动态插入与删除不影响查询效率

在实际搜索场景中，数据往往是动态变化的，需要频繁进行插入和删除操作。跳跃表在插入和删除节点时，平均时间复杂度为 $O(\log n)$，并且不会破坏跳跃表的整体结构，从而保证了查询效率不受影响。

当插入一个新节点时，首先要确定新节点的层数。Redis 中采用一种随机化的方式来确定新节点的层数，这样可以保证跳跃表结构的随机性和平衡性。然后，根据新节点的分值，在跳跃表中找到合适的插入位置，并更新相应的指针。

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

删除节点时，同样需要先找到要删除的节点，然后更新相关指针。如果删除节点后，跳跃表的高层链表变得过于稀疏，还会调整跳跃表的层数。

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->length) {
            zsl->tail = zsl->header;
        } else {
            while (zsl->level > 1 &&
                   zsl->header->level[zsl->level - 1].forward == NULL)
            {
                zsl->level--;
            }
        }
        if (node) {
            *node = x;
        }
        zslFreeNode(x);
        return 1;
    } else {
        if (node) {
            *node = NULL;
        }
        return 0;
    }
}

内存友好

相比于一些复杂的平衡树结构，跳跃表的实现相对简单，内存开销较小。每个节点除了存储元素本身和分值外，只需要额外存储指针信息。虽然跳跃表需要额外的空间来存储多层链表结构，但由于其随机化的特点，在实际应用中，跳跃表的空间复杂度是可以接受的。

此外，跳跃表的节点内存分配相对灵活，可以根据实际需要动态调整层数，避免了像一些平衡树结构那样为了维持严格的平衡条件而需要大量复杂的操作和额外的内存开销。

易于实现与维护

跳跃表的实现相对直观，代码逻辑清晰。与一些复杂的平衡树算法（如红黑树）相比，跳跃表的插入、删除和查找操作的代码实现更容易理解和维护。这使得开发人员在使用跳跃表时，能够更快地掌握其原理和实现细节，降低了开发和维护的成本。

同时，跳跃表的随机化结构使得它在面对不同的数据分布时，都能保持较好的性能表现，不需要像一些平衡树那样针对特定的数据分布进行复杂的调整。

与其他数据结构在搜索场景中的对比

与二叉搜索树对比

二叉搜索树在理想情况下，查找、插入和删除操作的时间复杂度为 $O(\log n)$。然而，当数据分布不均匀时，二叉搜索树可能会退化为链表，时间复杂度变为 $O(n)$。例如，当插入的数据是有序的，二叉搜索树会形成一条单链，此时搜索效率极低。

而跳跃表通过多层链表结构和随机化的层数确定方式，能够在各种数据分布情况下保持平均 $O(\log n)$ 的时间复杂度，不会出现像二叉搜索树那样极端的退化情况。

与平衡树对比

平衡树（如 AVL 树、红黑树）能够保证在任何情况下，查找、插入和删除操作的时间复杂度为 $O(\log n)$。但是，平衡树的实现非常复杂，需要严格维护树的平衡条件。在插入和删除节点时，可能需要进行多次旋转操作来恢复平衡，这增加了代码的复杂性和维护成本。

跳跃表虽然平均时间复杂度与平衡树相同，但实现简单，不需要像平衡树那样进行复杂的旋转操作。在一些对实现复杂度有要求的场景中，跳跃表更具优势。

与哈希表对比

哈希表在查找单个元素时，平均时间复杂度为 $O(1)$，在这方面表现非常出色。然而，哈希表不支持范围查询，并且哈希表中的元素是无序的。如果需要进行范围查询或者按照某种顺序遍历元素，哈希表就无法满足需求。

而跳跃表不仅可以快速查找单个元素，还能高效地进行范围查询，并且元素是有序存储的，这使得跳跃表在搜索场景中有更广泛的应用。

在 Redis 中的实际应用场景

有序集合（Sorted Set）

Redis 的有序集合是基于跳跃表和哈希表实现的。有序集合中的每个元素都有一个分值，通过跳跃表可以按照分值对元素进行排序，从而实现快速的范围查询和排名操作。

例如，在一个排行榜应用中，我们可以使用 Redis 的有序集合来存储用户的分数，通过跳跃表结构，能够快速查询某个分数段内的用户列表，或者获取某个用户的排名。

import redis

r = redis.Redis(host='localhost', port=6379, db=0)

# 添加元素到有序集合
r.zadd('scores', {'user1': 100, 'user2': 80, 'user3': 90})

# 获取分数在 80 到 100 之间的元素
result = r.zrangebyscore('scores', 80, 100)
print(result)

时间序列数据处理

在时间序列数据场景中，数据通常按照时间戳进行排序。Redis 可以使用跳跃表来存储时间序列数据，通过时间戳作为分值，能够快速查询某个时间范围内的数据。

例如，在监控系统中，需要记录服务器在不同时间点的性能指标（如 CPU 使用率、内存使用率等）。可以将时间戳作为分值，性能指标数据作为元素存储在 Redis 的跳跃表中，方便快速查询某个时间段内的性能数据。

优化与扩展

内存优化

虽然跳跃表本身内存开销相对较小，但在大规模数据场景下，仍然可以通过一些方式进一步优化内存使用。例如，可以采用压缩存储方式，对于跨度较大的指针，可以使用更紧凑的表示方式来减少内存占用。

另外，在确定节点层数时，可以根据实际数据量和分布情况，调整随机化算法，避免层数过高导致过多的内存浪费。

性能优化

为了进一步提高跳跃表在搜索场景中的性能，可以考虑使用多线程或分布式架构。在多线程环境下，对跳跃表的查询操作可以并行化，提高整体的查询效率。在分布式场景中，可以将跳跃表数据分布在多个节点上，通过分布式算法实现数据的快速定位和查询。

同时，对于频繁查询的热点数据，可以采用缓存机制，将查询结果缓存起来，减少对跳跃表的直接查询次数。

功能扩展

在实际应用中，可以对跳跃表进行功能扩展。例如，增加对节点的权重支持，使得在范围查询时可以根据权重进行筛选。还可以扩展跳跃表的结构，支持多维数据的存储和查询，以满足更复杂的搜索需求。

总之，Redis 跳跃表在搜索场景中具有诸多优势，其快速定位、范围查询高效、动态插入与删除不影响查询效率、内存友好、易于实现与维护等特点，使其成为一种非常实用的数据结构。通过与其他数据结构的对比，我们可以更清楚地看到跳跃表在不同场景下的适用性。在 Redis 的实际应用场景中，跳跃表发挥了重要作用，并且通过优化与扩展，可以进一步提升其性能和功能，满足不断变化的业务需求。