企业官网建设流程全解析

ZSet 要同时满足两件事：按 score 排序取范围，和按 member 查 score。

单靠一种结构做不到两件事都快。要按 score 排序，得用有序结构；要按 member O(1) 查，得用哈希表。Redis 没有硬凑成一种，而是两个都用：一个跳表负责排序和范围，一个dict负责 member 到 score 的映射。

元素少的时候还有第三种形态，一个 listpack 全搞定。所以 ZSet 也有两种编码，listpack和skiplist。

跳表

跳表（skip list）是一摞链表叠起来。最底层是一条完整的有序链表，往上一层是下一层的抽样，每层节点数减半，最上面几层只剩几个节点：

查找从最高层开始往右走。下一个节点的值比目标大（或者到 NULL 了），就下降一层继续往右；比目标小就继续往右走。拿上面这个表找 5 走一遍：

L3: head 的 forward 是 7，7 > 5，下降 L2: head 的 forward 是 4，4 < 5，走到 4 4 的 forward 是 7，7 > 5，下降 L1: 从 4 往右，forward 是 5，命中

这个例子的节点太少，看不出快在哪。节点一多差别就出来了：最高层一步能跨过一大片节点，每下降一层把范围缩小一截，期望查找次数是 O(log n)，和二分差不多。

层高是随机的

跳表每一层的节点是随机抽出来的。新插一个节点时，它有几层是随机决定的：先定 1 层，然后每次有 1/4 的概率再加一层，加到 32 层封顶。

#defineZSKIPLIST_MAXLEVEL32// 最大层数#defineZSKIPLIST_P0.25// 升层的概率

P = 0.25表示每升一层的概率是四分之一，平均下来的层数是1 / (1 - 0.25) = 1.33，也就是每个节点平均带 1.33 个前进指针，内存开销不算大。

为什么要随机，不搞成严格二分？因为严格二分需要维持结构平衡，插入删除就得重新调整。随机层高让跳表在概率意义上保持平衡，插入删除只要改几个指针，不用做任何"重新平衡"的动作。这是跳表比平衡树简单的地方。

节点的构成

typedefstructzskiplistNode{sds ele;// member，就是 ZADD 里的成员doublescore;// 分值structzskiplistNode*backward;// 后退指针，只有一层structzskiplistLevel{structzskiplistNode*forward;// 每一层的前进指针unsignedlongspan;// 到下一个节点跨过了多少个底层节点}level[];}zskiplistNode;

level是柔性数组，长度就是随机出来的层数。每一层除了forward指针，还带一个span。

span是这一层从当前节点走到下一个节点，沿途跨过了多少个最底层的节点。有了它在找路的时候顺手累加，就能算出当前节点排第几。

ZRANK就是靠span做到的。查一个 member 的排名时，沿着跳表往下走，每往右走一步就把那个节点的span加到计数里，走到底就得到了排名，全程 O(log n)，不用遍历整个集合。

span是为了让跳表除了能按分值找元素，还能回答"排第几"。没有它，ZRANK就只能从表头一个一个数过去，变成 O(n)。

哈希表配合跳表

跳表按 score 排序，但给定一个 member 去跳表里找它的 score，得从头顺着跳，ZSCORE会变成 O(log n)。所以 ZSet 同时挂了一个dict：

typedefstructzset{dict*dict;// member → score，O(1) 查zskiplist*zsl;// 按 score 排序}zset;

两个结构里的 member 是同一份sds，通过指针共享，不复制内容，只多花一个指针的存储。

不同的命令走不同的结构：

写入类的命令要同时维护两个结构：ZADD一个新 member，得往dict里加一条映射，同时往跳表里按 score 位置插一个节点；ZREM要两边都删。所以这些是 O(log n)，跳表那一侧是瓶颈。

这里有个细节，range 命令拿到的元素顺序是跳表的顺序，但返回的真实数据（member）是跟dict共享的那份，两边不会对不上。

listpack 编码

元素少的时候，ZSet 不用跳表，直接用一个 listpack：

127.0.0.1:6379>ZADD rank90tom85jerry(integer)2127.0.0.1:6379>OBJECT ENCODING rank"listpack"

listpack 里元素按 score 从小到大排好，member 和它对应的 score 相邻存，大概长这样：

[ tom | 90 | jerry | 85 ]

小集合上用 listpack 的理由和别的类型一样：元素就几个，从头线性扫一遍也不慢，还省掉了跳表每个节点的指针、span、dict那一堆开销。

切换条件是默认的老两组数：

元素数 <= zset-max-listpack-entries( 默认 128 ) 且 每个 member <= zset-max-listpack-value( 默认 64 字节 ) → listpack 否则 → skiplist

注意listpack和skiplist之间是互斥的二选一，不像 Hash 那样hashtable底下还藏着一个dict——ZSet 的skiplist编码本身就包含了跳表加dict两个结构。转换同样是单向的，一旦成了skiplist就不会退回 listpack。

和平衡树的取舍

"为什么不用平衡树（红黑树、AVL）"是常见的问题。按能力对比，两种结构其实打平：

功能上跳表没有比平衡树强，性能上也都是 O(log n)。Redis 选跳表，理由是实现简单。

平衡树的插入删除要维护平衡，红黑树有一整套旋转和变色的规则，代码长，边界情况多，出了问题不好查。跳表的插入删除就是顺着找路改几个指针，层高随机生成，不用任何重新平衡的逻辑，代码短得多。antirez 在实现 ZSet 的时候明确说过，跳表实现起来简单，而且做范围查询（ZRANGEBYSCORE这类）比平衡树更直接。

还有一个次要的优势是范围查询的缓存局部性。跳表最底层是一条链表，按顺序遍历就是顺着forward走；平衡树做一个范围查询要在树上中序遍历，跳来跳去。不过这个理由在 Redis 里不占主要位置。

内存上跳表不占便宜。每个节点平均 1.33 个前进指针，加上span，比平衡树每个节点两个子指针的开销还大一点。所以内存不是选它的原因，简单才是。

排行榜

ZSet 最经典的用法就是排行榜，因为 score 排序和 member 去重它天然都有。

# 三个玩家，分数 90 / 85 / 95ZADD rank90tom85jerry95spike# 取分数最高的 10 个，带分数，从高到低ZREVRANGE rank09WITHSCORES# spike 95# tom 90# jerry 85# 查某个人的排名（从 0 开始）ZREVRANK rank tom# 1# 给某人加分ZINCRBY rank5tom# 95# 取分数在 90 到 100 之间的ZRANGEBYSCORE rank90100

ZREVRANGE是按 score 从大到小，ZRANGE是从小到大，排行榜一般用前者。分页就是改下标，第二页ZREVRANGE rank 10 19。

分数相同时的排序规则要留意。ZSet 在 score 相等时按 member 的字典序排，不是按写入顺序。如果排行榜需要"同分先到先得"，光靠 score 不够，得把时间戳编进 score 里，比如score = 分数 * 10^10 - 时间戳，用低位的精度存先后。

延时队列也是同一个套路，把 score 当成"到期时间戳"：

ZADD delay1735689600order:123# 取出所有到期的任务ZRANGEBYSCORE delay01735689600LIMIT01

LIMIT 0 1只取一个，取出来处理掉再ZREM。跳表和dict一起撑着这个结构，所以"按时间找"和"按任务 ID 删"都快。

ZSet 也被 GEO 借去用了，GEOADD出来的 key，TYPE是zset，底层就是跳表，score 是经纬度编码成的一个整数，见 《签到、UV、附近的人》。