想象你生活在一座棋盘式老城，路面全是单车道，每个路口都有红绿灯。某天政府决定修高架：第一层高架每隔两条街设一个匝道，第二层每隔四条街设一个，第三层每隔八条街设一个……从此老司机去城市另一端时，先上最高层高架一路飞驰，发现快过头了，就下到低一层的快速路继续逼近，最后落到地面街道精确停靠——全程跳过几十个红绿灯。 这就是跳表（Skip List）的核心思想：在一条普通有序链表之上，用多层“索引通道”让查找跳跃式前进，把 O(n) 的逐个比较变成 O(log n) 的快速逼近。Redis 的 Sorted Set（有序集合）正是这项技术的明星应用——游戏排行榜、实时热榜、延迟队列背后都有它的身影。本文将用“城市立体交通网”这个比喻，带你从零看懂跳表的多级索引、掷硬币式的概率平衡，以及 Redis 如何用 skiplist + hash 双结构同时实现“按分数排序”和“按成员查分”。

岗位关联

跳表是理解“以空间换时间”和“概率即平衡”两大工程思想的绝佳入口。掌握它，你不仅能看懂 Redis 核心数据结构的源码，还能在设计高并发有序存储方案时多一把趁手的工具。

目录
  1. 可视化演示
  2. 跳跃查找思想
  3. 多级索引结构
  4. 概率平衡机制
  5. Sorted Set 双结构
  6. 核心操作实现
  7. 性能复杂度分析
  8. 工程应用场景
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示跳表多级稀疏索引结构、从顶层向下的查找过程、概率晋升插入机制及Redis ZSet双结构应用，交互切换深入理解跳表核心原理。

本节配有交互动效（进入视口后自动加载，约 3KB）。

跳表：有序链表上的多级稀疏索引 底层完整有序链表，上层按概率抽取节点形成稀疏索引 最高层节点最少，逐层向下密度递增 查找：从最高层向右走，碰壁则下降一层 多级索引实现O(logN)查找。

跳跃查找思想

周五晚高峰，你开车横穿整座城市。如果只走地面街道，每个路口都可能遇到红灯，十公里路程要停几十次。聪明的做法是先上环城高架——高架入口虽少，但上去之后可以一口气越过七八个地面路口，等快到目的地了再下桥走最后几百米。跳表的灵感与修高架如出一辙：它给普通链表“修高架”。

普通有序链表的查找只能从头节点开始，逐个 next 向后比较，找第 n 个元素平均要比较 n/2 次，时间复杂度为 O(n)，这就是城市地面交通的拥堵。跳表的改进是：额外维护若干层“索引链表”，每一层都比下一层稀疏。查找时从最高层出发，沿着当前层向右走，一旦发现“下一个节点已经超过目标”，就下移到低一层继续——整个过程像高架→快速路→地面街道的逐级下降，跳过了大量冗余比较。

理想情况下，如果第 i 层每两个节点挑一个进入第 i+1 层，那么顶层大约只剩 2 个节点，层数约为 log₂n。层数每增加 1，单次跳跃能跨过的节点数翻倍，这正是查找能从 O(n) 降到 O(log n) 的物理基础：

有了这套“立体路网”，老司机找目标时先走高架远眺，再下快速路逼近，最后落地街道精确停靠，全程不超过 log₂n 次“跳跃+下移”。这正是跳表名字的由来——用多级索引“跳”过冗余节点。

L(n)=log⁡2n\displaystyle L(n) = \log_2 n
这个公式说明了跳表的“理想层高”：n 个元素的链表，约 log₂n 层索引就能让顶层只剩两个哨兵节点。
  1. n底层节点总数：底层链表保存全部 n 个数据元素，是查找的最终归属地。
    n\displaystyle n
  2. log₂二分次数：n 个有序元素，每次折半后剩余规模的对数级表达。
    log⁡2n\displaystyle \log_2 n
  3. L(n)理想层数：让顶层只剩约 2 个节点所需的索引层数，也是查找路径的“高度”。
    L(n)=log⁡2n\displaystyle L(n) = \log_2 n

多级索引结构

