跳表 (Skip List) - 数据结构深度解析

📚概述与定义

跳表（Skip List）由 William Pugh 于 1990 年发明，通过在有序链表上增加多级索引层，将查找复杂度从 O(n) 降低到 O(log n)。

有序存储 O(log n) 查找概率平衡支持范围查询

设计动机

有序链表插入删除 O(1)，但查找需 O(n)。平衡树查找高效但实现复杂。跳表采用空间换时间策略，通过随机化多层索引，在保持实现简单的同时达到平衡树性能。

核心思想 如同高速公路快车道可跳过部分出口直达远处，跳表通过多层“快速通道”（索引层）快速跳过大量节点。

🏗️结构原理

跳表由多层链表组成，最底层（Level 0）包含所有元素，每向上一层节点数约减半，形成金字塔结构。

层级结构示意

节点结构

每个跳表节点包含以下信息：

key：节点存储的键值（用于排序和查找）
value：节点存储的实际数据（可选）
forward[]：指针数组，forward[i] 指向第 i 层的下一个节点
level：节点的层高（随机生成）

层高随机化

节点层高通过抛硬币随机决定：“正面”则层数加一，直到“反面”或达最大层。概率 p 通常取 0.5 或 0.25。

function randomLevel():
    level = 1
    while random() < p and level < MAX_LEVEL:
        level = level + 1
    return level

概率分析 当 p = 0.5 时，平均每个节点出现在 2 层中，跳表平均占用约 2n 个指针空间，复杂度 O(n)。

⚙️核心操作

查找操作 (Search)

从最高层开始，逐层向右下方搜索，直到找到目标或到达最底层末尾。

从头节点的最高层开始

若当前层下一节点的 key 小于目标，则向右移动

若当前层下一节点的 key 大于等于目标，则下降一层

重复步骤 2-3，直到找到目标或到达 Level 0 末尾

function search(key):
    x = header
    // 从最高层向下搜索
    for i = level downto 0:
        while x.forward[i].key < key:
            x = x.forward[i]    // 向右移动
        // 下降到下一层
    x = x.forward[0]
    if x.key == key:
        return x.value
    return null

插入操作 (Insert)

先查找插入位置，记录每层的前驱节点，然后随机生成新节点层高，最后在各层插入。

function insert(key, value):
    update[] = new array of MAX_LEVEL    // 记录各层前驱
    x = header
    // 从高层向低层搜索插入位置
    for i = level downto 0:
        while x.forward[i].key < key:
            x = x.forward[i]
        update[i] = x
    // 生成随机层高
    newLevel = randomLevel()
    if newLevel > level:
        for i = level + 1 to newLevel:
            update[i] = header
        level = newLevel
    // 创建新节点并插入
    newNode = createNode(key, value, newLevel)
    for i = 0 to newLevel:
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode

删除操作 (Delete)

类似插入，先找到目标节点及各层前驱，然后在各层删除该节点的链接。

function delete(key):
    update[] = new array of MAX_LEVEL
    x = header
    // 搜索并记录前驱
    for i = level downto 0:
        while x.forward[i].key < key:
            x = x.forward[i]
        update[i] = x
    x = x.forward[0]
    if x.key == key:
        // 逐层删除链接
        for i = 0 to level:
            if update[i].forward[i] != x:
                break
            update[i].forward[i] = x.forward[i]
        // 调整跳表层高
        while level > 0 and header.forward[level] == NIL:
            level = level - 1

📊复杂度分析

操作	平均时间复杂度	最坏时间复杂度	空间复杂度
查找 (Search)	O(log n)	O(n)	O(1)
插入 (Insert)	O(log n)	O(n)	O(log n)
删除 (Delete)	O(log n)	O(n)	O(1)
范围查询	O(log n + k)	O(n + k)	O(k)

为什么平均 O(log n)？ 每层节点数约为下层 1/p，平均层数 log_1/pn，每层平均搜索 1/p 步，总步数 O(log n)。

空间开销

设 p = 0.5，节点平均指针数 2，总空间 O(n)。若 p = 0.25，平均约 1.33 个指针，空间更省。

优缺点总结

优点

实现简单，比平衡树代码量少 50% 以上
支持高效的范围查询，天然有序遍历
并发友好，局部修改不影响整体结构
平均性能与平衡树相当
插入删除无需全局重平衡

缺点

最坏情况 O(n)，无严格性能保证
空间开销略高（约 2n 指针）
缓存局部性较差，不适合磁盘存储
随机数生成有一定开销

🔒并发跳表

跳表结构使其天然适合并发。插入删除只影响局部节点，无需全局重平衡。

并发实现要点

