跳到主内容
快讯直播
AI智模界
AI 词典

跳表:用多层链表给有序集合开快车道

跳表(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)同样用跳表维护有序写入,写路径简单,并发时只需局部加锁。

对你的意义

如果在做排行榜、热搜、延时队列、区间查询这类“既要排序又要范围”的功能,跳表值得放进工具箱。更值得带走的是一个工程直觉:不是每个问题都需要理论最优解,一个可读、可调试、够快的方案,往往比一个漂亮但难维护的结构更划算。

AI 生成本文由 AI 基于公开信息自动生成,仅供参考。