高架桥不是每栋楼都有匝道。地面街道（L0）每个小区都有出入口；一级快速路（L1）每隔一个街区设入口；城市环线（L2）每隔四个街区才有一个入口；跨城高速（L3）只在几个大枢纽接驳。层数越高，入口越稀疏，但单次跨越的距离越远。

跳表的多级索引完全复刻了这套结构。L0 是包含全部 n 个节点的普通有序链表；L1 从 L0 中约每两个取一个节点；L2 从 L1 中约每两个取一个……每一层节点数约为下一层的一半。工程实现中，每个节点内部用一个 forward 指针数组保存它在各层的后继节点，相当于每个路口记录了通往各层高架的入口位置。

在第 k 层出现的节点，需要连续通过 k 次“晋升”。如果晋升概率 p = 1/2，那么一个节点正好出现在第 k 层的概率为：

工程实现中，层数不需要预先规划。每个新节点根据自己的“匝道数量”（随机层数）就地扩建 forward 指针数组，各层指针互不干扰，形成一座自然生长的立体交通网。

P(Lk)=(12)k\displaystyle P(L_k) = \left(\frac{1}{2}\right)^k
这个概率公式说明第 k 层的期望节点数约为 n × (1/2)^k，层数越高节点越稀有，与“匝道越少越高效”的直觉完全一致。
  1. L_k第 k 层索引：k=0 是底层完整链表，k 越大越接近顶层，节点越稀疏。
    Lk\displaystyle L_k
  2. 1/2单次晋升概率：从低层进入高一层时，只有约一半节点能“入选”。
    12\displaystyle \frac{1}{2}
  3. k 次方连续晋升：要出现在第 k 层，必须连续 k 次都成功入选。
    (12)k\displaystyle \left(\frac{1}{2}\right)^k
  4. 数值验证n=10 时 L2 期望节点数为 10/4 = 2.5 个，与“每隔三四个街区一个匝道”吻合。
    10×(12)2≈2.5\displaystyle 10 \times \left(\frac{1}{2}\right)^2 \approx 2.5

概率平衡机制

你可能想问：每条高架的入口位置是谁定的？城市规划局没有派人去数车流，而是用最简单粗暴的办法——掷硬币。每个路口抛一枚硬币，正面就建一个上高架的匝道，反面就不建。看似随意，但大数定律保证：一半路口有匝道，四分之一的路口有双层匝道，八分之一有第三层……分布天然均匀，不需要任何人工规划。

跳表的“层数”正是这样掷出来的。插入新节点时，从第 0 层开始反复抛硬币（用随机数生成器模拟），每出现一次正面层数 +1，直到出现反面为止，得到最终层数。这个过程完全随机、无状态，不需要像红黑树那样在插入后做旋转或染色。单个新节点的期望层数是一个等比级数求和：

这就是“概率平衡”的精髓：用随机性替代强制调整。红黑树靠变色和旋转维持绝对平衡；跳表揣着一枚硬币走天下，虽然每条路径不完全均衡，但统计上所有路径都接近最优。老工程师的直觉是：与其精打细算，不如抛硬币。

E[level(x)]=11−p\displaystyle E[\text{level}(x)] = \frac{1}{1-p}
当 p=1/2 时，每个新节点的平均层数约为 2 层。加上 n 个节点的规模因素，整体期望最大层高约为 log₂n，这就是“概率平衡”的数学基础。
  1. level(x)新节点的随机层数：插入节点 x 时掷硬币得到的层高，决定它拥有多少层指针。
    level(x)\displaystyle \text{level}(x)
  2. p单次晋升概率：每次掷硬币出现正面的概率，Redis 实现中取 0.5。
    p\displaystyle p
  3. 等比级数求和层数为 k 的概率是 (1-p)·p^k，对全部 k 求期望得到 1/(1-p)。
    1+p+p2+⋯=11−p\displaystyle 1 + p + p^2 + \cdots = \frac{1}{1-p}
  4. 代入 p=0.5平均每个节点约 2 层，既保证足够跳跃能力，又不至于过度浪费空间。
    E[level(x)]=2\displaystyle E[\text{level}(x)] = 2

Sorted Set 双结构

