跳表可以理解为“带多级索引的有序链表”。普通有序链表查询需要从头扫到尾，时间复杂度是 O(n)；跳表在链表上方加了多层索引，查询时可以从高层快速跳过一批节点，再逐层下降。
O(n)Redis 的有序集合 ZSet 底层就使用了跳表和哈希表的组合，所以跳表在后端面试里经常和 Redis 一起出现。
文章内容概览：
什么是跳表？
跳表为什么能把查询从 O(n) 降到平均 O(logn)？
O(n)O(logn)跳表如何查找、插入和删除？
跳表和红黑树应该怎么对比？
Redis ZSet 为什么会用到跳表？
什么是跳表？
跳表（Skip List）是一种基于有序链表的数据结构。它的底层仍然是一条完整的有序链表，所有元素都会出现在最底层；在底层链表之上，跳表再建立若干层更稀疏的索引。
可以把它想成一本书的目录：
最底层链表像正文页码，信息最完整，但从第一页翻到最后一页很慢。
上层索引像目录，信息更少，但能快速跳到接近目标的位置。
查询时先从最高层索引往右跳，跳不动了就下降一层，直到最底层。
跳表和普通链表最大的区别就在这里：普通链表每次只能向后走一步；跳表可以在高层索引中一次跳过多个节点。
跳表的节点长什么样？
普通链表节点通常只有一个 next 指针，而跳表节点会有多个前进指针。一个节点如果出现在第 3 层，就意味着它在第 0、1、2 层都有对应指针。
next抽象来看，跳表节点可以理解成这样：
class SkipListNode {
int value;
SkipListNode[] forward;
}class SkipListNode {
int value;
SkipListNode[] forward;
}这里的 forward[i] 表示当前节点在第 i 层指向的下一个节点。真实工程实现里还可能保存 score、member、backward 指针、span 等信息，用来支持排名、反向遍历和范围查询。
forward[i]i层数是怎么来的？
跳表并不通过旋转、变色来维持平衡，它依赖随机层数。
插入一个新节点时，通常会用随机函数决定它能升到多少层。可以把这个过程想成抛硬币：节点一定会出现在最底层；如果第一次抛到正面，就升一层；再抛到正面，再升一层；直到抛到反面或达到最大层数。
这样做的结果是：越高层的节点越少，越低层的节点越密。理想情况下，第 1 层大约保留一半节点，第 2 层再保留一半，第 3 层继续减少。虽然不是严格平衡，但从概率上看，高度会维持在 O(logn) 级别。
O(logn)这也是跳表名字里“跳”的来源：高层索引允许查询过程跳过一段又一段元素。
面试考察重点
能说清跳表为什么比普通链表查询快。
能描述查找、插入、删除的大致过程。
能说明跳表平均查询、插入、删除是 O(logn)。
O(logn)能解释跳表和红黑树的取舍。
能关联 Redis ZSet 的范围查询场景。
跳表怎么查找？
查找时从最高层索引开始：
如果当前节点的下一个节点小于目标值，就向右走。
如果下一个节点大于目标值或为空，就下降一层。
到最底层后继续查找目标节点。
这个过程有点像在有序数组里二分，但跳表底层仍然是链表结构。
更准确地说，跳表每一层都是有序链表。查询时始终遵循一个原则：能往右走就往右走，不能往右走就往下走。
假设要查找 26：
26从最高层头节点开始。
如果右侧节点值小于 26，说明目标还在右边，可以继续右移。
26如果右侧节点值大于 26，说明再往右就越过目标了，于是下降一层。
26重复这个过程，最后在最底层确认目标是否存在。
如果目标不存在，跳表也能找到它应该插入的位置：最底层中小于目标值的最后一个节点，就是插入位置的前驱节点。
插入和删除
插入一个节点时，需要先找到每一层中它的前驱节点，然后把新节点接进去。新节点能提升到多少层，通常由随机函数决定。
删除节点时，也要找到各层前驱节点，再把指针绕过目标节点。
跳表不靠旋转维持平衡，而是靠随机层数让索引高度保持在合理范围内。这也是它实现起来比红黑树更容易的地方。
实际写插入代码时，经常会维护一个 update 数组：update[i] 表示第 i 层中新节点应该插入在哪个节点后面。查找插入位置的过程中顺手把这些前驱节点记录下来，拿到随机层数后，就能逐层修改指针。
updateupdate[i]i删除也是类似思路：先找到每一层的前驱节点，如果这一层的下一个节点正好是目标节点，就把前驱节点的 forward 指向目标节点的下一个节点。
forward因此，跳表的插入和删除并不是只改底层链表，还要同步维护目标节点出现过的那些索引层。
复杂度
操作平均复杂度说明查找O(logn)通过多级索引跳过节点插入O(logn)查找位置后更新多层指针删除O(logn)查找前驱后断开指针范围查询O(logn + k)先定位起点，再顺序返回 k 个元素
操作平均复杂度说明
操作
平均复杂度
说明
查找O(logn)通过多级索引跳过节点
查找
O(logn)
O(logn)通过多级索引跳过节点
插入O(logn)查找位置后更新多层指针
插入
O(logn)
O(logn)查找位置后更新多层指针
删除O(logn)查找前驱后断开指针
删除
O(logn)
O(logn)查找前驱后断开指针
范围查询O(logn + k)先定位起点，再顺序返回 k 个元素
范围查询
O(logn + k)
O(logn + k)先定位起点，再顺序返回 k 个元素
空间复杂度是 O(n) 级别，但会比普通链表多一些索引指针。
O(n)这里的 O(logn) 是平均意义上的复杂度，依赖随机层数带来的概率平衡。跳表不像红黑树那样提供严格的最坏情况平衡约束，但在随机函数正常、参数设置合理的情况下，性能通常很稳定。
O(logn)范围查询是跳表很舒服的场景：先用 O(logn) 定位到范围起点，再沿着最底层链表顺序向后遍历 k 个结果即可。
O(logn)k跳表和红黑树怎么选？
对比点跳表红黑树平衡方式随机层数旋转和变色实现难度相对更直接插入删除修复更复杂范围查询顺着底层链表扫，很方便中序遍历也可以，但实现更绕最坏复杂度依赖随机性有严格平衡约束工程代表Redis ZSetJava TreeMap、HashMap 树化
对比点跳表红黑树
对比点
跳表
红黑树
平衡方式随机层数旋转和变色
平衡方式
随机层数
旋转和变色
实现难度相对更直接插入删除修复更复杂
实现难度
相对更直接
插入删除修复更复杂
范围查询顺着底层链表扫，很方便中序遍历也可以，但实现更绕
范围查询
顺着底层链表扫，很方便
中序遍历也可以，但实现更绕
最坏复杂度依赖随机性有严格平衡约束
最坏复杂度
依赖随机性
有严格平衡约束
工程代表Redis ZSetJava TreeMap、HashMap 树化
工程代表
Redis ZSet
Java TreeMap、HashMap 树化
TreeMapHashMapRedis ZSet 为什么用跳表？
ZSet 需要支持：
按 member 快速查 score。
按 score 排序。
按 score 范围查询。
获取排名。
哈希表适合按 member 查 score，跳表适合按 score 排序和范围查询。两者组合后，ZSet 能同时支持快速查找和有序遍历。
更具体一点：
通过哈希表，可以根据 member 直接找到对应 score。
通过跳表，可以按 score 从小到大维护顺序。
做 ZRANGE、ZRANGEBYSCORE 这类范围查询时，跳表可以先定位起点，再沿链表连续返回结果。
ZRANGEZRANGEBYSCORE如果跳表节点维护 span 信息，还可以支持排名相关操作。
需要注意，Redis 会根据数据规模和配置使用不同的内部编码来节省内存。面试里说“ZSet 使用哈希表 + 跳表”通常是在讨论它面向较大有序集合时的核心结构。
易错点
跳表不是数组，也不是二叉树，它的底层是链表。
跳表平均复杂度是 O(logn)，不是靠严格平衡保证。
O(logn)范围查询是跳表的强项，先定位起点，再沿底层链表遍历。
Redis ZSet 不是只用跳表，还配合了哈希表。
高频问题自测
跳表为什么查询快？
跳表和红黑树有什么区别？
Redis ZSet 为什么不用红黑树？
跳表的层数怎么决定？
跳表范围查询复杂度是多少？
参考资料
Skip Lists: A Probabilistic Alternative to Balanced Trees
Skip Lists: A Probabilistic Alternative to Balanced Trees
William Pugh：A Skip List Cookbook
William Pugh：A Skip List Cookbook
Redis Docs：Sorted Sets
Redis 源码：t_zset.c
写在最后
如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。
JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。
如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。