跳表(Skip List)是一种在有序链表上叠加多层索引的有序数据结构,它通过随机方式把查找从 O(n) 降到期望的 O(log n)。
把“站站都停”改成“只停大站”
想象一条地铁线,站站都停的慢车走完全程要很久。跳表的思路是多开几趟快车:大站车只停几个大站,区间车停得多一些,最底层则是站站都停的慢车。
结构上正是如此。最底层是一条包含全部元素的有序链表;在它之上,每个节点以固定概率(通常 1/2)被选入上一层,形成一条更稀疏的索引链;再往上同理,直到某一层只剩很少几个节点。同一份数据被组织成若干层链表,越往上越稀疏、跨的步子越大。
查找时从最高层出发:看下一个节点,如果它的值还没超过目标,就沿这一层往前走;一旦超过,就“下楼梯”到下一层接着走。每下降一层,候选范围大致缩小一半,整体只需 O(log n) 步。插入时先找到位置放进底层,然后一直抛硬币决定要不要继续往上建索引。这也是它不需要旋转、不需要重新平衡的原因。
和平衡树的分工
| 维度 | 跳表 | 平衡树(如红黑树) |
|---|---|---|
| 结构 | 多层链表 | 树,靠旋转维持平衡 |
| 查找与增删 | 期望 O(log n) | 最坏 O(log n) |
| 实现难度 | 核心逻辑很短 | 旋转、变色分支多 |
| 范围查询 | 底层就是有序链表,顺着走 | 需中序遍历 |
| 修改影响面 | 只动局部指针 | 旋转可能牵动较大范围 |
Redis 为什么选它
Redis 的有序集合(Sorted Set,简称 zset)要同时支持:按分数排序、按分数区间取元素、查某个元素的排名。跳表在底层维护一条有序链表,范围查询顺着链表走就行,天然合适;每个索引节点再记录一个“跨度(span)”,排名查询边走边累加即可。
红黑树(Red-Black Tree)在最坏情况下的保证更严格,但插入删除要处理旋转和变色,代码分支多、容易出 bug;范围查询得靠中序遍历,不如链表直观;一次旋转牵动的指针范围也更大。
对一个把“简单可维护”看得很重的项目来说,跳表的期望性能已经够用,实现却短得多。工程上常被提起的说法是:它用一点点概率上的不确定性,换来了代码结构上的简单。
同样的取舍也出现在别处:LevelDB、RocksDB 的内存表(MemTable)同样用跳表维护有序写入,写路径简单,并发时只需局部加锁。
对你的意义
如果在做排行榜、热搜、延时队列、区间查询这类“既要排序又要范围”的功能,跳表值得放进工具箱。更值得带走的是一个工程直觉:不是每个问题都需要理论最优解,一个可读、可调试、够快的方案,往往比一个漂亮但难维护的结构更划算。
