Redis的zset在底层同时使用了哈希表和跳跃表，其中跳跃表（skiplist）专门负责按分值排序以及范围查询。跳跃表是一种概率型数据结构，它用多层有序链表模拟平衡树的能力，却避免了旋转操作。理解它的实现，对掌握Redis有序集合的性能特征非常关键。
跳跃表节点与整体结构
在Redis源码中，跳跃表节点由zskiplistNode表示，每个节点包含分值（score）、成员对象（ele）、后退指针（backward）以及层数组（level）。层数组的每一项是一个前向指针加跨度（span），跨度记录了两个节点之间的节点数量，用于计算排名。节点层数是在插入时随机生成的，最大允许的层数为32，这足以支撑非常大规模的数据而不出现明显性能退化。
整个跳跃表由zskiplist结构管理，它保存头节点、尾节点、当前最大层数以及节点总数。头节点是一个特殊的辅助节点，拥有32个层但不存储实际数据，它的作用是统一各层链表的起点。由于每层都是有序链表，高层链表节点稀疏、低层链表节点密集，查找时从最高层开始向下层收缩，大幅减少了比较次数。
和平衡二叉树的节点结构相比，跳跃表节点不需要颜色标记或父子指针，内存布局更扁平。虽然平均每个节点会多出几倍指针，但在Redis这种以内存换性能的场景中，简单的指针数组比复杂的树平衡逻辑更容易维护和调试。下面的代码展示了节点的简化定义：
typedef struct zskiplistNode {
double score;
robj *ele;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[32];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
随机层数与插入流程
跳跃表最核心的设计是插入时的随机层数算法。Redis使用zslRandomLevel函数，以0.25的概率让节点晋升到更高一层，直到达到最大层数或随机停止。这种幂次概率保证了平均每个节点大约包含1.33层，整体结构在统计意义上趋于平衡。与红黑树每次插入后必须做旋转和变色不同，跳跃表插入仅涉及局部指针修改，不会触发全局结构调整。
具体插入过程首先要在各层找到新节点应有的前驱节点，并记录在更新数组里。随后生成随机层数，如果新层数大于当前跳跃表的最大层数，就把超出的层的前驱统一指向头节点。接着分配节点并逐层串入链表，同时更新各层的跨度值。由于跨度影响着排名计算，插入时要把受影响前驱节点的span加上新节点带来的偏移，并把新节点自身的span设为后续节点的原span减一。
下面是一段简化后的插入逻辑示例，用于说明层数随机与链表串联的关系。注意实际源码还要处理分值相同但成员不同的情况，以保证字典序唯一。
int zslRandomLevel(void) {
int level = 1;
while ((random() & 0xFFFF) < (0xFFFF * 0.25))
level++;
return (level < 32) ? level : 32;
}
void zslInsert(zskiplist *zsl, double score, robj *ele) {
zskiplistNode *update[32], *x;
int i, level;
x = zsl->header;
for (i = zsl->level - 1; i >= 0; i--) {
while (x->level[i].forward &&
x->level[i].forward->score < score)
x = x->level[i].forward;
update[i] = x;
}
level = zslRandomLevel();
if (level > zsl->level) {
for (i = zsl->level; i < level; i++)
update[i] = zsl->header;
zsl->level = level;
}
x = createNode(level, score, ele);
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
}
}
查找删除与范围查询的取舍
查找操作从最高层出发，沿着前向指针向右比较分值，当右侧节点分值更大或为空时就下降一层，直到最底层找到目标或确认不存在。平均时间复杂度为O(log n)，最坏情况为O(n)，但随机层数机制让最坏情况出现概率极低。删除节点时同样先定位各层前驱，再逐层脱链并修复跨度，最后若最高层变空则降低跳跃表层级。
范围查询是跳跃表相比平衡树最直观的优势。执行ZRANGE类命令时，先按分值或排名定位起始节点，然后沿最底层前向指针线性遍历即可，无需像树结构那样做中序遍历栈操作。对于需要返回一段连续排名的场景，跳跃表只需常数级的定位加线性扫描，实现简单且缓存命中率高。
当然跳跃表也有缺点，主要是额外指针带来的内存开销，以及随机性导致理论上性能不如严格平衡树稳定。但Redis的有序集合还用哈希表维护了成员到分值的映射，跳跃表只解决排序和区间问题，因此这种取舍在工程上非常合理。下面的表格对比了两者在典型操作上的差异：
| 操作 | 跳跃表 | 红黑树 |
|---|---|---|
| 插入 | 局部指针修改，无旋转 | 旋转加变色 |
| 范围查询 | 底层线性遍历 | 中序遍历 |
| 排名计算 | 利用span直接累加 | 需维护子树大小 |
| 实现复杂度 | 低 | 高 |
综合来看，Redis选择跳跃表不是因为它在理论上更优，而是它在保持对数级性能的同时极大降低了代码复杂度和维护成本，这也符合Redis一贯追求简洁高效的工程哲学。