想象你走进一座巨大的图书馆——这里是 Redis 的「收藏馆」（Sorted Set，简称 zset）。馆里每一本书都带着一个「热度分值」，从 1 到 100 贴着标签，整整齐齐排成长长的书架。你要找一本热度 67 的书，如果使用入口处的电脑检索机（dict 哈希表），输入书名一秒定位到具体书架——这是「单点查找」的绝活。但如果你想问「热度 60 到 80 之间有哪些书」呢？电脑检索机就无能为力了，你需要一套「楼层导览图」（skiplist 跳表）。 这套导览图分好几层：最底层的 L0 是全部馆藏清单，密密麻麻；往上一层 L1 只列热门书；再往上 L2 只列爆款；最高层 L3 只保留镇馆之宝。找书时从最高层往下跳——先看爆款名录圈定大致区间，再翻热门书目缩小范围，最后落到 L0 精确锁定。每跳一层，候选范围就砍掉一大截，几步之内就能从几百万本书里揪出目标。这就是 Redis zset 的底层秘密：一张多层导览图 + 一台检索机，配合得天衣无缝。本文带你拆解这套设计，看懂跳表的节点、跨度、晋升概率 p=0.25 背后的工程智慧。

岗位关联

理解 zset 底层的 skiplist + dict 双结构，你将能解释 Redis 范围查询为何高效、排行榜与延迟队列为何选它，并在系统设计中做出正确的存储选型判断。

目录
  1. 可视化演示
  2. 双结构设计——检索机与导览图各司其职
  3. 跳表节点结构——书签上的层层指引
  4. 层级晋升机制——四分之一概率的掷骰子
  5. 范围查询实现——顺着楼层导览逐排浏览
  6. 复杂度分析——一步跳三层，对数级收敛
  7. 工程取舍——为什么是跳表而不是平衡树
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示Redis Sorted Set底层跳表结构：多层指针索引、节点层级随机选择(p=0.25)、以及新节点插入时的搜索路径与指针更新过程。

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

跳表多层索引结构 Header/Tail：哨兵节点，占满所有层 高层节点：概率p=0.25逐层提升 P(node at level k) = p^(k-1) 每层都是有序链表，高层索引加速底层遍历，实现O(log n)查找。

双结构设计——检索机与导览图各司其职

走进 zset 图书馆，你会发现它刻意配备了两套检索设施。入口处是一台电脑检索机——输入书名，零点几秒就告诉你它在哪个书架的哪一层，这就是 dict 哈希表。而在每层楼道里贴着好几版「楼层导览图」：最全的一版列了所有馆藏，往上有一版只列热门书，再往上只列爆款书。这就是 skiplist 跳表。一台机器管「精确查找」，一摞导览图管「范围浏览」，二者缺一不可。

Redis 的 Sorted Set 在设计上同样是「一鱼两吃」：dict 保存 member 到 score 的映射，负责 O(1) 的单点写入与查询；skiplist 则按 score 维护一个有序结构，负责区间扫描与排序。同一本书（member 对象）在两个结构里各有一份「档案条目」，但通过指针共享同一对象实体，绝不复制字符串内容。当客户端执行 ZADD 时，Redis 先更新 dict，再在 skiplist 中插入一个新的 (score, member) 节点；ZSCORE 只查 dict；ZRANGE 只走 skiplist。

两个结构通过双向指针保持同步，插入删除都在 O(log n) 内完成。这样设计让「点查」和「范围查」互不拖累——如果只用 skiplist，单点查询要 O(log n)；如果只用 dict，范围查询只能全表扫描。正是这种分工，让 zset 在游戏排行榜、延迟队列等场景中游刃有余。

回到图书馆：一位读者想查某本书是否在馆，直接问电脑检索机；另一位读者想浏览「热度 60 到 80」的书架，就拿起导览图逐层定位。两台设施各忙各的，互不干扰，却共享同一套藏书——这正是 zset 双结构最精妙的地方。