无锁查找：查找操作只读，无需加锁，可完全并发执行
细粒度锁：插入/删除时仅锁定受影响的相邻节点
CAS 操作：使用原子操作实现无锁链表修改
标记删除：先标记节点为已删除，再物理移除

Java ConcurrentSkipListMap JDK 提供的 ConcurrentSkipListMap 采用无锁算法，使用标记节点和 CAS 操作确保线程安全，读操作完全无锁。

跳表变体

确定性跳表：使用确定性规则而非随机数决定层高，保证最坏 O(log n)
索引跳表：在节点中维护 span 信息，支持 O(log n) 的按位置访问
带权跳表：节点存储子树大小，支持快速排名查询

⚖️与其他数据结构对比

特性	跳表	红黑树	AVL 树	B+ 树
查找复杂度	O(log n) 平均	O(log n) 最坏	O(log n) 最坏	O(log n) 最坏
实现复杂度	简单	复杂	中等	复杂
范围查询	高效	需中序遍历	需中序遍历	高效
并发支持	容易	困难	困难	中等
内存局部性	较差	较好	较好	优秀
空间开销	约 2n 指针	3n 指针 + 颜色	3n 指针 + 高度	变长指针数组

何时选跳表？ 需简单实现、高效范围查询或良好并发性能时，跳表是优秀选择。Redis Sorted Set 正是基于跳表实现。

💻代码实现 (Java)

import java.util.Random;

public class SkipList<K extends Comparable<K>, V> {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    
    private final Node<K, V> header;
    private int level;
    private final Random random;
    
    // 节点定义
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V>[] forward;
        
        @SuppressWarnings("unchecked")
        Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            this.forward = new Node[level + 1];
        }
    }
    
    public SkipList() {
        header = new Node<>(null, null, MAX_LEVEL);
        level = 0;
        random = new Random();
    }
    
    // 随机层高生成
    private int randomLevel() {
        int lvl = 0;
        while (random.nextDouble() < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }
    
    // 查找操作
    public V search(K key) {
        Node<K, V> current = header;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key.compareTo(key) < 0) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        if (current != null && current.key.compareTo(key) == 0) {
            return current.value;
        }
        return null;
    }
    
    // 插入操作
    @SuppressWarnings("unchecked")
    public void insert(K key, V value) {
        Node<K, V>[] update = new Node[MAX_LEVEL + 1];
        Node<K, V> current = header;
        
        // 找到各层前驱
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key.compareTo(key) < 0) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        
        current = current.forward[0];
        
        // 更新已存在的 key
        if (current != null && current.key.compareTo(key) == 0) {
            current.value = value;
            return;
        }
        
        // 创建新节点
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = header;
            }
            level = newLevel;
        }
        
        Node<K, V> newNode = new Node<>(key, value, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }
    
    // 删除操作
    @SuppressWarnings("unchecked")
    public boolean delete(K key) {
        Node<K, V>[] update = new Node[MAX_LEVEL + 1];
        Node<K, V> current = header;
        
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key.compareTo(key) < 0) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        
        current = current.forward[0];
        
        if (current != null && current.key.compareTo(key) == 0) {
            for (int i = 0; i <= level; i++) {
                if (update[i].forward[i] != current) break;
                update[i].forward[i] = current.forward[i];
            }
            while (level > 0 && header.forward[level] == null) {
                level--;
            }
            return true;
        }
        return false;
    }
}

🚀实际应用场景

Redis Sorted Set

Redis 有序集合底层使用跳表实现 ZRANGE、ZRANK 等命令，支持高效的范围查询和排名操作。

LevelDB / RocksDB

Google 的 LevelDB 及其衍生版本使用跳表作为 MemTable 的数据结构，支持高效写入。

并发容器

Java 的 ConcurrentSkipListMap/Set 基于跳表实现，提供线程安全的有序 Map/Set。

时序数据库

InfluxDB 等时序数据库使用跳表进行时间戳索引，支持快速的时间范围查询。

内存数据库索引

Apache Lucene 使用跳表加速倒排索引的合并与遍历操作。

区块链

部分区块链实现使用跳表管理账户状态，支持快速的状态查询与验证。

🎮在线演示工具

在下方输入整数值，体验跳表的插入、查找、删除操作：

跳表操作演示

正在处理中，请稍候...

演示说明 本演示为纯前端实现，可直接在浏览器中体验跳表的插入、查找、删除操作。节点层高通过随机算法生成（p=0.5）。

📖参考资料

Pugh, W. (1990). Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676.
Redis 源码 - t_zset.c 跳表实现
Java ConcurrentSkipListMap 源码分析
LevelDB 源码 - db/skiplist.h
《算法导论》第三版 - 随机化数据结构