跳表面试题总结：多级索引、范围查询与 Redis ZSet

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