跳表（Skip List）：简单高效的有序数据结构

1. 跳表的起源与动机

1.1 历史背景

跳表由William Pugh于1990年在论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中提出。Pugh当时面临一个经典问题：

如何在保持链表简单性的同时，获得接近二叉搜索树的查询效率？

传统解决方案要么复杂（AVL树、红黑树的旋转平衡），要么牺牲有序性（哈希表）。跳表提供了一个优雅的折中：概率性平衡代替强制性平衡。

1.2 设计哲学

数据结构	平衡策略	复杂度	实现难度
有序链表	无	查询O(n)	极简单
二叉搜索树	无	查询O(n)（退化）	简单
AVL树	强制旋转平衡	查询O(log n)	复杂
跳表	概率性分层	期望O(log n)	简单

跳表的核心洞察：随机化可以替代复杂的再平衡操作。

2. 核心思想与直观理解

2.1 从链表到跳表

想象一条高速公路（链表）和多条快速路（索引层）：

markdown
 体验AI代码助手
 代码解读
复制代码
普通公路（Level 0）：每1公里一个出口
    ├───●───●───●───●───●───●───●───●───●───●───●───●───●───●───●
       1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

一级快速路（Level 1）：每2公里一个出口
    ├───●───────────●───────────●───────────●───────────●
       1           3           5           7           9

二级快速路（Level 2）：每4公里一个出口
    ├───●───────────────────────●───────────────────────●
       1                       5                       9

三级快速路（Level 3）：每8公里一个出口
    ├───●───────────────────────────────────────────────●
       1                                               9

从A地到B地，你先走高级快速路，接近目的地时逐级下降，最终到达。

2.2 关键特性

特性1：有序性

底层（Level 0）是有序链表，所有数据按序排列

特性2：索引分层

每个节点随机拥有1~MAX_LEVEL层指针
上层节点是下层节点的"快速通道"

特性3：概率分布

节点出现在第k层的概率为 p^k（通常p=0.5）
50%的节点有1层，25%有2层，12.5%有3层...

yaml
 体验AI代码助手
 代码解读
复制代码
节点层数分布（p=0.5）：
Level 0: ████████████████████████████████████████ 100%
Level 1: ████████████████████░░░░░░░░░░░░░░░░░░░░  50%
Level 2: ██████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  25%
Level 3: █████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  12.5%
Level 4: ██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░   6.25%

3. 数据结构详解

3.1 节点结构

python
 体验AI代码助手
 代码解读
复制代码
from typing import List, Optional
import random

class SkipListNode:
    """
    跳表节点
    
    每个节点包含：
    - key: 排序键（可为None表示头节点）
    - value: 存储的值
    - forward: 各层的前向指针数组
    """
    def __init__(self, key: Optional[int], value: Optional[any], level: int):
        self.key = key
        self.value = value
        # forward[i] 表示第i层的下一个节点
        self.forward: List[Optional['SkipListNode']] = [None] * level
    
    def __repr__(self):
        return f"Node({self.key}: {self.value}, levels={len(self.forward)})"

3.2 跳表结构

python
 体验AI代码助手
 代码解读
复制代码
class SkipList:
    """
    跳表实现
    
    参数：
    - max_level: 最大层数，决定最高索引层（通常16足够处理2^16个元素）
    - p: 晋升概率，控制层数分布（通常0.5）
    """
    def __init__(self, max_level: int = 16, p: float = 0.5):
        self.max_level = max_level
        self.p = p
        self.level = 0  # 当前实际使用的最高层数
        
        # 头节点，包含所有层的起始指针
        self.head = SkipListNode(None, None, max_level)
        
        # 统计信息
        self.size = 0
    
    def _random_level(self) -> int:
        """
        随机生成节点层数
        
        算法：每层以概率p晋升，直到不晋升或达到max_level
        
        数学期望：E[level] = 1/(1-p) - 1
        当p=0.5时，期望层数为1
        """
        level = 1
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level

3.3 可视化表示

yaml
 体验AI代码助手
 代码解读
复制代码
跳表示例（插入 3, 6, 7, 9, 12, 17, 19, 21, 25, 26）：

Level 3:  HEAD ──────────────────────────────────────────────→ 25
Level 2:  HEAD ─────────────────────────────→ 17 ─────────────→ 25 ─────────────→ 26
Level 1:  HEAD ───────────→ 6 ───────────→ 17 ───────────→ 25 ───────────→ 26
Level 0:  HEAD → 3 → 6 → 7 → 9 → 12 → 17 → 19 → 21 → 25 → 26

查找路径示例（查找 19）：
1. L3: HEAD → 25 (25>19，下降)
2. L2: HEAD → 17 (17<19，前进) → 25 (25>19，下降)
3. L1: 17 → 25 (25>19，下降)
4. L0: 17 → 19 (找到！)

