跳表（Skip List）技术详解：结构、操作与应用

1. 引言​

在数据结构领域，高效的查找、插入和删除操作是衡量数据结构性能的核心指标。平衡二叉搜索树（如红黑树、AVL 树）和哈希表虽能提供较好性能，但存在实现复杂或无法支持有序遍历等局限。跳表（Skip List） 作为一种概率性数据结构，通过 “分层索引” 的思想，在保证平均 O (log n) 时间复杂度的同时，大幅降低了实现难度，且天然支持有序数据的高效操作，广泛应用于 Redis、LevelDB 等高性能存储系统中。​

2. 跳表的核心概念与结构原理​

2.1 定义​

跳表是一种有序链表的扩展结构，通过在原始链表（最底层）之上建立多层 “索引链表”，实现快速定位。每一层索引链表中的节点，都是其下一层节点的子集，且严格保持与原始链表一致的有序性（通常为升序）。​

2.2 核心术语​

• 底层链表（Base Layer）：存储全部数据的有序链表，是跳表的基础。​

• 索引层（Index Layer）：位于底层之上的分层结构，用于加速查找，层数越多，查找效率越高（但空间开销也越大）。​

• 节点（Node）：存储数据（key-value）和指向各层下一个节点的指针（forward 数组），forward [i] 表示第 i 层中当前节点的后继节点。​

• 层高（Level）：节点在跳表中的最大层级（如一个节点同时存在于第 0 层和第 1 层，则其层高为 2），跳表的整体高度由最高层节点的层高决定。​

• 概率生成器：用于随机生成新节点的层高，通常遵循 “几何分布”（如 50% 概率层数 + 1），保证跳表结构的平衡性。​

2.3 结构示意图​

以有序数据[1,3,5,7,9,11]为例，跳表结构如下（层数从下到上为 0~2）：​

• 第 2 层（顶层索引）：1 → 5 → 11​

• 第 1 层（中层索引）：1 → 3 → 7 → 11​

• 第 0 层（底层链表）：1 → 3 → 5 → 7 → 9 → 11​

可见，上层索引通过 “跳过部分节点” 减少了查找时的比较次数，本质是用空间换时间。

3. 跳表的核心操作（增删查）​

跳表的所有操作均围绕 “分层定位” 展开，核心是先通过上层索引快速缩小查找范围，再到下层精确匹配。以下操作均基于 “升序跳表”，且假设 key 不重复（若支持重复 key，需调整相等时的处理逻辑）。​

3.1 查找操作（Search）​

3.1.1 核心思路​

从跳表的顶层索引开始，沿当前层向前遍历：​

• 若下一个节点的 key 小于目标 key，继续向前；​

• 若下一个节点的 key 大于目标 key，切换到下一层（降低一层）；​

• 重复上述过程，直到到达第 0 层；​

• 在第 0 层中，若找到 key 相等的节点，返回该节点的 value；否则返回 “不存在”。​

3.1.2 步骤示例（查找 key=7）​

1. 从顶层（第 2 层）开始，当前节点为 1，下一个节点为 5（5<7），向前移动到 5；​

1. 第 2 层中 5 的下一个节点为 11（11>7），切换到第 1 层；​

1. 第 1 层中 5 的下一个节点为 7（7 = 目标 key），切换到第 0 层；​

1. 第 0 层中确认 7 存在，返回其 value。​

3.1.3 伪代码​

function search(targetKey):​

    current = 跳表的头节点（head）​

    # 从顶层向下遍历​

    for i from 跳表最大高度-1 down to 0:​

    # 沿当前层向前，直到下一个节点key>targetKey​

    while current.forward[i] != null and current.forward[i].key < targetKey:​

        current = current.forward[i]​

        # 到达第0层，检查下一个节点是否为目标​

        current = current.forward[0]​

    if current != null and current.key == targetKey:​

        return current.value​

    else:​

        return null​

​

3.1.4 时间复杂度​

• 平均情况：O (log n)（每层遍历的节点数为常数，总层数为 log n）；​

• 最坏情况：O (n)（极端情况下所有节点层高为 1，退化为普通链表），但概率极低（可忽略）。​
   

3.2 插入操作（Insert）​

插入操作的核心是 “先找到插入位置，再随机生成新节点的层高，最后更新各层指针”。​

3.2.1 核心步骤​

1. 定位插入前驱：与查找类似，从顶层向下遍历，记录每一层中 “最后一个 key 小于目标 key” 的节点（记为update[i]，即第 i 层中插入位置的前驱节点）；​

1. 随机生成层高：通过概率生成器确定新节点的层高（记为newLevel），若newLevel超过当前跳表的最大高度，更新跳表最大高度，并补充update数组中高层的前驱节点（为头节点）；​

1. 创建新节点：新节点的forward数组长度为newLevel，初始值均为 null；​

