跳表Skip list

在有序链表上增加多层稀疏索引。

核心约束: 底层包含全部元素，高层是有序子序列。
适用问题: 有序集合、区间访问和排名索引。
边界与取舍: 多层指针增加内存；期望复杂度依赖层高策略。

常见操作#

n 为节点数，k 为范围结果数；节点层高按独立几何分布选择。

操作	时间复杂度	条件与说明
查找 / 插入 / 删除	期望 $O(\log n)$ ；最坏 $O(n)$	随机层高提供期望界，不能当作平衡树的确定性最坏保证。
范围扫描	期望 $O(\log n+k)$	定位起点后沿最底层输出 k 个节点。
完整有序遍历	$O(n)$	沿最底层链接前进。

时间与空间#

时间复杂度: 查找 / 更新期望 $O(\log n)$
存储空间: 期望 $O(n)$

空间统计各层链接总数；实际实现常限制最大层高。

工程中的应用#

1 个案例 · 附源码

Redis·Sorted Set7.2.0

排行榜为何同时需要跳表和哈希表

Redis 有序集合既要按成员查分数，也要按分数和名次遍历；较大集合通过两种索引服务这些访问方式。

跳表哈希表

附源码片段 · 索引与查找

基础原理参考资料

Open Data Structures · SkiplistSSet随机层高、搜索路径与增删查的期望时间证明。