Orien Daily
Redis 跳表：一个被低估的数据结构是怎么变成排序集合心脏的
很多人提到跳表，第一反应是"随机化的平衡树替代品"，然后就不再深想了。但如果你读 Redis 的 t_zset.c，会发现跳表在那里的用法远比教科书上的演示精巧得多。
先说跳表本身的直觉。普通链表查找是 O(n)，这没人想用。跳表的核心操作是"往上搭快车道"——每个节点以 50% 概率决定是否出现在上一层，这样第 k 层的节点数大约是第 k-1 层的一半，形成一种概率性的"二分查找"结构。查找时从最高层往右走，走不动就往下跳一层，平均 O(log n)。这个概率构造意味着不需要像红黑树那样做旋转维护，插入删除简单得多。
但 Redis 没有简单照搬 Pugh 的原始论文。如果你看 zslInsert 的源码，会发现它在插入时维护了一个 rank 数组——记录每一层从起点到插入位置跳了多少步。这不是跳表标准操作，而是 Redis 自己加的。目的很明确：ZRANK 命令需要 O(log n) 地返回元素排名，而不是遍历计数。这个 rank 信息在节点删除时也要更新，维护成本不高，但功能价值极大。这就是读源码比读论文多出来的东西——工程场景会倒逼数据结构变形。
再比如，Redis 的跳表每个节点存了分值（score）和成员对象（obj），但比较排序的优先级是先 score 后 obj 指针地址。为什么要用指针地址而不是字符串字典序？因为指针比较是 O(1)，而字符串比较可能很长。在内存数据库的热路径上，这种选择不是微优化，是设计决策。
还有个容易忽略的细节：跳表的最大层数 Redis 设成了 32，而不是理论上足够的 ceil(log₂(n))。因为 2^32 已经远超任何合理的集合大小，留余量比动态计算层数更划算。这种"够用就行"的常数选择贯穿整个 Redis 源码。
CS