zset=dict⏟单点查询+skiplist⏟范围查询\text{zset} = \underbrace{\text{dict}}_{\text{单点查询}} + \underbrace{\text{skiplist}}_{\text{范围查询}}
dict 解决「这本书在哪个书架」的单点问题，skiplist 解决「整个书架区间里有哪些书」的范围问题，两者共享同一批节点。
  1. zsetRedis 的 Sorted Set 类型，它的值对象由两种底层结构组合而成
    zset\text{zset}
  2. dict哈希表结构，以 member 为键、score 为值，提供 O(1) 精确查找与更新
    dict:member→score\text{dict}: \text{member} \to \text{score}
  3. skiplist跳表结构，按 score 排序的多层链表，支持范围遍历与排名
    skiplist:score→member\text{skiplist}: \text{score} \to \text{member}
  4. 组合关系两结构共享节点指针，写操作同步更新，而非复制数据
    同增同删，指针共享\text{同增同删，指针共享}

跳表节点结构——书签上的层层指引

当你展开图书馆的导览图，会发现每一版导览图上的记录都像一个小书签：书签中央写着书名和热度（score），书签下方只延伸出一条「后退箭头」指回前一个书架位；而书签上方伸出好几条「前跳箭头」，分别指向更高层导览图上的下一本书。箭头越长，跳过的中间书架越多。管理员就是靠这些箭头快速移动的。

Redis 的 zskiplistNode 正是这样的书签。它包含四部分：member 和 score 是书的身份；backward 指针指向前驱节点，用于倒序遍历；level 数组则是一个柔性数组，每个 level 元素由 forward 指针和 span 字段组成。forward 指向该层下一个节点，span 记录「从当前节点沿这一层跳到目标，在底层链表上跨越了多少个节点」。level 数组的长度是插入时随机生成的，通常远小于 ZSKIPLIST_MAXLEVEL=32。

span 是跳表实现排名的关键。ZREVRANK 求某成员排名时，查找路径每向右移动一次，就把该层的 span 累加起来，最后得到的就是该节点在底层链表中的位置。由于 p=0.25 下每个节点平均只有 1.33 个 level 元素，这些计数占用非常紧凑，但同时为 O(log n) 的排名查询提供了足够的路径信息。

就像你的书签上标着「从这里跳过去，会经过 7 本书」——管理员不用真的一本本数，就能报出你要找的书排在整条书架的第几本。span 给跳表装上了里程表，让排名查询不再需要遍历全部节点。

span(u,v)=rank(v)−rank(u)\text{span}(u, v) = \text{rank}(v) - \text{rank}(u)
span 是带箭头的「里程表」：从节点 u 沿高层指针跳到 v，里程表记录了底层链表上你实际跨越了多少本书。
  1. span从 u 沿某一层的指针跳到 v 时，底层完整链表上经过的节点个数
    span(u,v)\text{span}(u, v)
  2. rank节点在 L0 完整链表中的位置序号，从 0 开始计数
    rank(v)=rank(u)+span(u,v)\text{rank}(v) = \text{rank}(u) + \text{span}(u, v)
  3. 路径累计从起点到目标的完整路径上，所有被跳过的节点数逐层累加即得排名
    rank(v)=∑路径span(每一步)\text{rank}(v) = \sum_{\text{路径}} \text{span}(\text{每一步})

层级晋升机制——四分之一概率的掷骰子

新书上架时，管理员会掷一个特制的四面骰子：掷出 1，这本书就有资格进入「上一层导览图」；再掷一次，又是 1 才能进入再上一层。所以大约 1/4 的书出现在第二层，1/16 出现在第三层，1/64 出现在第四层——层数越高，书目越精。掷骰子完全随机，任何一本书都有机会成为「爆款」，与它的热度分无关。

跳表的层级同样完全由随机算法决定。插入节点时调用 t_random() 生成 level：从 1 开始，每次以概率 p=0.25 继续 +1，直到失败或达到上限 ZSKIPLIST_MAXLEVEL=32。这样得到的层数服从几何分布。Redis 之所以选 p=0.25 而非经典论文中的 0.5，是因为内存数据库里指针占用是主要成本：p 越小，平均每节点指针数越少，空间越省。

p=0.25 时，每个节点平均层数为 1/(1-p)=4/3，即平均只有 1.33 个前向指针；而 p=0.5 时是 2 个指针，跳表整体指针内存节省约三分之一。代价是高层节点更稀疏，查找时垂直下降次数略增，但常数仍然可控。最大层级 32 足以支撑 2^32 量级的元素规模，几乎永远不会触顶。