假设你是景区游客中心的工作人员，每天要回答两类问题：“张三是多少分？”（按姓名查分值）和“排行榜前十都是谁？”（按分数排序）。如果只准备一本按姓名拼音排列的花名册，查分数倒是快，但排榜要翻完整本书；如果只准备一本按分数排的排行榜，排榜快，可要查“张三”还得在榜里从头找到人。

Redis 的 Sorted Set（Zset）没有二选一，而是两本册子同时维护：一个 hash 字典（dict）存储 member → score 映射，提供 O(1) 的按成员查分；一个 skiplist 按 score 排序存储 member，提供 O(log n) 的排序与范围操作。执行 ZADD 时，先更新 hash，再把 (score, member) 插入 skiplist 保持有序。

一次 ZADD 的总成本是两个结构的开销相加：

游客中心的两本册子由同一套流程协同更新：哈希册保证“我叫张三，考了 92 分”一秒查得；跳表册保证“92 分排第几、周围是谁”尽收眼底。Redis 把“点查”和“排序”两个世界无缝拼接，这正是 Zset 能同时支撑排行榜与会员查询的秘密。

TZADD=O(1)+O(log⁡n)\displaystyle T_{\text{ZADD}} = O(1) + O(\log n)
这个组合公式揭示了 Zset 的“双引擎”：哈希负责点查的闪电速度，跳表负责有序世界的稳定高效，两者缺一不可。
  1. O(1)hash 更新：对 dict 按 member 键写入或修改 score，与集合大小无关，像花名册按姓名直接翻页。
    O(1)\displaystyle O(1)
  2. O(log n)skiplist 插入：把 (score, member) 按分值插入有序跳表，维持排行榜顺序。
    O(log⁡n)\displaystyle O(\log n)
  3. 加法顺序执行：两步先后串行完成，总耗时近似两者相加。
    TZADD\displaystyle T_{\text{ZADD}}

核心操作实现

老司机接到新订单，要往排行榜里插一个 87 分的新成员。他先上最高层高架向右一路狂飙，快接近 87 分时（下一个节点已是 90 分，超过了），就下到快速路；在快速路上再次逼近，发现下一跳又过头了，再下到地面街道；最后在 85 分和 90 分之间的空位停稳，把新门牌挂进街道，再抛硬币决定要不要顺便开通高架入口。

跳表插入的工程实现正是这个“逐层下降找前驱”的过程：从最高层开始，每层向右找到“最后一个小于新值的节点”记入 update[] 数组；然后根据随机层数创建新节点，顺着 update[] 在各层完成指针拼接。删除是逆操作：先找到目标节点，然后逐层把指向前方目标节点的指针摘除。范围查询 zrangebyscore 则先用 O(log n) 定位到分数下限，再沿 L0 向后遍历输出。

如果范围查询要返回 m 个元素，总代价为：

插入 87 分的新成员，耗时只在“下桥”途中；桥修好后，每次路过 85→90 这段路，都能稳稳经过 87。范围查询更像是沿地面街道顺路挨家挨户发通知——起点找得快，整条街逛完也快。

Trange=O(log⁡n+m)\displaystyle T_{\text{range}} = O(\log n + m)
这个范围查询公式揭示了跳表在“排序集合”场景的独特优势：定位起点后沿底层链表顺序输出即可，无需像平衡树那样做中序遍历。
  1. O(log n)定位起点：从最高层逐层下探，找到第一个不小于范围下界的节点。
    O(log⁡n)\displaystyle O(\log n)
  2. m结果数量：需要输出的元素个数，例如排行榜前 10 名，m=10。
    m\displaystyle m
  3. 对比 O(n)如果从底层开始找起点，最坏要扫过全部 n 个节点。
    O(n)\displaystyle O(n)
  4. 两阶段相加定位 + 沿底层链表遍历输出，总耗时相加。
    O(log⁡n+m)\displaystyle O(\log n + m)

性能复杂度分析

修高架当然要花钱——土地、桥墩、钢筋水泥都是额外开销。跳表也一样，每一层索引的 forward 指针都是额外的内存。但城市愿意为通行效率买单：多花一倍指针空间，换来查找从“扫码式逐户”升级为“高架飞驰”。

跳表总指针数的期望值可以精确计算：第 i 层期望节点数为 n × (1/2)^i，对所有层求和，得到总和约为 2n。也就是说，跳表的空间复杂度是 O(n)，常数因子约为 2——每个节点平均多存一个指针的代价，完全可控。

