跳表实现与 Redis 应用场景：从概率平衡到有序集合的工程实践
一、有序数据的查询困境：为什么平衡树不是唯一选择
在需要维护有序数据并支持快速查找、插入、删除的场景中，红黑树是最经典的数据结构选择。但红黑树有一个工程实现上的致命缺陷：插入和删除时需要通过旋转操作维护平衡，旋转逻辑复杂且容易写错。Linux 内核和 Java TreeMap 中的红黑树实现都曾因旋转逻辑 Bug 导致安全问题。
跳表（Skip List）提供了一种完全不同的思路：用概率替代确定性来维持平衡。不需要复杂的旋转操作，只需要在插入时以一定概率决定节点是否"晋升"到更高层。这种概率性平衡的期望性能与红黑树相当（查找、插入、删除均为 O(log n)），但实现简单得多——一个完整的跳表实现约 150 行代码，而红黑树至少 300 行。
Redis 选择跳表而非红黑树作为有序集合（ZSET）的底层实现，正是看中了跳表的实现简洁性和范围查询优势。在 Redis 的 ZSET 中，跳表不仅支持单点查询，还高效支持 ZRANGEBYSCORE 等范围操作，这是红黑树需要额外处理才能实现的。
二、跳表的核心机制：概率晋升与多层索引
跳表的本质是在有序链表之上建立多层索引。最底层是完整的有序链表，每上一层是下一层的"快速通道"，只保留部分节点。
flowchart LR
subgraph Level 3
A3[HEAD] –> B3[25]
B3 –> C3[NIL]
end
subgraph Level 2
A2[HEAD] –> B2[10]
B2 –> C2[25]
C2 –> D2[40]
D2 –> E2[NIL]
end
subgraph Level 1
A1[HEAD] –> B1[5]
B1 –> C1[10]
C1 –> D1[15]
D1 –> E1[25]
E1 –> F1[30]
F1 –> G1[40]
G1 –> H1[50]
H1 –> I1[NIL]
end
subgraph Level 0 完整链表
A0[HEAD] –> B0[3]
B0 –> C0[5]
C0 –> D0[7]
D0 –> E0[10]
E0 –> F0[15]
F0 –> G0[20]
G0 –> H0[25]
H0 –> I0[30]
I0 –> J0[35]
J0 –> K0[40]
K0 –> L0[45]
L0 –> M0[50]
M0 –> N0[NIL]
end
B3 -.-> B2
B2 -.-> B1
C2 -.-> E1
D2 -.-> G1
查找过程：从最高层的 HEAD 开始，向右查找直到下一个节点的值大于目标值，然后向下进入下一层继续查找。这种"先横移再下移"的策略，类似于二分查找的逐层缩小范围。
晋升概率：每个新插入的节点，以概率 p（通常 0.5）决定是否晋升到上一层。晋升过程持续直到概率失败或达到最大层数。期望层数为 O(log n)，因此查找的期望时间复杂度为 O(log n)。
范围查询优势：跳表在底层是一个有序链表，范围查询只需找到起始节点后沿链表遍历即可。而红黑树的范围查询需要中序遍历，实现更复杂。
三、生产级跳表实现
3.1 核心数据结构
// skiplist.go
// 跳表的 Go 实现，参考 Redis ZSET 的设计
package skiplist
import (
"fmt"
"math/rand"
)
const (
maxLevel = 32 // 最大层数，足以支撑 2^32 个元素
probability = 0.25 // 晋升概率，Redis 使用 0.25 而非 0.5
// 0.25 的概率使得每 4 个节点有 1 个晋升，减少内存占用
)
// Node 跳表节点
type Node struct {
score float64 // 排序分数
member string // 成员标识（Redis ZSET 中的 member）
backward *Node // 后向指针，用于从尾到头遍历和 ZRANGE
level []Level // 每层的前进指针和跨度
}
// Level 每层的指针信息
type Level struct {
forward *Node // 前进指针
span int // 跨度：到下一个节点的距离（用于计算排名）
// span 是 Redis 的关键设计，支持 O(log n) 的 ZRANK 操作
}
// SkipList 跳表
type SkipList struct {
header *Node // 头节点（哨兵节点，不存储数据）
tail *Node // 尾节点指针
length int // 节点数量
level int // 当前最大层数
}
// NewSkipList 创建跳表
func NewSkipList() *SkipList {
return &SkipList{
header: &Node{
level: make([]Level, maxLevel),
},
level: 1,
}
}
// randomLevel 随机生成节点层数
func randomLevel() int {
level := 1
for rand.Float64() < probability && level < maxLevel {
level++
}
return level
}
3.2 插入操作
// insert.go
// 跳表插入操作
func (sl *SkipList) Insert(score float64, member string) *Node {
// update[i] 记录每层中插入位置的前驱节点
update := make([]*Node, maxLevel)
// rank[i] 记录每层前驱节点的排名（用于更新 span）
rank := make([]int, maxLevel)
x := sl.header
for i := sl.level – 1; i >= 0; i– {
// rank 初始化为上一层的排名
if i == sl.level-1 {
rank[i] = 0
} else {
rank[i] = rank[i+1]
}
// 向右查找插入位置
for x.level[i].forward != nil &&
(x.level[i].forward.score < score ||
(x.level[i].forward.score == score &&
x.level[i].forward.member < member)) {
rank[i] += x.level[i].span
x = x.level[i].forward
}
update[i] = x
}
// 随机生成新节点的层数
level := randomLevel()
if level > sl.level {
// 新节点层数超过当前最大层数，初始化高层
for i := sl.level; i < level; i++ {
rank[i] = 0
update[i] = sl.header
update[i].level[i].span = sl.length
}
sl.level = level
}
// 创建新节点
x = &Node{
score: score,
member: member,
level: make([]Level, level),
}
// 更新每层的前进指针和跨度
for i := 0; i < level; i++ {
x.level[i].forward = update[i].level[i].forward
update[i].level[i].forward = x
// 更新跨度：新节点插入后，前驱节点的跨度需要重新计算
x.level[i].span = update[i].level[i].span – (rank[0] – rank[i])
update[i].level[i].span = (rank[0] – rank[i]) + 1
}
// 更新未触及层的跨度（新节点层数 < 最大层数时）
for i := level; i < sl.level; i++ {
update[i].level[i].span++
}
// 设置后向指针
if update[0] != sl.header {
x.backward = update[0]
}
if x.level[0].forward != nil {
x.level[0].forward.backward = x
} else {
sl.tail = x
}
sl.length++
return x
}
3.3 查找与范围查询
// query.go
// 跳表查找与范围查询
// GetRank 获取成员的排名（0-based）
// 利用 span 字段，O(log n) 时间复杂度
func (sl *SkipList) GetRank(score float64, member string) int {
x := sl.header
rank := 0
for i := sl.level – 1; i >= 0; i– {
for x.level[i].forward != nil &&
(x.level[i].forward.score < score ||
(x.level[i].forward.score == score &&
x.level[i].forward.member <= member)) {
rank += x.level[i].span
x = x.level[i].forward
}
// 精确匹配检查
if x.member == member && x.score == score {
return rank – 1 // 转为 0-based
}
}
return -1 // 未找到
}
// RangeByScore 范围查询：返回分数在 [min, max] 之间的所有成员
// 这是 Redis ZRANGEBYSCORE 的核心实现
func (sl *SkipList) RangeByScore(min, max float64) []*Node {
var result []*Node
// 第一步：找到第一个 score >= min 的节点
x := sl.header
for i := sl.level – 1; i >= 0; i– {
for x.level[i].forward != nil && x.level[i].forward.score < min {
x = x.level[i].forward
}
}
x = x.level[0].forward // 移动到第一个 >= min 的节点
// 第二步：沿底层链表遍历，收集 score <= max 的节点
for x != nil && x.score <= max {
result = append(result, x)
x = x.level[0].forward
}
return result
}
四、架构权衡与适用边界
跳表 vs 红黑树的选择。跳表的优势在于实现简单、范围查询高效、并发友好（锁粒度更细）。红黑树的优势在于确定性性能（最坏情况 O(log n)）和更低的内存开销（跳表每个节点需要额外存储多层指针）。Redis 选择跳表的核心原因是范围查询和排名操作的高效实现。
晋升概率的影响。概率 p=0.5 时，期望层数最少但内存开销最大；p=0.25 时，内存开销降低约 50%，但查找路径略长。Redis 使用 p=0.25，在内存和性能之间取得了较好的平衡。
并发安全的实现。跳表的插入只影响局部节点，比红黑树的旋转操作更容易做细粒度锁。Java 的 ConcurrentSkipListMap 使用无锁 CAS 操作实现并发安全，性能优于 ConcurrentSkipListSet。
适用边界：跳表适用于需要有序数据、频繁范围查询、且对实现复杂度敏感的场景。Redis ZSET 是最典型的应用。对于不需要范围查询的纯查找场景（如 Set），哈希表更高效。对于内存极度受限的嵌入式场景，跳表的多层指针开销可能不可接受。
五、总结
跳表用概率平衡替代确定性平衡，在期望 O(log n) 的性能下大幅降低了实现复杂度。核心机制是多层索引 + 概率晋升，Redis 使用 0.25 的晋升概率在内存和性能间取得平衡。跳表在 Redis ZSET 中的应用，关键在于 span 字段支持 O(log n) 的排名计算，以及底层有序链表支持高效的范围查询。工程选型时，跳表适合需要范围查询和排名操作的场景，纯查找场景哈希表更优，内存敏感场景需要权衡多层指针的开销。