掷骰子看似随意，却保证了每层导览图上的书目大约是上一层的四倍——下宽上尖，形如金字塔。这份「随机的秩序」让跳表不需要任何旋转调整，就能保持极佳的查找效率，比起红黑树那种需要复杂旋转的平衡方式，实在省心太多。

P(L=k)=(1−p)pk−1,E[L]=11−p=43P(L = k) = (1-p)p^{k-1}, \quad \mathbb{E}[L] = \frac{1}{1-p} = \frac{4}{3}
一个节点恰好有 k 层的概率，是「前 k-1 次都成功晋升、第 k 次晋升失败」的连乘结果；平均下来每个节点只有 4/3 层，非常省内存。
  1. P(L=k)一个节点恰好拥有 k 层的概率，等于前 k-1 次晋升成功、第 k 次失败
    P(L=k)=(1−p)⋅pk−1P(L=k) = (1-p) \cdot p^{k-1}
  2. p^{k-1}连续 k-1 次掷骰子都命中晋升概率 p 的概率
    pk−1,p=0.25p^{k-1}, \quad p = 0.25
  3. E[L]层数的数学期望，对几何分布求和得到
    E[L]=1+p+p2+⋯=11−p\mathbb{E}[L] = 1 + p + p^2 + \cdots = \frac{1}{1-p}
  4. 代入 p=0.25期望层数为 4/3，即平均每个节点只有 1.33 层
    11−0.25=43≈1.33\frac{1}{1-0.25} = \frac{4}{3} \approx 1.33

范围查询实现——顺着楼层导览逐排浏览

当读者问「热度 60 到 80 的书有哪些」时，管理员从最高层导览图出发，先找到热度 60 附近的区域，然后落回最全的 L0 清单，从第一本符合的书开始，顺着箭头一排排往后读，读到热度超过 80 才停手。这套「先跳后走」的方法，让范围浏览变得又快又准。

这就是 ZRANGEBYSCORE 的实现：先在 skiplist 中查找 score 的下界（≥ min），再从该位置沿 forward[0] 逐节点遍历，直到超过 max。由于 L0 是完整的有序双链表，向前向后都很自然。ZRANGE 取排名区间 [start, stop] 时则利用 span 累计 rank 快速定位起点，再顺序走 m-1 步。zrevrange 的逻辑完全相同，只是方向反过来：从高层找上界，沿 backward 从大到小收集。

skiplist 天然支持范围遍历——找到一个端点后，范围内每个节点都只需 O(1) 移动一步；而平衡树做范围遍历需要中序遍历，树节点在内存中不连续、cache miss 更多。对于「分页取 Top N」「按时间窗口取样本」这类高频操作，skiplist 的链表式连续步进远比树的穿线遍历友好。

管理员不需要把整座馆藏书目从头翻起——先看爆款名录圈定楼层，再落到完整书单逐排扫过。找起点靠「跳」，扫结果靠「走」：一跳一走的配合，让百万级数据的范围查询也只在眨眼之间。

Trange(n,m)=O(log⁡n+m)T_{\text{range}}(n, m) = O(\log n + m)
范围查询的总时间 = 「跳到起点」的对数时间 + 「逐本输出」的线性时间，命中越多输出越久，但起点的定位永远是对数级的。
  1. T_range范围查询的总耗时，由定位和输出两个阶段构成
    Trange=Tlocate+m⋅TstepT_{\text{range}} = T_{\text{locate}} + m \cdot T_{\text{step}}
  2. log n从最高层逐层下降到下界附近所需的比较次数
    Tlocate=O(log⁡n)T_{\text{locate}} = O(\log n)
  3. m命中集合的元素个数，每个元素沿链表移动一步 O(1)
    m⋅O(1)=O(m)m \cdot O(1) = O(m)

复杂度分析——一步跳三层，对数级收敛

如果把查找过程画成图，就像从图书馆顶楼的大厅往下走螺旋楼梯：每走一步，导览图的「书目密度」就稀疏一些，候选范围缩小到原来的四分之一。从顶层到地面，一路只走了 O(log n) 步，却把几百万本书的搜索空间压缩成寥寥数本。这种感觉，就像查字典时先翻目录、再翻章节、最后翻页码。

在 p=0.25 的跳表中，期望查找路径长度为 O(log_{1/p} n) = O(log_4 n)。因为每向上走一层，候选节点数就乘以 p，即缩小为原来的 1/4，所以从顶层一路查到 L0，需要比较约 log_4 n 次。这与二叉平衡树的 O(log_2 n) 只差一个常数因子 2，对数意义上完全同阶，因此工程上直接写作 O(log n)。

