上一篇讲到 ZSet 的 skiplist 编码其实是 dict + zskiplist 两个结构一起工作:dict 负责"这个成员分数是多少"的 O(1) 查找,zskiplist 负责"按分数排序、按排名区间查询"。这一篇专门拆开 zskiplist 本身——它靠什么在不需要整体重排的情况下,把插入、删除、按名次查找都做到 O(log N)。
本机真实运行的 Redis 8.10.1 上建了一个 100 万成员的真实 ZSet,ZRANK 的服务端耗时在成员数从 1000 涨到 100 万的过程中几乎没有变化。
一个有序数据结构,插入、删除、按名次查找,理论上都能用平衡树做到 O(log N)。Redis 选了另一条路。
普通有序链表插入/删除只需改几个指针,但要找"第 500000 名是谁"或者"某个成员排第几",只能从头一个个数过去。
红黑树、AVL 树能做到 O(log N),但插入删除后要维护平衡(旋转、变色),实现复杂,范围查询也不如链表结构直观。
本质还是链表,但每个节点随机拥有额外的"高层快捷指针"。查找时先在高层大步跳,跳过头再逐层下沉,期望复杂度 O(log N),不需要任何旋转或再平衡。
跳表由 William Pugh 在论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中提出。Redis 用平衡树的替代方案换来的是实现简单(没有旋转、没有再平衡的边界情况)、范围查询友好(区间本身就是链表上的一段),用统计概率换掉了最坏情况的严格保证——这也是"probabilistic"这个词的含义:单次操作有极小概率退化,但期望情况稳定在 O(log N)。
课本里的跳表节点通常是"值 + 每层一个指针"这么简单。8.10.1 版本的真实实现做了一次内存布局优化,和大多数教程描述的经典版本不一样。
src/server.h · redis @ 8.10.1, L1791 /* Node info placed in level[0].span since it's unused at level 0 */ typedef struct zskiplistNodeInfo { uint16_t sdsoffset; /* 成员字符串相对节点起始地址的偏移 */ uint8_t levels; /* 这个节点有几层(1-32) */ uint8_t reserved; } zskiplistNodeInfo; typedef struct zskiplistNode { double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; /* level 0 时被复用来存 zskiplistNodeInfo */ } level[]; /* sds 成员字符串直接紧跟在 level[] 数组后面,同一块内存里 */ } zskiplistNode;
两个不那么"教科书"的真实细节:
src/t_zset.c · redis @ 8.10.1, L169 static zskiplistNode *zslCreateNode(zskiplist *zsl, int level, double score, sds ele) { size_t node_size = sizeof(zskiplistNode) + level * sizeof(struct zskiplistLevel); size_t sds_buf_size = sds_hdr_len + ele_len + 1; size_t total_size = node_size + sds_buf_size; zskiplistNode *zn = zmalloc_usable(total_size, &usable); // 一次分配搞定 ... char *sds_buf = (char*)zn + node_size; sds embedded_sds = sdsnewplacement(sds_buf, sds_buf_size, sds_type, ele, ele_len); zslSetNodeInfo(zn, level, sds_offset); // 层数、偏移量塞进 level[0].span ... }
每个节点的层数(level 数组长度)在分配时就定死,是个变长数组(struct zskiplistLevel level[])——节点越矮,分配的内存越小,这也是为什么"层数是随机的"这件事在内存层面完全体现在了每个节点的实际大小上。
每个新节点的层数,靠一个"抛硬币"式的循环决定——不是预先算好,是一边抛一边往上加。
src/t_zset.c · redis @ 8.10.1, L254 static int zslRandomLevel(void) { static const int threshold = ZSKIPLIST_P*RAND_MAX; int level = 1; while (random() < threshold) level += 1; return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; }
每个节点起步至少是 1 层。之后每多"抛"中一次(概率 ZSKIPLIST_P = 0.25),层数就 +1,直到抛不中为止,封顶 ZSKIPLIST_MAXLEVEL = 32。结果是层数越高,节点越少——这不是巧合,是几何分布的直接后果:第 k 层存在的概率是 0.25^(k-1)。
用同样规则(seed=123)独立跑了 20000 次抽样,和理论概率逐层核对:
| 层数 | 实测占比 | 理论占比 (0.25^(k-1)×0.75) | 样本数 |
|---|---|---|---|
| 1 | 0.7499 | 0.7500 | 14997 |
| 2 | 0.1855 | 0.1875 | 3711 |
| 3 | 0.0486 | 0.0469 | 972 |
| 4 | 0.0121 | 0.0117 | 242 |
| 5 | 0.0030 | 0.0029 | 60 |
| 6 | 0.0006 | 0.0007 | 13 |
| 7 | 0.0002 | 0.0002 | 4 |
四分之三的节点只有 1 层(和普通链表节点没区别),能长到 5 层以上的节点,两万个里不到一百个。真正撑起"跳过大段元素"的,是这一小撮高层节点。
本机真实运行的 Redis,--pipe 批量插入 100 万条随机分数的 ZADD,确认走的是 skiplist 编码。
直接测 ZRANK 单次往返耗时,会被网络/协议开销(~95us)完全淹没,看不出结构本身的差异。用 pipeline 把 5000 次 ZRANK 打包发送、摊平网络开销,才能看到服务端真实的每次执行成本:
| ZSet 成员数 N | 编码 | ZRANK 服务端耗时(pipeline 摊平后) |
|---|---|---|
| 1,000 | skiplist | 3.764 us/次 |
| 10,000 | skiplist | 3.798 us/次 |
| 100,000 | skiplist | 3.787 us/次 |
| 1,000,000 | skiplist | 3.856 us/次 |
成员数涨了 1000 倍,耗时几乎没变。这不是"没测出差异"的失败实验——这恰恰是 O(log N) 该有的样子:log2(1,000,000) ≈ 20,log2(1,000) ≈ 10,跳表要多跳的层数只多了一倍,而每一跳本身是几十纳秒级别的指针操作,在微秒级的测量精度下根本看不出来。如果 ZRANK 真是从头数到尾的 O(N) 实现,1000 倍的成员数增长会直接体现成千倍的耗时增长——那种差异是不可能被淹没的。
用 8 个 (分数, 成员) 复现一次完整的插入过程——从最高层开始网右走,走不动就下沉一层,一路记录"跳过了多少元素"。
每个节点的层数由和真实 zslRandomLevel() 完全一致的抛硬币算法生成(seed 固定以保证可复现),路径记录、最终排名均由独立的暴力排序交叉验证过,不是手摆的示意图。