当晋升概率为 p 时，期望总指针数为：

相比红黑树，跳表的工程优势有三：一是实现简单，红黑树的左旋右旋变色让无数程序员头秃，跳表只需要“掷硬币 + 连指针”；二是范围查询天然高效，红黑树找区间需要中序遍历并回溯父节点；三是并发友好，跳表的各层指针可以通过 CAS 无锁更新，而红黑树的全局再平衡在高并发下是灾难。Redis 作者在源码注释中坦言：跳表“足够简单，且能很好地完成任务”。

E[S]=n1−p\displaystyle E[S] = \frac{n}{1-p}
p=1/2 时，期望总指针数为 2n。这是“空间换时间”的定量答案：额外空间就是每个节点平均多约 1 个指针。
  1. n底层节点数：所有数据必然出现在 L0，这是指针开销的基数。
    n\displaystyle n
  2. 等比级数每层节点数按 p 的比例递减，形成等比数列。
    n+np+np2+⋯\displaystyle n + np + np^2 + \cdots
  3. 级数求和等比级数的和收敛到 n/(1-p)，这是概率论的标准结论。
    ∑i=0∞npi=n1−p\displaystyle \sum_{i=0}^{\infty} n p^i = \frac{n}{1-p}
  4. p=1/2 代入期望总指针数为 2n，空间复杂度量级为 O(n)。
    E[S]=2n\displaystyle E[S] = 2n

工程应用场景

城市核心区寸土寸金，但几乎所有繁华地带都离不开立体交通。同样，在内存数据库和有序集合的世界里，凡是“既要有序、又要高效增删、还要范围查询”的场景，跳表都是主力选手。Redis 的 Zset 就是最著名的例子。

几个经典场景包括：直播打赏榜、游戏天梯榜用 ZADD 写分、ZREVRANGE 取 Top N；分布式延迟队列用 ZADD（时间戳，任务） 将到期时间作为 score，定时用 ZRANGEBYSCORE 取出所有已到期任务执行；内存数据库的有序索引、好友动态时间线等也常以 Zset 作为底层结构。

排行榜取 Top K 的复杂度同样优秀：

从直播间的热榜到 AI 训练任务的延迟调度，跳表像城市的立体路网一样默默支撑着“有序世界”的运转。下次你用 Redis 敲下 ZADD 时，不妨想想那个掷硬币修高架的老工程师——概率与索引的结合，让复杂世界变得简单而高效。

TZREVRANGE=O(log⁡n+m)\displaystyle T_{\text{ZREVRANGE}} = O(\log n + m)
排行榜场景公式说明：无论排行榜里躺着多少用户，取前 100 名都只需“定位最高分 + 沿底层倒序输出 100 个”，几十万用户和几万用户耗时几乎一样。
  1. ZREVRANGE倒序取区间：从分数最高端开始取 m 个元素，对应排行榜前 m 名。
    TZREVRANGE\displaystyle T_{\text{ZREVRANGE}}
  2. 定位最高分跳表支持从最高层快速找到分值最大的节点。
    O(log⁡n)\displaystyle O(\log n)
  3. m取出条数：一次取 m 条结果，与总用户数无关，T 只随 m 线性增长。
    m\displaystyle m
  4. 结论百万级排行榜取 Top 10 依然是微秒级响应。
    O(log⁡n+10)\displaystyle O(\log n + 10)

AI 应用场景

推荐系统候选池实时排序

阶段：特征工程与实时召回后的候选排序服务

解决的问题：推荐系统为每个用户生成候选物品后，需要按 CTR 预估分排序并截取 Top K。传统做法每次请求都全量排序，候选池因实时行为频繁更新，成本居高不下。用 Redis Zset 以预估分为 score 增量写入，ZREVRANGE 毫秒取 Top K，同时用 ZREMRANGEBYSCORE 淘汰低分项，让候选池始终“鲜活且有序”。

具体案例：某短视频推荐系统为每个用户维护一个“会话候选池”Zset，新物品的 CTR 预估分实时 ZADD，每次刷新页面用 ZREVRANGE key 0 49 取 50 个推荐项，全程亚毫秒，支撑每秒数万用户的个性化刷新。