实际访问节点：HEAD(L3) → HEAD(L2) → 17(L2) → 17(L1) → 17(L0) → 19(L0)
共6步，而普通链表需要7步

4. 核心操作实现

4.1 查询操作（Search）

算法思路：从最高层开始，在当前层尽可能向右移动，遇到更大的值就下降一层。

python
 体验AI代码助手
 代码解读
复制代码
def search(self, key: int) -> Optional[any]:
    """
    查询操作
    
    步骤：
    1. 从当前最高层(level)开始
    2. 在当前层向右移动，直到下一个节点key >= target
    3. 下降到下一层，重复步骤2
    4. 到达Level 0后，检查下一个节点是否等于target
    
    时间复杂度：O(log n) 期望
    """
    current = self.head
    
    # 从高层到低层
    for i in range(self.level - 1, -1, -1):
        # 在当前层尽可能向右走
        while (current.forward[i] is not None and 
               current.forward[i].key < key):
            current = current.forward[i]
    
    # 现在current是小于key的最大节点，检查下一个
    current = current.forward[0]
    
    if current is not None and current.key == key:
        return current.value
    return None

查询过程可视化：

ini
 体验AI代码助手
 代码解读
复制代码
查找 key = 15

Level 2:  1 ──────────────→ 9 ──────────────→ 17
          ↑                 ↑
          │                 └─ next=17 > 15, 下降
          └─ current

Level 1:  1 ──────→ 5 ──────→ 9 ──────→ 13 ──────→ 17
                            ↑           ↑
                            │           └─ next=17 > 15, 下降
                            └─ current (从L2下来)

Level 0:  1 → 3 → 5 → 7 → 9 → 11 → 13 →→ 17
                                    ↑
                                    └─ next=15 == target, 找到！

访问节点数：3层 × 少量节点 = O(log n)

4.2 插入操作（Insert）

算法思路：

找到每一层需要插入位置的前驱节点（update数组）
随机决定新节点层数
在各层插入新节点，调整指针

python
 体验AI代码助手
 代码解读
复制代码
def insert(self, key: int, value: any) -> bool:
    """
    插入操作
    
    步骤：
    1. 找到每一层的前驱节点（update数组）
    2. 如果key已存在，更新value
    3. 随机决定新节点层数
    4. 如果新层数>当前层数，更新head的forward和level
    5. 创建新节点，在各层插入
    
    时间复杂度：O(log n) 期望
    """
    # update[i] 表示第i层需要更新的节点（即新节点的前驱）
    update: List[Optional[SkipListNode]] = [None] * self.max_level
    current = self.head
    
    # 第一步：找到每一层的前驱节点
    for i in range(self.level - 1, -1, -1):
        while (current.forward[i] is not None and 
               current.forward[i].key < key):
            current = current.forward[i]
        update[i] = current
    
    # 移动到Level 0的下一个节点
    current = current.forward[0]
    
    # Key已存在，更新value
    if current is not None and current.key == key:
        current.value = value
        return False  # 未插入新节点
    
    # 第二步：随机决定新节点层数
    new_level = self._random_level()
    
    # 如果新层数超过当前层数，需要更新更高层的update为head
    if new_level > self.level:
        for i in range(self.level, new_level):
            update[i] = self.head
        self.level = new_level
    
    # 第三步：创建新节点
    new_node = SkipListNode(key, value, new_level)
    
    # 第四步：在各层插入（调整指针）
    for i in range(new_level):
        new_node.forward[i] = update[i].forward[i]
        update[i].forward[i] = new_node
    
    self.size += 1
    return True

插入过程可视化：

yaml
 体验AI代码助手
 代码解读
复制代码
插入 key=10, value="X"（随机层数=2）

插入前：
Level 2:  HEAD ─────────────────────────→ 17
Level 1:  HEAD ───────────→ 9 ─────────→ 17
Level 0:  HEAD → 3 → 6 → 9 → 12 → 17

Step 1: 找到update数组
  L2: HEAD (因为17>10)
  L1: 9 (因为9<10<17)
  L0: 9 (因为9<10<12)

Step 2: 随机层数=2，需要更新L0,L1

Step 3: 插入（调整指针）
Level 2:  HEAD ─────────────────────────→ 17  (不变)
Level 1:  HEAD ───────────→ 9 ─────→ 17
                              ↓
                            next(17)
Level 0:  HEAD → 3 → 6 → 9 ────→ 12 → 17
                          ↓
                        next(12)

新节点10的forward: [12, 17, None, None, ...]
9的forward[0]从12改为10，forward[1]从17改为10