需要强调的是，跳表的 O(log n) 是「期望」复杂度而非最坏保证。极端随机情况下所有节点都在同一层，链表退化为单链表，查找退化为 O(n)。但每个节点的层数独立同分布，这种全面退化在实际中概率极低。内存方面，p=0.25 时每个节点平均 1.33 个前向指针，远小于平衡树每个节点 2-3 个指针加颜色标记的开销。

就像螺旋楼梯每一圈都能帮你过滤掉四分之三的楼层，你永远不用一层层爬完所有书架。偶尔运气差一点，楼梯「只修了一层」，那就只能沿长廊走一遍——但图书馆把这件罕见事件的概率压到了几乎可以忽略。

E[C]=O(log⁡1/pn),最坏 Cmax⁡=O(n)\mathbb{E}[C] = O\left(\log_{1/p} n\right), \quad \text{最坏 } C_{\max} = O(n)
平均情况下每跳一步淘汰四分之三的候选元素，所以是 O(log n)；但若骰子连续「失手」让所有书都只进 L0，就会退化成逐本查找的 O(n) 链表。
  1. E[C]查找过程平均需要比较的次数
    E[C]=O(log⁡4n)\mathbb{E}[C] = O(\log_4 n)
  2. 底数推导每上升一层候选范围缩为原来的 p 倍，n·p^k = 1 时 k = log_{1/p} n
    n⋅pk=1⇒k=log⁡1/pnn \cdot p^{k} = 1 \Rightarrow k = \log_{1/p} n
  3. 最坏情况所有节点层数都等于 1，跳表退化为普通单链表
    Cmax⁡=O(n)C_{\max} = O(n)

工程取舍——为什么是跳表而不是平衡树

你可能会问：图书馆为什么不用更「标准」的索书号分类树（红黑树）来组织导览图？管理员会告诉你：树形索引改起来太麻烦——每插一本书，可能要旋转、变色、调整一堆指针；而跳表只需要把骰子一掷、沿路更新几个指针，规则简单到实习生都能一次写对。这就是工程世界对「简单」的偏爱。

这是 Redis 作者 antirez 的真实选择。平衡树（如红黑树）保证严格 O(log n)，但实现复杂：插入删除需处理左旋右旋、节点变色，范围遍历需要中序穿线。跳表最坏情况虽差，但实现代码量约为红黑树的三分之一，范围查询直接沿链表遍历，内存上还因 p=0.25 而更紧凑。缓存局部性方面，skiplist 的节点在内存中不连续，但这与树结构相近，没有明显劣势。

更关键的是，zset 的双结构让 ZSCORE 走 dict，常用单点操作达到 O(1)，这更是纯树结构做不到的。此外跳表对并发修改更友好：插入只需更新局部前驱的指针，加锁范围小；红黑树的旋转则可能波及局部子树，锁粒度更粗。在 Redis 的单线程模型下，实现简单意味着更少的 bug 与更易维护的源码，这本身就是巨大的工程价值。

zset 图书馆最终选择了「导览图 + 掷骰子」这套质朴方案：不去维护金贵的平衡树，而是用概率让结构近似平衡。少一点理论上的「绝对完美」，换来的是写起来简单、跑起来省内存、并发起来不打架——这正是工程世界的智慧。

Mptr=n1−p=43n（跳表）Mtree≈2n（红黑树）M_{\text{ptr}} = \frac{n}{1-p} = \frac{4}{3}n \quad \text{（跳表）} \qquad M_{\text{tree}} \approx 2n \quad \text{（红黑树）}
全部节点加起来，跳表平均只需约 4n/3 个前向指针，而红黑树每个节点要存左、右、父三个指针及颜色位——内存差距一眼可见。
  1. M_ptr跳表全节点前向指针的总数，等于节点数乘以期望层数
    Mptr=n⋅E[L]=n1−pM_{\text{ptr}} = n \cdot \mathbb{E}[L] = \frac{n}{1-p}
  2. 代入 p=0.25每节点 4/3 个指针，共 4n/3 个前向指针
    n0.75=43n\frac{n}{0.75} = \frac{4}{3}n
  3. 红黑树指针每节点存左孩子、右孩子、父节点三个指针，约 2n+ 个有效指针
    Mtree≈2nM_{\text{tree}} \approx 2n

