跳表实现与性能剖析：为什么 Redis 选它而不是红黑树

2026/7/10 23:02:18

跳表实现与性能剖析：为什么 Redis 选它而不是红黑树

一、一道面试题引出的数据结构选型

"Redis 的有序集合（Sorted Set）底层用的是什么数据结构？" 答案是跳表和压缩列表。但如果继续追问："为什么用跳表而不用红黑树或 AVL 树？" 能给出完整回答的人就不多了。

这个问题触及了数据结构选型的核心：不是看谁的理论复杂度更优，而是看谁在实际工程约束下表现更好。这篇文章从实现出发，回答为什么跳表在 Redis 的场景中是更优选择。

二、跳表的结构原理

graph TD subgraph 第3层 H3["head(-∞)"] --> N30[30] --> T3["tail(+∞)"] end subgraph 第2层 H2["head(-∞)"] --> N10[10] --> N30 --> N50[50] --> T2["tail(+∞)"] end subgraph 第1层 H1["head(-∞)"] --> N3[3] --> N10 --> N20[20] --> N30 --> N40[40] --> N50 --> N60[60] --> T1["tail(+∞)"] end

跳表的核心思想：用多层索引加速链表查找。底层是完整的有序链表，上层是下层的"快速通道"。每次查找从顶层开始，能跳过大量节点后下降到底层。

三、生产级实现（参考 Redis 设计）

import random from typing import Optional class SkipListNode: """跳表节点 与标准链表的区别：每个节点维护一个 forward 数组， forward[i] 指向第 i 层的下一个节点。 """ __slots__ = ("key", "value", "forward", "span") # span[i] 记录 forward[i] 跨越了多少个节点， # 用于快速计算排名（ZRANK 操作）。 def __init__(self, level: int, key, value): self.key = key self.value = value self.forward: list[Optional["SkipListNode"]] = [None] * level self.span: list[int] = [0] * level class SkipList: """跳表：Redis Sorted Set 的底层实现参考 关键设计决策： 1. 最大层数 32：2^32 > 40 亿，对于内存中的集合足够。 2. 升级概率 0.25：每个节点有 25% 机会升一层。 这个值的选择影响了空间开销与查找速度的平衡。 3. 维持 span 字段：支持 O(log n) 的按排名查找。 """ MAX_LEVEL = 32 # 最大层数 P = 0.25 # 升级概率（Redis 用的是 ZSKIPLIST_P） def __init__(self): self.head = SkipListNode(self.MAX_LEVEL, None, None) self.level = 1 # 当前最高层（从 1 开始） self.length = 0 # 节点总数 def _random_level(self) -> int: """随机生成新节点的层数 每个节点有 P 的概率升级到第 k 层，有 (1-P) 的概率止步。 期望层数 = 1/(1-P) = 1.33（当 P=0.25 时）。 这意味着每个节点平均有 1.33 个 forward 指针， 额外的空间开销约为 33%，在内存中可以接受。 """ level = 1 while random.random() < self.P and level < self.MAX_LEVEL: level += 1 return level def insert(self, key, value) -> None: """插入节点：O(log n) 期望复杂度""" # update[i] 记录第 i 层中最后一个 key < 插入 key 的节点 update = [None] * self.MAX_LEVEL # rank[i] 记录从 head 到 update[i] 之间的节点跨度 rank = [0] * self.MAX_LEVEL current = self.head # 从最高层向下搜索插入位置 for i in range(self.level - 1, -1, -1): # 累加跨度 rank[i] = rank[i + 1] if i < self.level - 1 else 0 while ( current.forward[i] and current.forward[i].key < key ): rank[i] += current.span[i] current = current.forward[i] update[i] = current # 生成新节点的层数 new_level = self._random_level() if new_level > self.level: # 新节点层数更高，补充上层 update for i in range(self.level, new_level): rank[i] = 0 update[i] = self.head update[i].span[i] = self.length self.level = new_level # 在各层插入新节点 new_node = SkipListNode(new_level, key, value) for i in range(new_level): # 链表的插入操作 new_node.forward[i] = update[i].forward[i] update[i].forward[i] = new_node # 更新 span new_node.span[i] = ( update[i].span[i] - (rank[0] - rank[i]) if update[i].forward[i] else 0 ) update[i].span[i] = (rank[0] - rank[i]) + 1 # 对于高于新节点层数的层，span 加 1 for i in range(new_level, self.level): update[i].span[i] += 1 self.length += 1 def search(self, key): """查找节点：O(log n) 期望复杂度""" current = self.head for i in range(self.level - 1, -1, -1): while current.forward[i] and current.forward[i].key < key: current = current.forward[i] current = current.forward[0] if current and current.key == key: return current.value return None def get_by_rank(self, rank: int): """按排名查找：O(log n)，得益于 span 字段""" if rank < 1 or rank > self.length: return None current = self.head traversed = 0 for i in range(self.level - 1, -1, -1): while ( current.forward[i] and traversed + current.span[i] <= rank ): traversed += current.span[i] current = current.forward[i] if traversed == rank: return current.value return None

四、为什么 Redis 选择跳表

4.1 范围查询天然友好

跳表的底层是有序链表，范围查询（ZRANGEBYSCORE）只需找到起点，然后沿第 0 层顺序遍历。红黑树需要中序遍历，涉及更多的指针跳转。

4.2 并发实现更简单

跳表的插入是局部的——只影响搜索路径上的节点。而红黑树的旋转可能影响大片子树。在复杂的并发场景下，局部修改更容易控制锁粒度。

4.3 实现复杂度更低

跳表的完整实现约 200 行（参考 Redis 的 t_zset.c）。红黑树的实现通常需要 400+ 行。在需要调试或定制行为时，简单的实现是巨大的优势。

4.4 内存开销可接受

每个跳表节点平均有 1.33 个 forward 指针（P=0.25 时）。虽然比红黑树（固定 2 个指针 + 1 bit 颜色）稍多，但在 Redis 的内存场景下完全可接受——尤其是 ZSET 通常用压缩列表存小数据。

五、边界与权衡

5.1 概率性的性能

跳表的查询复杂度是期望O(log n)，而非严格保证。在极端情况下（连续低概率），树可能会"退化"。但 P=0.25 的设定使得最差情况的概率极低（层高超过 32 的概率约为 10^-19）。

5.2 内存 vs 速度

P 越大，平均层数越高，查找越快但内存开销越大。Redis 选择 P=0.25 是在两者之间的最佳平衡点。

5.3 小数据集的退路

Redis 在元素较少时使用压缩列表（ziplist）而非跳表。这是多层级存储策略的体现——不同数据规模用不同结构。

六、总结

Redis 选择跳表而非红黑树，不是因为跳表在理论上更优，而是因为在它的具体场景中（范围查询多、需要排名计算、追求实现简单），跳表是综合最优解。工程选型的本质，是在目标场景的约束条件下，找到权衡最合理的数据结构。

跳表实现与性能剖析：为什么 Redis 选它而不是红黑树