4.3 删除操作（Delete）

python
 体验AI代码助手
 代码解读
复制代码
def delete(self, key: int) -> bool:
    """
    删除操作
    
    步骤：
    1. 找到每一层的前驱节点
    2. 如果目标不存在，返回False
    3. 在各层删除目标节点（调整指针跳过目标）
    4. 更新当前层数（去掉空的顶层）
    
    时间复杂度：O(log n) 期望
    """
    update: List[Optional[SkipListNode]] = [None] * self.max_level
    current = self.head
    
    # 找到每一层的前驱
    for i in range(self.level - 1, -1, -1):
        while (current.forward[i] is not None and 
               current.forward[i].key < key):
            current = current.forward[i]
        update[i] = current
    
    # 目标节点
    target = current.forward[0]
    
    # 不存在
    if target is None or target.key != key:
        return False
    
    # 在各层删除（调整指针）
    for i in range(self.level):
        if update[i].forward[i] != target:
            break  # 更高层没有该节点
        update[i].forward[i] = target.forward[i]
    
    # 更新当前层数
    while (self.level > 0 and 
           self.head.forward[self.level - 1] is None):
        self.level -= 1
    
    self.size -= 1
    return True

4.4 范围查询（Range Query）

跳表的优势之一，哈希表无法高效支持：

python
 体验AI代码助手
 代码解读
复制代码
def range_query(self, start: int, end: int) -> List[tuple]:
    """
    范围查询：返回key在[start, end]内的所有(key, value)
    
    时间复杂度：O(log n + k)，k为结果数量
    """
    result = []
    
    # 找到start位置
    current = self.head
    for i in range(self.level - 1, -1, -1):
        while (current.forward[i] is not None and 
               current.forward[i].key < start):
            current = current.forward[i]
    
    # 从start开始遍历Level 0
    current = current.forward[0]
    while current is not None and current.key <= end:
        result.append((current.key, current.value))
        current = current.forward[0]
    
    return result

5. 复杂度分析

5.1 数学推导

节点层数期望：

第k层节点数期望：n × p^k
当 p=0.5 时，第k层约有 n/2^k 个节点

查询复杂度：

每层访问的节点数期望：2（因为节点密度减半）
总层数期望：log_{1/p}(n)
总复杂度：O(log n)

空间复杂度：

每个节点期望层数：1/(1-p)
当p=0.5时，期望2层
总空间：O(n)

5.2 概率分析表（p=0.5, n=1,000,000）

层数	期望节点数	查询时访问概率
1	500,000	100%
2	250,000	~100%
3	125,000	~50%
4	62,500	~25%
5	31,250	~12%
...	...	...
20	<1	极低

5.3 与理论最优的比较

操作	跳表期望	平衡树	有序数组
查询	O(log n)	O(log n)	O(log n)
插入	O(log n)	O(log n)	O(n)
删除	O(log n)	O(log n)	O(n)
范围查询	O(log n + k)	O(log n + k)	O(log n + k)
实现难度	简单	复杂	中等

6. 与其他数据结构的对比

6.1 详细对比表

特性	跳表	红黑树	AVL树	B+树	哈希表
有序遍历	✅ O(n)	✅ O(n)	✅ O(n)	✅ O(n)	❌ O(n log n)
最值查询	✅ O(1)	✅ O(log n)	✅ O(log n)	✅ O(log n)	❌ O(n)
范围查询	✅ O(log n+k)	✅ O(log n+k)	✅ O(log n+k)	✅ O(log n+k)	❌ O(n)
第k大元素	✅ O(log n)	✅ O(log n)*	✅ O(log n)*	✅ O(log n)	❌ O(n)
实现复杂度	低	高	高	中	低
常数因子	较小	较小	较小	较大	最小
锁粒度（并发）	细	粗	粗	中	中

*需要维护子树大小

6.2 为什么选择跳表？

优势场景：

需要有序性 + 频繁修改：跳表优于有序数组
实现简单：跳表代码量约为红黑树的1/5
并发性能好：细粒度锁，不同层的操作可并行
范围查询友好：天然支持，无需额外结构

劣势场景：

极致性能要求：哈希表O(1)更快（但无序）
内存极度紧张：链表结构有指针开销
需要持久化：B+树更适合磁盘存储

7. 实际应用场景

7.1 Redis 中的跳表

Redis 的 Sorted Set（ZSET） 底层使用跳表 + 哈希表： http://hebkssfp.mpmpc.cn/ http://njkssfp.mpmpc.cn/ http://szkssfp.mpmpc.cn/ http://hzkssfp.mpmpc.cn/ http://hfksssfp.mpmpc.cn/ http://xmkssfp.mpmpc.cn/ http://fzkssfp.mpmpc.cn/ http://nckssfp.mpmpc.cn/ http://jnkssfp.mpmpc.cn/ http://qdkssfp.mpmpc.cn/ http://zzkssfp.mpmpc.cn/ http://whkssfp.mpmpc.cn/ http://cskssfp.mpmpc.cn/