1. 更新各层指针：对每一层i（0~newLevel-1），将newNode.forward[i]指向update[i].forward[i]，再将update[i].forward[i]指向newNode。​

3.2.2 关键：层高生成策略​

为保证跳表的平衡性，新节点的层高需遵循几何分布（即层数越高，概率越低）。常见策略：​

• 初始层高为 1；​

• 每次以 50% 的概率将层高 + 1，直到概率试验失败或达到预设最大层高（避免层高过高导致空间浪费）。​

生成层高的伪代码​

function randomLevel():
    level = 1
    # 50%概率提升层数，最大层高限制为MAX_LEVEL（如32）
    while random() < 0.5 and level < MAX_LEVEL:
        level += 1
    return level

3.2.3 伪代码​

function insert(newKey, newValue):
    # update数组存储各层插入位置的前驱节点
    update = array of size MAX_LEVEL
    current = 跳表的头节点（head）
    
    # 步骤1：定位各层前驱节点
    for i from 跳表最大高度-1 down to 0:
        while current.forward[i] != null and current.forward[i].key < newKey:
            current = current.forward[i]
        update[i] = current  # 记录第i层的前驱
    
    # 检查是否已存在（避免重复插入）
    current = current.forward[0]
    if current != null and current.key == newKey:
        current.value = newValue  # 若支持覆盖，更新value
        return
    
    # 步骤2：随机生成新节点的层高
    newLevel = randomLevel()
    
    # 若新层高超过当前最大高度，补充update数组高层的前驱为头节点
    if newLevel > 跳表当前最大高度:
        for i from 跳表当前最大高度 to newLevel-1:
            update[i] = head
        跳表当前最大高度 = newLevel
    
    # 步骤3：创建新节点并更新指针
    newNode = new Node(newKey, newValue, newLevel)
    for i from 0 to newLevel-1:
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode

3.3 删除操作（Delete）​

删除操作的核心是 “先找到待删除节点的各层前驱，再删除节点并修复指针”。​

3.3.1 核心步骤​

1. 定位前驱节点：与插入类似，遍历各层，记录待删除节点的前驱节点（update[i]）；​

1. 检查节点是否存在：在第 0 层确认待删除节点存在（若不存在，直接返回）；​

1. 删除节点并修复指针：对每一层i（0~ 待删除节点的层高 - 1），将update[i].forward[i]指向待删除节点的下一个节点（delNode.forward[i]）；​

1. 调整跳表最大高度：若删除后顶层索引无节点（头节点的 forward 为 null），降低跳表的最大高度（避免空索引层浪费空间）。​

3.3.2 伪代码​

function delete(targetKey):
    update = array of size MAX_LEVEL
    current = 跳表的头节点（head）
    
    # 步骤1：定位各层前驱节点
    for i from 跳表最大高度-1 down to 0:
        while current.forward[i] != null and current.forward[i].key < targetKey:
            current = current.forward[i]
        update[i] = current
    
    # 步骤2：检查待删除节点是否存在
    current = current.forward[0]
    if current == null or current.key != targetKey:
        return  # 节点不存在，无需删除
    
    # 步骤3：删除节点并修复各层指针
    for i from 0 to current.level-1:
        # 若前驱节点的下一个节点不是待删除节点，说明该层无此节点，跳出
        if update[i].forward[i] != current:
            break
        update[i].forward[i] = current.forward[i]
    
    # 步骤4：调整跳表最大高度（删除空顶层）
    while 跳表当前最大高度 > 1 and head.forward[跳表当前最大高度-1] == null:
        跳表当前最大高度 -= 1
    
    # 释放待删除节点内存（可选，视语言而定）
    free(current)

​

4. 跳表的性能分析​

4.1 时间复杂度​

• 查找、插入、删除：平均 O (log n)，最坏 O (n)（概率极低）。​

原因：跳表的层数遵循几何分布，平均层数为 log n，每层遍历的节点数为常数，因此总操作次数为 O (log n)。​

4.2 空间复杂度​

• 平均 O (n)，最坏 O (n log n)。​

原因：每个节点的平均层高为 2（几何分布的期望），因此总指针数为 O (2n) = O (n)；极端情况下所有节点层高为 log n，总指针数为 O (n log n)，但概率极低。​

5. 跳表的应用场景​

跳表因 “高效 + 易实现” 的特性，在工业界应用广泛：​

• Redis 的 Sorted Set：Redis 中有序集合（zset）的底层实现之一（当数据量大或 key 较小时），利用跳表实现 O (log n) 的增删查和有序遍历。​
• LevelDB/RocksDB：作为 LSM 树（日志结构合并树）中 MemTable 的实现，支持高效的内存数据有序操作。​
• 区间查询场景：因跳表天然有序，可快速实现 “查找 key 在 [a,b] 之间的所有节点”（如 Redis 的 zrange 命令）。