Redis Sorted Set 跳表的实现示例_Redis

前言

在 redis 中，sorted set（有序集合） 是一种非常重要且高效的数据结构。与普通的 set 不同，sorted set 为每个元素关联了一个分数（score），并按照这个分数进行排序。在许多需要快速插入、删除、查找和范围查询的场景下，sorted set 提供了理想的解决方案。而其底层的核心数据结构之一便是 跳表（skip list），这种结构有效地支持了有序集合的高效操作。

本文将深入剖析跳表的实现原理，并通过 redis 中 sorted set 的具体案例进行分析，帮助你更好地理解 redis sorted set 的强大性能来源。

什么是跳表？

跳表（skip list）是一种 平衡数据结构，它通过多级索引加快了查找操作的效率，最早由 william pugh 在 1990 年提出。它的时间复杂度与平衡二叉树类似，均为 o(log n)，但跳表的实现相对简单，操作灵活。

跳表的基本思想是通过在链表基础上建立多层索引，提升数据的查找效率。每一层都是下一层的 “缩略图”，这样在查找时，能通过跳跃方式快速逼近目标元素。

跳表的结构

跳表的结构类似于多层链表：

第一层 是完整的有序链表，所有数据都在这一层。
第二层及以上 则是对部分数据的抽象，使得每一层的数据量逐步减少，但依然保持有序。

每个元素会以一定概率决定是否提升到上层。因此，跳表有多条指向不同节点的指针，最低层类似普通链表，而上层指针可以跨越多个节点。

跳表的时间复杂度

在最优情况下，跳表通过减少层数并允许跳跃式查找，平均查找、插入和删除的时间复杂度都为 o(log n)，空间复杂度为 o(n)。这种特性使得跳表非常适合用于实现有序集合，尤其是像 redis 这样要求高效范围查询的场景。

redis 中的 sorted set

redis 的 sorted set 是通过两个核心数据结构实现的：

跳表（skip list）：用于按照分数（score）排序元素，支持按顺序查找、范围查找等操作。
哈希表：用于根据元素的唯一标识符（member）快速定位元素，避免重复插入。

redis 通过这两种数据结构的结合，实现了有序集合的高效性和灵活性。

sorted set 的存储结构

redis sorted set 的存储结构是 zset，它内部由一个 dict 和一个 zskiplist 组成：

dict：保存成员和对应分数的映射关系，确保成员唯一性，插入和删除操作时间复杂度为 o(1)。
zskiplist：用于按分数排序的跳表，支持按分数范围查找、范围删除等操作，时间复杂度为 o(log n)。

这种设计确保了插入、删除和范围查询等操作在高效性和稳定性上的平衡。

跳表在 redis sorted set 中的实现

1. 跳表节点（zskiplistnode）

在 redis 中，每个跳表节点不仅包含元素的分数和成员信息，还包含多个指向其他节点的指针，用于支持多层索引的实现。redis 中 zskiplistnode 的定义如下：

typedef struct zskiplistnode {
    sds ele;  // 成员（member）
    double score;  // 分数（score）
    struct zskiplistnode *backward;  // 后退指针，用于反向遍历
    struct zskiplistlevel {
        struct zskiplistnode *forward;  // 前进指针，指向下一节点
        unsigned int span;  // 跨度，用于快速定位节点
    } level[];  // 每个节点的多层指针
} zskiplistnode;

ele：保存成员数据。
score：保存对应成员的分数。
backward：用于反向遍历，支持双向链表的功能。
level：是一个数组，每个元素对应一层，保存指向下一个节点的指针。

2. 跳表结构（zskiplist）

redis 中的 zskiplist 结构表示整个跳表，它由头节点、尾节点、最大层数和节点总数组成：

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

3. 插入操作

插入新元素时，跳表通过从高层向低层逐层查找插入位置，并将新节点插入到相应层级的链表中。每插入一个新节点时，会随机决定它提升到哪一层，这种随机性保证了跳表的平衡性。

redis 使用的随机层数生成算法如下：

int zslrandomlevel(void) {
    int level = 1;
    while ((random() & 0xffff) < (0.25 * 0xffff)) {
        level += 1;
    }
    return (level < zskiplist_maxlevel) ? level : zskiplist_maxlevel;
}

zslrandomlevel 函数根据概率随机生成节点的层数，使得跳表在理论上能够保持 log 级别的复杂度。

插入示例：

假设我们向 redis 中的 sorted set 插入一个元素：

zadd myzset 1 "apple"

redis 首先通过随机算法为该元素分配一个层数。
然后，从最高层逐步查找合适的插入点，依次更新前后节点的指针，完成插入。

4. 查找操作

跳表的查找操作通过从上到下逐层遍历实现。每一层跳过若干节点进行快速查找，直到在最低层找到目标元素。由于跳表的层级设计，查找操作的时间复杂度为 o(log n)。

查找示例：

例如，我们要查询分数为 3 的元素：

zrange myzset 3 3

跳表将从最高层开始，跳过一部分节点，快速找到分数为 3 的节点。

5. 删除操作

删除元素时，跳表会先找到目标元素所在的位置，然后从每一层中移除节点。为了保持数据结构的平衡，删除时会调整各层级指针，并在必要时降低跳表的层数。

删除示例：

假设我们删除 myzset 中分数为 2 的元素：

zrem myzset "banana"

跳表会从头节点开始，逐层找到 banana 所在的位置，并移除该元素，同时更新前后节点的指针关系。

redis 跳表的优势与局限

优势

高效的范围查询：跳表通过分层索引，可以快速完成范围查找、排名等操作。
插入、删除操作高效：跳表保持了 o(log n) 的插入和删除复杂度，适合大规模数据的动态增删。
实现简单：相比平衡树，跳表结构相对简单，更易于实现和维护。

局限

内存占用：跳表需要为每个节点维护多层指针，在内存占用上相对链表较大。
随机性导致的性能波动：由于跳表使用随机算法决定节点层数，可能导致性能出现波动，虽然这种概率极低。

总结

redis 中的跳表作为 sorted set 的核心数据结构，提供了高效的排序、插入、删除以及范围查找等功能。通过跳表的多层索引机制，redis 在处理有序集合时能够维持 o(log n) 的时间复杂度，同时结合哈希表确保了成员的唯一性和快速访问。

跳表的设计简单却强大，是 redis 高性能的关键之一。在理解了其实现原理后，我们可以更好地运用 redis 的 sorted set，优化高并发环境中的数据查询与操作。

如果你在构建需要排序、范围查询或动态调整的数据系统时，redis 的 sorted set 和跳表的组合无疑是一个值得选择的高效解决方案。

到此这篇关于redis sorted set 跳表的实现示例的文章就介绍到这了,更多相关redis sorted set 跳表内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！

Redis Sorted Set 跳表的实现示例

2024年11月25日 • Redis •我要评论

前言