c
 体验AI代码助手
 代码解读
复制代码
// Redis 跳表节点定义（zskiplistNode）
typedef struct zskiplistNode {
    sds ele;                    // 成员对象
    double score;               // 分数（排序键）
    struct zskiplistNode *backward;  // 后退指针（用于倒序遍历）
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;      // 到下一个节点的跨度（用于RANK查询）
    } level[];
} zskiplistNode;

Redis选择跳表的原因：

实现简单，代码量少（vs 红黑树）
范围查询天然支持（ZRange/ZRevRange）
有序遍历效率高
方便实现ZRANK（通过span字段）

7.2 LevelDB/RocksDB 中的跳表

内存中的 MemTable 使用跳表作为默认实现：

markdown
 体验AI代码助手
 代码解读
复制代码
写入流程：
1. 写入WAL日志（持久化）
2. 插入跳表（MemTable）
3. MemTable满后，转为Immutable MemTable
4. 后台线程将Immutable MemTable写入SSTable（磁盘）

跳表的优势：

写入无需磁盘IO，纯内存操作
有序性保证后续SSTable合并高效
并发读写性能好（MVCC）

7.3 其他应用

系统	用途	特点
Lucene	倒排索引合并	多路归并优化
MemSQL	内存索引	并发控制
Cassandra	内存表	写优化
HBase	MemStore	类似LevelDB

8. 高级主题

8.1 并发跳表（Lock-Free）

使用 CAS（Compare-And-Swap） 实现无锁并发：

python
 体验AI代码助手
 代码解读
复制代码
import threading
from typing import Atomic  # 伪代码，实际需使用特定库

class ConcurrentSkipList:
    """
    无锁并发跳表（概念演示）
    
    核心思想：
    1. 使用CAS操作更新指针
    2. 标记删除（逻辑删除）避免ABA问题
    3. 每层独立加锁或使用原子操作
    """
    def __init__(self):
        self.head = SkipListNode(None, None, MAX_LEVEL)
        self.locks = [threading.Lock() for _ in range(MAX_LEVEL)]
    
    def concurrent_insert(self, key, value):
        # 1. 找到位置（无锁遍历）
        # 2. 从底层开始，逐层CAS插入
        # 3. 如果CAS失败，重试
        pass  # 实际实现较复杂

8.2 优化策略

1. 概率p的选择

p=0.5：平衡空间和速度（常用）
p=0.25：更少指针，更省空间，查询略慢
p=0.75：更多指针，更快查询，更费空间

2. 确定性跳表（Deterministic Skip List）

不随机，按固定规则分层（如每2^k个节点升一层）
查询复杂度严格O(log n)，但插入可能需要调整多个节点

3. 跳表变种

变种	特点	应用
1-2-3跳表	确定性分层	教学演示
指数跳表	节点按指数分布	特定负载优化
分数级联	加速查询	计算几何

8.3 完整优化实现

python
 体验AI代码助手
 代码解读
复制代码
class OptimizedSkipList:
    """
    生产级跳表优化
    """
    def __init__(self, max_level: int = 32, p: float = 0.25):
        self.max_level = max_level
        self.p = p
        self.level = 1
        self.head = self._create_node(None, None, max_level)
        self._size = 0
        
        # 预分配update数组，避免重复创建
        self._update_buffer = [None] * max_level
    
    def _create_node(self, key, value, level):
        # 使用对象池或__slots__减少内存开销
        node = object.__new__(SkipListNode)
        node.key = key
        node.value = value
        node.forward = [None] * level
        return node
    
    def __len__(self):
        return self._size
    
    def iter_range(self, start, end):
        """生成器实现的范围查询，节省内存"""
        node = self._find_ge(start)
        while node and node.key <= end:
            yield (node.key, node.value)
            node = node.forward[0]

总结

跳表是一种简单、高效、优雅的概率性数据结构，它通过随机分层实现了对数级查询复杂度，同时保持了链表的简洁性。其核心优势在于：

实现简单：无需复杂的旋转平衡逻辑
性能优异：期望O(log n)的查询/插入/删除
范围友好：天然支持有序遍历和范围查询
并发适配：细粒度锁或无锁实现可行

在现代系统中，跳表广泛应用于内存数据库（Redis、LevelDB）的索引实现，是有序数据结构的重要选择。

参考实现代码（完整可运行版本）：

点击查看完整代码

目录