AI 应用场景

实时排行榜——玩家分数的实时冲刺

阶段：在线数据存储与高性能查询

解决的问题：排行榜需要高频「更新分数 + 取 TopN」。传统方案用 SQL ORDER BY score DESC LIMIT 100，每次全表排序代价高，高并发下数据库扛不住。zset 用 skiplist 维护有序分数，ZADD 更新 O(log n)，ZREVRANGE 取 Top100 为 O(log n + 100)，就像图书馆管理员翻一下爆款名录就能报出前 100 名。

具体案例：某日活千万的休闲手游，玩家每局结束把分数 ZADD 进 zset；运营大屏每 5 秒 ZREVRANGE 拉取前 100 名展示；同时用 ZSCORE 查任意玩家当前排名。整套逻辑由 Redis 单节点承担每秒数万 QPS，无需预计算排行榜。

AI 训练样本的时间窗口截取

阶段：数据预处理 / 特征工程

解决的问题：训练序列模型（推荐、风控）需要「取某用户最近 N 天行为」。用 MySQL 的 ts BETWEEN 查询，一旦未命中索引就全表扫描；用 zset 以时间戳为 score、行为 ID 为 member，ZRANGEBYSCORE 一条命令返回有序行为序列，就像沿着导览图快速圈出指定时间段的所有事件书签。

具体案例：推荐团队要构造「用户近 7 天点击过的商品序列」特征：线上每次点击产生一次 ZADD 写入 per-user zset，离线特征任务用 ZRANGEBYSCORE 拉取窗口数据并拼接成序列输入模型，比原先 ClickHouse 按时间戳查询的耗时还低一个量级。

AI 异步任务延迟调度

阶段：任务编排与调度

解决的问题：训练任务或推理任务需要延迟触发。传统定时扫描数据库「到期任务」低效且昂贵。用 zset 以执行时间戳为 score 做延迟队列，后台进程定时 ZRANGEBYSCORE(0, now) 取到期任务执行；任务失败时 ZADD 到未来时间戳即可延迟重试，一切有序可控。

具体案例：某 AI 平台承接批量图片审核推理，任务提交后延迟 30 秒执行以便聚合多图；调度器用 zset 按「应执行时间」排序，每 5 秒取到期待处理任务投递到 GPU 推理队列，任务级 SLA 稳定在秒级，代码量比引入独立消息队列少得多。

Python 演示

python71 行
import random  class Node:    def __init__(self, score, member, level):        self.score = score        self.member = member        self.next = [None] * level  class Skiplist:    MAX_LEVEL = 16    P = 0.25     def __init__(self):        self.header = Node(0, "HEAD", self.MAX_LEVEL)        self.level = 1     def random_level(self):        lvl = 1        while random.random() < self.P and lvl < self.MAX_LEVEL:            lvl += 1        return lvl     def insert(self, score, member):        update = [None] * self.MAX_LEVEL        cur = self.header        for i in range(self.level - 1, -1, -1):            while cur.next[i] and cur.next[i].score < score:                cur = cur.next[i]            update[i] = cur        lvl = self.random_level()        if lvl > self.level:            for i in range(self.level, lvl):                update[i] = self.header            self.level = lvl        node = Node(score, member, lvl)        for i in range(lvl):            node.next[i] = update[i].next[i]            update[i].next[i] = node        return node     def search(self, score):        cur = self.header        for i in range(self.level - 1, -1, -1):            while cur.next[i] and cur.next[i].score < score:                cur = cur.next[i]        cur = cur.next[0]        return cur if cur and cur.score == score else None     def range_by_score(self, lo, hi):        result = []        cur = self.header        for i in range(self.level - 1, -1, -1):            while cur.next[i] and cur.next[i].score < lo:                cur = cur.next[i]        cur = cur.next[0]        while cur and cur.score <= hi:            result.append((cur.score, cur.member))            cur = cur.next[0]        return result  if __name__ == "__main__":    zset = Skiplist()    for name, score in [("alice", 65), ("bob", 80), ("carol", 42),                        ("dave", 90), ("eve", 67)]:        zset.insert(score, name)    print("范围 [60, 85]:", zset.range_by_score(60, 85))    hit = zset.search(80)    print("精确查找 80:", hit.member if hit else "不存在")
目的：用约 60 行实现一个简化版跳表，模拟 zset 的 skiplist 侧核心逻辑——随机层级晋升、O(log n) 精确查找、按分数范围查询。
  1. while random.random() < self.P and lvl < self.MAX_LEVEL:掷骰子决定节点层数，p=0.25 保证平均只有 1.33 层。
  2. for i in range(self.level - 1, -1, -1):从最高层向下逐层搜索，这是「先看爆款名录再落回完整清单」的遍历顺序。
  3. while cur.next[i] and cur.next[i].score < score:在当前层向右跳到不超过目标分数的节点，跳过中间大片元素。
  4. if lvl > self.level:新节点的层数超过历史最高层时，需要把头节点的高层指针也纳入更新范围。
  5. node.next[i] = update[i].next[i]新节点先接住前驱原本指向的下一个节点，断链后不丢数据。
  6. update[i].next[i] = node再让前驱指向自己，完成这一层的链表插入。
  7. result.append((cur.score, cur.member))从下界定位后沿 L0 逐节点收集，直到超过上界，正是 ZRANGEBYSCORE 的核心循环。