分布式延迟队列与 AI 任务调度

阶段：模型训练与推理任务的异步调度

解决的问题：AI 训练任务常有“延迟触发”（如失败后 30 分钟重试、定时评测）。传统方案用数据库轮询，既慢又有时间误差；用 Redis Zset 以目标触发时间戳为 score、任务 ID 为 member，扫描线程每秒 ZRANGEBYSCORE(now, now) 取出到期任务，删除后派发执行，精准且高效。

具体案例：某 MLOps 平台的模型重试队列用 Zset 管理 10 万个延迟任务，扫描线程每秒一次 O(log n + m) 查询即可唤醒到点任务，重试延迟控制在百毫秒内，避免了对训练集群的无效空转。

HNSW 向量检索中的跳表思想

阶段：向量数据库的近似最近邻检索（ANN）

解决的问题：RAG 应用中需要在百万级向量里快速查找相似向量。HNSW（分层可导航小世界图）受跳表直接启发：用随机函数决定向量节点的层数，高层图稀疏连接远距离节点充当“高架”，底层图密集连接近邻充当“街道”，搜索时从顶层贪婪逼近再逐层下探——与跳表查找路径如出一辙。

具体案例：Milvus 与 FAISS 中的 HNSW 索引在 100 万条 768 维向量上实现毫秒级召回，正是跳表“多级索引 + 概率分层”思想在向量空间的延伸，为 RAG 应用的实时问答提供了底层加速。

Python 演示

python104 行
import random  class SkipNode:    def __init__(self, value, level):        self.value = value        self.next = [None] * (level + 1)  class SkipList:    MAX_LEVEL = 16    P = 0.5     def __init__(self):        self.head = SkipNode((float('-inf'), ''), self.MAX_LEVEL)        self.level = 0     def random_level(self):        level = 0        while random.random() < self.P and level < self.MAX_LEVEL:            level += 1        return level     def find(self, value):        cur = self.head        for i in range(self.level, -1, -1):            while cur.next[i] and cur.next[i].value < value:                cur = cur.next[i]        cur = cur.next[0]        return cur.value if cur else None     def insert(self, value):        update = [self.head] * (self.MAX_LEVEL + 1)        cur = self.head        for i in range(self.level, -1, -1):            while cur.next[i] and cur.next[i].value < value:                cur = cur.next[i]            update[i] = cur        new_level = self.random_level()        if new_level > self.level:            for i in range(self.level + 1, new_level + 1):                update[i] = self.head            self.level = new_level        node = SkipNode(value, new_level)        for i in range(new_level + 1):            node.next[i] = update[i].next[i]            update[i].next[i] = node     def delete(self, value):        update = [self.head] * (self.MAX_LEVEL + 1)        cur = self.head        for i in range(self.level, -1, -1):            while cur.next[i] and cur.next[i].value < value:                cur = cur.next[i]            update[i] = cur        target = cur.next[0]        if target and target.value == value:            for i in range(self.level + 1):                if update[i].next[i] and update[i].next[i].value == value:                    update[i].next[i] = target.next[i]            while self.level > 0 and self.head.next[self.level] is None:                self.level -= 1            return True        return False     def range_query(self, low, high):        cur = self.head        for i in range(self.level, -1, -1):            while cur.next[i] and cur.next[i].value < low:                cur = cur.next[i]        result = []        cur = cur.next[0]        while cur and cur.value <= high:            result.append(cur.value)            cur = cur.next[0]        return result  class ZSet:    def __init__(self):        self.dict = {}        self.sl = SkipList()     def zadd(self, member, score):        if member in self.dict:            self.sl.delete((self.dict[member], member))        self.dict[member] = score        self.sl.insert((score, member))     def zscore(self, member):        return self.dict.get(member)     def zrangebyscore(self, low, high):        return self.sl.range_query((low, ''), (high, '\uffff'))  if __name__ == '__main__':    z = ZSet()    z.zadd('alice', 85)    z.zadd('bob', 92)    z.zadd('carol', 78)    z.zadd('dave', 92)    print('bob score:', z.zscore('bob'))    print('80-100:', z.zrangebyscore(80, 100))
目的：用 Python 从零实现跳表，并封装一个模拟 Redis Sorted Set 的 ZSet 类，演示 ZADD、ZSCORE、ZRANGEBYSCORE 的底层工作方式。
  1. while random.random() < self.P and level < self.MAX_LEVEL:掷硬币晋升：每出现一次正面层数 +1，直到反面或达到上限。
  2. for i in range(self.level, -1, -1):从最高层开始逐层下降，查找的高架→地面路径。
  3. while cur.next[i] and cur.next[i].value < value:每层向右移动的条件：下一跳存在且值仍小于目标。
  4. if member in self.dict: self.sl.delete((self.dict[member], member))ZADD 时先按旧分数删掉旧记录，避免重复排序。
  5. self.sl.insert((score, member))把 （分数，成员） 作为整体插入跳表，分数优先、成员名次之。
  6. return self.sl.range_query((low, ''), (high, '\uffff'))范围查询：定位下限后沿底层遍历，直到超过上限。

