跳表实现与性能剖析为什么 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. 最大层数 322^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当 P0.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 指针P0.25 时。虽然比红黑树固定 2 个指针 1 bit 颜色稍多但在 Redis 的内存场景下完全可接受——尤其是 ZSET 通常用压缩列表存小数据。五、边界与权衡5.1 概率性的性能跳表的查询复杂度是期望O(log n)而非严格保证。在极端情况下连续低概率树可能会退化。但 P0.25 的设定使得最差情况的概率极低层高超过 32 的概率约为 10^-19。5.2 内存 vs 速度P 越大平均层数越高查找越快但内存开销越大。Redis 选择 P0.25 是在两者之间的最佳平衡点。5.3 小数据集的退路Redis 在元素较少时使用压缩列表ziplist而非跳表。这是多层级存储策略的体现——不同数据规模用不同结构。六、总结Redis 选择跳表而非红黑树不是因为跳表在理论上更优而是因为在它的具体场景中范围查询多、需要排名计算、追求实现简单跳表是综合最优解。工程选型的本质是在目标场景的约束条件下找到权衡最合理的数据结构。