常见误区

误区跳表平均 O(log n)，红黑树也是 O(log n)，那跳表在哈希表加持下肯定完胜，所有场景都应该更快。

正解跳表与红黑树的对数复杂度只差常数因子。p=0.25 时高层节点更稀疏，查找的垂直下降次数比 p=0.5 略多，常数并不占优。Redis 选跳表不是因为「更快」，而是因为它更简单、范围遍历更自然、配合 dict 后单点查询直接 O(1)。真正的性能优势来自双结构分工，而非跳表本身。

为何常见：只看到「O(log n)」这个记号，忽略了常数因子和系统设计，误把复杂度等价于性能。

误区跳表里层数多的节点，一定是分数高或者被频繁访问的「热门书」。

正解层数完全由插入时的一次随机骰子决定，与 score、访问频率毫无关系。一个低分冷门节点可能随机到 5 层，一个高分热点节点也可能只有 1 层。层数只是「索引密度」的属性，不是「内容热度」的属性。

为何常见：人们容易把结构上的「显眼位置」和语义上的「重要程度」混为一谈，就像把导览图上的大字号等同于书的价值。

误区zset 用了两个底层结构，等于把 member 和 score 各存了两遍，内存翻倍。

正解dict 保存 member→score 映射，skiplist 保存 score→member 的有序节点，两个结构通过指针共享同一个 member 字符串对象，并不复制数据内容。真正多出来的只是 skiplist 的 level 指针数组和 dict 的哈希桶开销，p=0.25 使得这部分非常小。

为何常见：直观上「两个结构 = 两份数据」，忽略了指针共享这一节省内存的关键设计。

误区p=0.5 时每层节点数是 p=0.25 的两倍，高层更密集，查找应该明显更快，所以 0.25 是性能妥协。

正解p 只影响常数因子，不影响 O(log n) 的量级。p=0.25 让每节点平均指针数从 2 个降到 1.33 个，省下约 1/3 的指针内存，而查找常数只增加约一个固定的比例。对 Redis 这种内存数据库，空间就是生命，省内存换取的收益远大于常数上的微小牺牲。

为何常见：只盯着查找延迟单一指标，忽略了内存占用、缓存命中率等同样影响系统吞吐的因素。

面试题

Q1. Redis 的 zset 底层采用哪两种结构组合实现？

单选题 · easy

  • A.B+树与哈希表
  • B.跳表与哈希表← 正确答案
  • C.红黑树与数组
  • D.有序数组与链表

答案：B。zset 用 skiplist 维护按 score 排序的有序链表以支持范围查询，同时用 dict 维护 member→score 映射实现 O(1) 单点操作。B+树是 MySQL 索引的选择，红黑树常见于内存 Map 实现，都不符合 zset 的组合方式。

Q2. Redis 跳表的层级晋升概率 p 的取值是多少？

单选题 · easy

  • A.0.1
  • B.0.25← 正确答案
  • C.0.5
  • D.0.75

答案：B。经典跳表论文采用 p=0.5，但 Redis 为了节省指针内存，将晋升概率定为 0.25。这样每个节点平均层数为 1/(1-p)=4/3，约为 1.33 个指针，比 p=0.5 时的 2 个指针省下约三分之一内存。