常见误区

误区“层数是随机生成的，万一手气差所有节点都只有一层，跳表不就变回普通链表了吗？O(log n) 是不是骗人的？”

正解单次极端结果概率极低。一个 100 万节点的跳表，全部节点层高只有 1 的概率是 2 的负一百万次方，比连续中十次彩票头奖还低无数倍。跳表保证的是期望性能，大数定律让大量独立随机事件的叠加结果高度稳定，工程上可视为稳定的 O(log n)。何况 MAX_LEVEL 限制了层高上限，绝不会无限增长。

为何常见：初学者把“随机”等同于“不可控”，忽略了概率论中“大量独立事件叠加后分布稳定”的基本直觉。

误区“跳表每层得保持严格二分的结构吧？插入删除后不需要旋转或重新分布节点吗？感觉维护成本好高。”

正解完全不需要。跳表的“平衡”来自插入时的随机层数，而不是插入后的结构调整。每个新节点掷硬币决定层数并就地插入，旧节点完全不动，便天然维持了“每层约一半”的统计结构。这也是跳表相比平衡树最大的工程优势——把“事后修复”变成“事前概率”。

为何常见：习惯了平衡树“插入后必须旋转/变色”的思路，想不到可以用随机化在源头解决问题。

误区“Redis 的 Sorted Set 就是跳表，没有别的结构了。”

正解Zset 是 dict + skiplist 双结构。dict 负责 member → score 的 O(1) 点查（ZSCORE），skiplist 负责按 score 排序与范围操作（ZRANGE / ZRANK）。两者在一次 ZADD 命令中被原子地协同更新。只讲跳表就丢掉了一半设计精髓。

为何常见：技术文章标题总强调“跳表”，让人忽略了源码里其实还有一张哈希表。

误区“反正是空间换时间，我把 MAX_LEVEL 设成 128 甚至 256，性能一定更好。”

正解层数是 log₂n 级别的，100 万节点约需 20 层，2 的 32 次方已是 42 亿节点规模。MAX_LEVEL 设置过高只会徒增头节点的空指针，且每次查找都要多做无意义的层数判断。Redis 采用 32 或 64 上限，背后是经过权衡的工程智慧。

为何常见：把“空间换时间”误解为“空间越多越快”，忽略了指针跳转本身也有微小的成本。

误区“跳表是链表加强版，查找肯定也是从头到尾遍历吧？最多比普通链表快一点。”

正解恰恰相反，跳表查找从最高层开始，向右走并与目标比较，下一个节点大于目标时下移一层。整个过程是“高层快速扫过、低层精确定位”的倒金字塔路径，步数约 log₂n 而不是 n。

为何常见：沿用了普通链表的“从 head 开始 next”心智模型，没意识到多级索引的意义正是“从最稀疏的道路出发”。

面试题

Q1. 跳表查找的平均时间复杂度是多少？

单选题 · easy

  • A.O(1)
  • B.O(log n)← 正确答案
  • C.O(n)
  • D.O(n log n)

答案：B。跳表通过多级索引让查找路径长度约为 log₂n，就像高架桥几步跳过几十个路口，期望复杂度为 O(log n)。A 是哈希表的复杂度，C 是普通链表的复杂度，D 是排序类算法的典型复杂度。

Q2. 跳表新节点的层数是如何决定的？

