有序集合 (Sorted Set) 的每个元素叫做 member，member 对应的分数叫做 score，member 之间的顺序由 score 大小确定。

在 Redis 中，按照存储的数据规模，有序集合的实现方式可以分为两种：压缩表和跳表。

ziplist

默认情况下，sorted set 的 member 个数小于 128 时，使用 ziplist 存储数据。

ziplist 将 member 和 score 串行存储在一个双向链表中，即每插入一个元素，就会向链表中插入一个 (member, score) 对。

ziplist 不能二分查找，每次比较移动两个节点。

skiplist

当元素数量或者 member 的长度达到一定规模时，sorted set 将结合 dict 和 skiplist 存储数据：

• 通过 dict 查询 member 对应的 score；
• 通过 skiplist 查询 score 对应的 member。

下面是 skiplist 的结构示意图：

zskiplistNode

有序集合的每个元素保存为一个 跳表节点 (Skiplist Node)，其定义如下：

typedef struct zskiplistNode {
    robj *robj;
    // 当前节点的排序分数
    double score;
    // backward 指向上一个节点
    struct zskiplistNode *backward;
    // level 是一个跳表层结构的数组，每个元素的结构为 zskiplistLevel
    struct zskiplistLevel {
        // 元素的 forward 指向了该层中的下一个节点
        struct zskiplistNode *forward;
        // 该层中上一个节点到当前节点在原始链表中跨越的节点数目
        unsigned int span;
    } level [];
} zskiplistNode;

每个跳表节点由四部分构成：

• 左上方格子存储 member 的 store 值，即 score；
• 左下方格子存储 member 值，即 robj；
• 右下方格子存储上一个跳表节点的地址，即 backward；
• 右上方的一个或者多个格子存储跳表层，即 level。

跳表层储存在一个数组 level 中，每个跳表节点的 level[i] 都指向了另外一个跳表节点。

所有原始的跳表节点构成了 level[0] 层，所以每个节点的 level[0] 构成了有序集合整体。

存在 level[1] 的节点共同组成了第一层 跳跃链表，如上图的 level[1].head -> 78.0 -> 87.5 -> NULL。

存在 level[2] 的节点共同组成了第二层跳表，如 level[2].head -> 78.0 -> NULL。

每个跳表层都拥有一个头结点和尾节点，最高跳表层只有一个有效的原始节点。

zskiplist

跳表的定义如下：

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

一个跳表结构由四部分组成：

• header：左上格子，指向头结点；
• tail：右上格子，指向原始链表最后一个节点；
• length：中间格子，原始链表的长度；
• level：下方格子，有效的跳表层数。

链表层的头结点和尾节点仍然是 zskiplistNode 结构，只是它们不存储任何数据。

上图中的灰色区域的头结点实际上是跳表节点结构的 level 部分，节点结构的其他部分没有数据。

途中的跳表层结构最多可以提供了31个额外的跳表层，第一层始终是原始链表。

此外 skiplist 中还定义了两个常量：

#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25

• ZSKIPLIST_MAXLEVEL 定义了每个跳表节点最多有32个跳表层；
• ZSKIPLIST_P 表示第 $n$ 层的节点在 $n+1$ 层出现的概率。

除了跳表，二叉平衡树 也能用来查询 score 对应的 member，其事件复杂度与跳表一样都是 $\text(\lg)$。但从实现上来讲，平衡树的实现更加复杂，其增删可能会引起对子树较大的调整。

一些问题

• 跳表层怎么构建？
• 怎么查询 score 对应的 member？
• 怎么插入一个节点？
• 怎么删除一个节点？