Q3. zrevrange 命令返回元素的顺序是？

单选题 · easy

  • A.分数从低到高
  • B.分数从高到低← 正确答案
  • C.按插入时间先后
  • D.随机顺序

答案：B。zrevrange 是 zrange 的反向操作，沿跳表 L0 的 backward 指针从后往前遍历，因此分数从高到低。zrange 是从低到高，二者合起来覆盖了排行榜的正倒序展示需求。

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

单选题 · mid

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

答案：B。p=0.25 时每向上走一层候选范围缩小为原来的 1/4，期望比较次数为 O(log_4 n)，即 O(log n)。它比平衡树的 O(log_2 n) 只差常数因子 2，因此对数意义上同阶。

Q5. 关于 zset 中的 dict 哈希表结构，下列说法正确的有哪些？

多选题 · mid

  • A.键是成员 member← 正确答案
  • B.值是分数 score← 正确答案
  • C.负责按分数范围查询
  • D.实现 O(1) 的单点更新← 正确答案

答案：ABD。dict 以 member 为键、score 为值，解决「这个成员多少分」的单点问题，ZADD 更新分数时 O(1) 改 dict。按分数范围查询是 skiplist 的职责，dict 无法做到，因此 C 错误。

Q6. 跳表节点中 span 字段表示什么？

单选题 · mid

  • A.节点自身的高度
  • B.节点到链表末尾的距离
  • C.该层指针跨越的底层节点个数← 正确答案
  • D.节点存储的分数值

答案：C。span 记录从当前节点沿某一层 forward 指针跳到目标节点，在 L0 完整链表上跨越了多少个节点。它用于在查找时累加计算排名，让 ZREVRANK 等命令无需遍历整个链表即可知道成员位置。

Q7. 若 p=0.25，一个节点恰好有 2 层的概率是多少？

单选题 · mid

  • A.0.25
  • B.0.75
  • C.0.1875← 正确答案
  • D.0.0625

答案：C。恰好 2 层意味着第 1 次晋升成功且第 2 次失败，概率为 (1-p)×p = 0.75×0.25 = 0.1875。选项 A 是单次晋升成功的概率，D 是恰好 3 层的概率（0.75×0.25×0.25=0.046875）的近似干扰项。

Q8. 为什么 Redis 选择跳表而非平衡树来实现 zset 的范围查询？

多选题 · hard

  • A.跳表实现更简单，代码量约为红黑树的三分之一← 正确答案
  • B.跳表范围遍历直接沿链表走，比树的中序遍历更自然← 正确答案
  • C.跳表能保证最坏 O(log n) 的严格复杂度
  • D.跳表通过概率达到近似平衡，无需旋转操作← 正确答案

答案：ABD。跳表的优势在于实现简单、范围遍历直接、靠随机晋升免去旋转。但它的 O(log n) 是期望复杂度而非最坏保证，极端情况下会退化为 O(n)，所以 C 错误。红黑树反而有严格最坏保证，这正是跳表在理论上「不完美」的地方。

Q9. 对 n 个元素的 zset 执行 ZRANGEBYSCORE 且命中 m 个元素，时间复杂度是多少？

单选题 · hard

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

答案：B。时间分为两段：先在跳表中从高层向下定位下界节点，耗时 O(log n)；再从下界沿 L0 逐个收集命中元素，每个 O(1)，共 O(m)。因此总复杂度为 O(log n + m)，选项 C 漏掉了定位成本。

Q10. 关于跳表最坏情况与工程权衡，下列说法正确的有哪些？

多选题 · extreme

  • A.最坏情况下查找复杂度退化为 O(n)← 正确答案
  • B.p=0.25 比 p=0.5 更省指针内存，但查找常数略大← 正确答案
  • C.降低 p 会让高层节点更稀疏← 正确答案
  • D.Redis 中节点可占用的最大层级为 32← 正确答案

答案：ABCD。若随机晋升全部失败，所有节点只有 1 层，跳表退化为普通链表，查找 O(n)，A 正确。p 越小，每层节点越稀疏，指针越省而垂直下降次数略增，B、C 正确。Redis 用 ZSKIPLIST_MAXLEVEL=32 限制最高层数，足以支撑海量数据，D 正确。