单选题 · easy

  • A.根据节点值大小计算
  • B.随机抛硬币，正面则升层← 正确答案
  • C.插入后统一重新平衡
  • D.由用户显式指定

答案：B。跳表用随机化（掷硬币）决定层数，每次晋升概率为 p，无需事后调整，这就是“概率平衡”的含义。C 是红黑树的平衡思路，A 和 D 与跳表设计无关。

Q3. Redis Zset 中，ZSCORE（按成员查分值）依赖哪个结构？

单选题 · mid

  • A.skiplist
  • B.dict← 正确答案
  • C.数组
  • D.双向链表

答案：B。Zset 是 dict + skiplist 双结构，dict 存 member → score 映射，提供 O(1) 的点查能力。skiplist 负责按分数排序，数组和双向链表均未参与 Zset 实现。

Q4. 跳表期望的空间复杂度是？

单选题 · mid

  • A.O(1)
  • B.O(log n)
  • C.O(n)← 正确答案
  • D.O(n log n)

答案：C。期望总指针数 = n/(1-p)，p=1/2 时为 2n，空间复杂度为 O(n)。虽然常数因子为 2，但量级与节点数线性相关，不是对数级或线性对数级。

Q5. 相比红黑树，跳表在哪些方面有优势？

多选题 · mid

  • A.实现简单，无需旋转变色← 正确答案
  • B.范围查询天然高效← 正确答案
  • C.并发场景更易实现无锁← 正确答案
  • D.最坏时间复杂度更低

答案：ABC。跳表实现简单（掷硬币 + 连指针）、范围查询沿底层链表直接遍历、并发下可用 CAS 逐层更新。但跳表在极端随机下最坏是 O(n)，红黑树保证最坏 O(log n)，所以 D 错误。

Q6. 跳表查找时，正确的搜索路径是？

单选题 · mid

  • A.从底层向右逐个扫描
  • B.从最高层向右，快过头了下移← 正确答案
  • C.从最高层向左搜索
  • D.随机选一层开始

答案：B。查找从最高层出发向右走，当下一个节点大于目标时下移到低一层，逐层逼近目标。A 是普通链表行为，C 方向错误，D 的随机起点无法保证对数级性能。

Q7. 晋升概率 p=0.5 时，一个节点出现在第 k 层的概率是？

单选题 · hard

  • A.1/2
  • B.1/2^k← 正确答案
  • C.1/(2n)
  • D.k/2

答案：B。节点要出现在第 k 层，必须连续 k 次晋升成功，每次概率 1/2，所以总概率为 (1/2)^k。A 是单次晋升概率，C 混淆了节点数量，D 无概率意义。

Q8. 以下哪些场景适合用跳表（Zset）实现？

多选题 · hard

  • A.实时排行榜 Top N← 正确答案
  • B.基于到期时间的延迟队列← 正确答案
  • C.无序 KV 缓存
  • D.按范围获取有序数据← 正确答案

答案：ABD。排行榜需要排序与范围取数（ZREVRANGE），延迟队列把时间戳当 score 并用 ZRANGEBYSCORE 取到期任务，有序范围查询正是跳表强项。C 是无序 KV，哈希表更合适，不需要跳表的有序性。

Q9. 跳表第 i 层的期望节点数约为第 i-1 层的多少？

单选题 · easy

  • A.相等
  • B.一半← 正确答案
  • C.两倍
  • D.随机无规律

答案：B。晋升概率 p=1/2，每层只有约一半节点进入上一层，所以第 i 层节点数约为第 i-1 层的一半，形成逐层稀疏的多级索引，就像高架匝道逐层减少。

Q10. 关于 Redis Zset 的 ZADD 操作，下列说法正确的是？

多选题 · mid

  • A.先更新 dict，再插入 skiplist← 正确答案
  • B.当 member 已存在时，按新 score 调整排序位置← 正确答案
  • C.只需操作 skiplist 即可
  • D.时间代价约为 O(1) + O(log n)← 正确答案

答案：ABD。ZADD 先写 dict（member → score），再把 (score, member) 插入 skiplist；member 已存在时先删旧记录再插新分值，保证有序。C 忽略 dict 的存在。总代价是 hash 的 O(1) 加跳表的 O(log n)。