跳表（Skip List） - 数据结构与算法-学习笔记-上海佼艾

一、什么是跳表

跳表（Skip List）是由 William Pugh 于 1989 年提出的一种概率平衡的链表数据结构。它在有序链表的基础上引入了"多层索引"的概念，使得搜索、插入和删除操作的平均时间复杂度从 O(n) 降低到 O(log n)。跳表的本质是用空间换时间——通过维护多级指针来加速查找过程。

与平衡树（如红黑树、AVL树）不同，跳表不依赖复杂的旋转操作来维持平衡，而是通过随机化层数来实现概率意义上的平衡。这使得跳表的实现代码非常简洁，且在实际应用中性能表现优秀。Redis 的有序集合（ZSET）底层就使用了跳表作为核心数据结构。

核心思想：跳表通过在原始有序链表上建立多层"索引"（Express Lane），让查找时能够"跳过"大量中间节点，从而将线性查找加速为近似二分查找。

直观理解：高速公路与普通公路

可以把跳表理解为一个多层高速公路系统。普通有序链表就像只有一条普通公路，节点依次排列，查找时必须逐个经过。而跳表在这个基础上修建了多条"高速公路"（索引层），每层高速公路只连接部分重要节点。查找时从最高层的高速公路出发，快速逼近目标区域，然后转入下一层进行精细定位——就像从高速公路切换到国道，再切换到乡道，最终精确到达目的地。

类比：想象你要找一本书的某一页。你不会从第1页逐页翻到第300页，而是先看目录找到章节（类似高层索引），再看小节定位（类似低层索引），最后精确翻到目标页码。

二、跳表的结构设计

2.1 节点结构

跳表的每个节点包含两部分信息：（1）存储的键值对（或仅键值）；（2）一个数组，其中每个元素存储指向该层下一个节点的指针。节点的"层数"（level）是在插入时随机决定的。

class SkipListNode:
    def __init__(self, key, value, level):
        self.key = key                # 节点键
        self.value = value              # 节点值
        self.forward = [None] * level  # 每层的前向指针

2.2 跳表整体结构

跳表由以下几个核心组件构成：

头节点（Head Node）：是一个特殊的哨兵节点，它的层数等于跳表当前的最大层数，不存储实际数据，仅用于辅助查找。
索引层级：从第 0 层（最底层，包含所有节点）到最高层（仅包含部分节点）。层数越高，节点越少，查找时跳过的距离越远。
最大层数（MaxLevel）：由数据规模决定，通常取 log₂(n) 或固定值（如 32、64）。
概率因子 p：控制节点层数分布的参数，通常取 1/2 或 1/4，表示节点升到下一层的概率。

class SkipList:
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level      # 最大层数
        self.p = p                      # 层数概率因子
        self.level = 0                 # 当前实际最大层数
        self.head = SkipListNode(None, None, max_level)

2.3 层数随机化策略

节点的层数通过随机算法确定。最常用的策略是"抛硬币"法：从第 0 层开始，每次以概率 p 决定是否升到下一层，直到随机失败或达到最大层数。这种策略保证了层数的概率分布满足几何分布，使得高层节点数量指数级减少。

import random

def random_level(p, max_level):
    level = 1
    while random.random() < p and level < max_level:
        level += 1
    return level

假设 p=0.5，层数分布如下：

层数 ≥ 1 的概率：100%（每个节点至少在第 0 层）
层数 ≥ 2 的概率：50%
层数 ≥ 3 的概率：25%
层数 ≥ k 的概率：p^(k-1)

因此，第 k 层的期望节点数为 n × p^(k-1)，呈指数衰减。

三、跳表的核心操作

3.1 搜索操作

搜索是跳表中最基础的操作。算法从最高层开始遍历，在每一层中水平移动直到遇到第一个大于等于目标值的节点，然后下降到下一层继续搜索，最终在第 0 层找到目标或确认不存在。

def search(self, key):
    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]

    # 到达第0层，检查目标节点
    current = current.forward[0]
    if current and current.key == key:
        return current.value
    return None

搜索过程的关键是每层向右、逐层向下的二维搜索模式。在最高层，每次跳跃可以越过大量节点，随着层数降低，跳跃步长逐渐缩小，最终精确定位。

时间复杂度：跳表的搜索操作平均时间复杂度为 O(log n)。在最坏情况下（随机化效果很差），时间复杂度退化为 O(n)。但由于随机化的保证，最坏情况发生的概率极低。

3.2 插入操作

插入操作在搜索的基础上增加了记录"前驱节点"的步骤。具体过程如下：

生成新节点的随机层数 new_level。
在每一层记录搜索路径上的前驱节点（update 数组）。
如果 new_level 大于当前最大层数，更新跳表的最大层数，并初始化新层的前驱为头节点。
在每一层将新节点插入到前驱节点之后。

def insert(self, key, value):
    update = [None] * self.max_level
    current = self.head

    # 1. 搜索并记录每层的前驱节点
    for i in range(self.level - 1, -1, -1):
        while current.forward[i] and current.forward[i].key < key:
            current = current.forward[i]
        update[i] = current

    current = current.forward[0]

    # 2. 如果键已存在，更新值
    if current and current.key == key:
        current.value = value
        return

    # 3. 生成随机层数
    new_level = random_level(self.p, self.max_level)

    # 4. 如果新层数超过当前最大层数，更新头节点指针
    if new_level > self.level:
        for i in range(self.level, new_level):
            update[i] = self.head
        self.level = new_level

    # 5. 创建新节点并插入到各层
    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

插入操作的巧妙之处在于：搜索过程和插入位置记录合二为一。在向下搜索的同时就记录了每一层需要更新的前驱节点，避免了第二次遍历。

3.3 删除操作

删除操作与插入类似，也需要记录前驱节点。找到目标节点后，在每一层将其从链表中移除。如果删除后某些层不再有节点，需要降低跳表的最大层数。

def delete(self, key):
    update = [None] * self.max_level
    current = self.head

    # 1. 搜索并记录每层的前驱节点
    for i in range(self.level - 1, -1, -1):
        while current.forward[i] and current.forward[i].key < key:
            current = current.forward[i]
        update[i] = current

    current = current.forward[0]

    # 2. 如果节点不存在，返回
    if not current or current.key != key:
        return False

    # 3. 在各层中移除节点
    for i in range(current.level):
        update[i].forward[i] = current.forward[i]

    # 4. 更新跳表最大层数（移除空的顶层）
    while self.level > 0 and self.head.forward[self.level - 1] is None:
        self.level -= 1

    return True

删除后需要从最高层向下检查，移除那些不再包含任何节点的空层，以保持跳表的效率。这一步虽然不是必须的，但有助于节省后续搜索操作的时间。

四、时间复杂度分析

4.1 平均时间复杂度

跳表的平均时间复杂度分析基于其随机化特性。当概率因子 p=0.5 时：

操作	平均时间复杂度	最坏时间复杂度
搜索（Search）	O(log n)	O(n)
插入（Insert）	O(log n)	O(n)
删除（Delete）	O(log n)	O(n)

William Pugh 的原始论文证明了跳表的期望搜索长度为 (1/p) × log₁/ₚ(n) + O(1)。当 p=0.5 时，期望比较次数约为 2 × log₂(n)。当 p=0.25 时，约为 4 × log₄(n) = 4 × log₂(n)/2 = 2 × log₂(n)，这与 p=0.5 的理论性能相当。

4.2 搜索路径长度分析

搜索路径的长度由两个因素决定：

垂直移动：从最高层下降到第 0 层的步数，每下降一层算一步，最多为当前最大层数。
水平移动：在每一层中水平遍历的节点数。在期望意义上，每层水平遍历的节点数不超过 1/p。

直观理解：当 p 较大时（如 0.5），层数较多，但每层水平移动较少；当 p 较小时（如 0.25），层数较少，但每层水平移动略多。两者在理论上的乘积大致恒定。

"跳表的期望时间复杂度与平衡二叉树相当，都是 O(log n)，但跳表的实现代码量仅为红黑树的五分之一左右。"—— William Pugh, 1989

五、空间复杂度分析

跳表使用额外的指针来构建索引层，因此付出了额外的空间代价。空间复杂度由各层指针总数决定。

5.1 指针开销的期望值

每个节点在第 k 层存在的概率为 p^(k-1)。由于节点最多在最高层有一个指针，因此节点指针数量的期望为：

E[pointers] = 1 + p + p² + p³ + ... < 1/(1-p)

当 p=0.5 时，每个节点平均有 2 个指针（即平均层数约为 2）。这意味着跳表的额外空间开销约为 O(n)，具体是 n/(1-p) 个指针。

概率因子 p	平均层数	空间复杂度	搜索常数因子
1/2 (0.5)	≈ 2	O(2n)	约 2 × log₂(n)
1/4 (0.25)	≈ 1.33	O(1.33n)	约 2 × log₂(n)
1/e (≈0.3679)	≈ 1.58	O(1.58n)	约 e × ln(n)

空间权衡：p=0.25 比 p=0.5 节省约 33% 的指针空间，搜索性能理论持平。因此 Redis 的有序集合实现选择了 p=0.25 作为默认参数。

六、跳表 vs 红黑树

跳表和红黑树都是 O(log n) 时间复杂度的有序数据结构，但在多个维度上存在差异：

对比维度	跳表（Skip List）	红黑树（Red-Black Tree）
实现复杂度	简单，约 100 行代码	复杂，约 400+ 行代码
平衡机制	概率平衡（随机化）	确定性平衡（旋转+染色）
范围查询	天然支持（底层为有序链表）	需中序遍历或额外指针
内存占用	平均 n/(1-p) 个指针	每个节点 2 个指针 + 1 个颜色位
最坏情况性能	O(n) 概率极低	严格 O(log n)
并发友好性	较高（各层指针独立更新）	较低（旋转操作影响范围大）
调试难度	低	高
典型应用	Redis ZSET、LevelDB MemTable	Linux 内核 CFS、C++ STL map/set

选择建议：在工程项目中，如果对最坏时间性能有严格实时要求（如航空航天、工业控制），应选择红黑树。如果希望代码维护简单、需要频繁执行范围查询或区间遍历，跳表是更好的选择。

跳表的独特优势

范围查询高效：跳表的第 0 层是完整的有序链表，范围查询（如"返回所有在 [a,b] 之间的元素"）只需要找到下界后顺序遍历即可。红黑树则需要中序遍历或额外的线索化。
实现直观：跳表的核心操作不涉及复杂的树旋转（左旋、右旋、变色等），代码容易理解和维护。
并发友好：跳表的更新操作只影响目标节点前后相邻节点的指针，锁粒度较细，适合无锁并发编程。而红黑树的旋转可能影响较大范围的节点。

七、跳表在 Redis 中的应用

7.1 Redis 有序集合（ZSET）

Redis 的有序集合是跳表最著名的工业应用之一。ZSET 在跳表的基础上进行了多项定制化改进：

分值+成员：每个节点存储一个 score（分值）和 member（成员），支持按分值排序。
相同的分值处理：当多个成员具有相同分值，按字典序（lexicographical order）排序。
双向链表：在第 0 层使用双向链表（backward 指针），便于逆序遍历，如 ZREVRANGE 命令。
跨度信息：每个节点的指针数组额外记录了"跨度"（span），即该层指针跳过了多少个节点，用于快速计算元素排名（ZRANK 命令）。
概率参数：Redis 使用 p=1/4（即 ZSKIPLIST_P = 0.25），ZSKIPLIST_MAXLEVEL = 32（可容纳 2³² 个元素）。

/* Redis 跳表节点结构（C 语言源码简化版） */
typedef struct zskiplistNode {
    sds ele;                        // 成员（字符串）
    double score;                  // 分值
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span;           // 跨度
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;           // 节点总数
    int level;                     // 当前最大层数
} zskiplist;

7.2 Redis 为什么选择跳表而不是红黑树

Redis 作者 antirez 在讨论中给出了具体原因：

内存占用更可控：跳表的平均层数约为 1.33（p=0.25 时），红黑树则需要存储更多的结构信息。
范围查询更高效：ZSET 经常执行 ZRANGEBYSCORE 这样的范围查询操作，跳表的底层链表天然支持高效的范围遍历。
实现更简单：跳表的插入、删除和查找逻辑更加直观，代码可维护性更好。
调试更容易：跳表的层级结构可以通过可视化工具直观展示，红黑树的旋转逻辑则难以调试。

"跳表的实现比平衡树简单得多，而且它支持范围查询。虽然跳表的 O(log n) 是平均情况而不是最坏情况，但通过合理参数选择，最坏情况在实际中几乎不可能发生。"—— Redis 作者 Salvatore Sanfilippo (antirez)

八、完整实现：Python 版跳表

下面给出一个完整的 Python 跳表实现，包含搜索、插入、删除和遍历操作：

import random


class SkipListNode:
    def __init__(self, key, value, level):
        self.key = key
        self.value = value
        self.forward = [None] * level

    @property
    def level(self):
        return len(self.forward)


class SkipList:
    def __init__(self, max_level=16, p=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):
        level = 1
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level

    def search(self, key):
        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 insert(self, key, value):
        update = [None] * self.max_level
        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]
            update[i] = current

        current = current.forward[0]
        if current and current.key == key:
            current.value = value
            return

        new_level = self._random_level()
        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

    def delete(self, key):
        update = [None] * self.max_level
        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]
            update[i] = current

        current = current.forward[0]
        if not current or current.key != key:
            return False

        for i in range(current.level):
            update[i].forward[i] = current.forward[i]

        while (self.level > 0 and
               self.head.forward[self.level - 1] is None):
            self.level -= 1

        self._size -= 1
        return True

    def display(self):
        print("Skip List (level=", self.level,
              ", size=", self._size, "):", sep="")
        level_labels = []
        for i in range(self.level):
            nodes = []
            cur = self.head.forward[i]
            while cur:
                nodes.append(str(cur.key))
                cur = cur.forward[i]
            level_labels.append(f"  Level {i}: " + " -> ".join(nodes))
        for line in reversed(level_labels):
            print(line)

    def __len__(self):
        return self._size

    def __contains__(self, key):
        return self.search(key) is not None

    def range_query(self, low, high):
        """返回键在 [low, high] 范围内的所有 (key, value) 对"""
        result = []
        current = self.head
        for i in range(self.level - 1, -1, -1):
            while (current.forward[i] and
                   current.forward[i].key < low):
                current = current.forward[i]
        current = current.forward[0]
        while current and current.key <= high:
            result.append((current.key, current.value))
            current = current.forward[0]
        return result

使用示例

# 创建跳表并插入数据
sl = SkipList(max_level=8, p=0.5)
sl.insert(3, "three")
sl.insert(1, "one")
sl.insert(7, "seven")
sl.insert(5, "five")
sl.insert(9, "nine")

sl.display()
# 输出示例（取决于随机化结果）：
# Skip List (level=3, size=5):
#   Level 2: 5
#   Level 1: 1 -> 5 -> 7
#   Level 0: 1 -> 3 -> 5 -> 7 -> 9

# 搜索
print(sl.search(5))   # 输出: five
print(sl.search(2))   # 输出: None

# 范围查询
print(sl.range_query(3, 7))
# 输出: [(3, 'three'), (5, 'five'), (7, 'seven')]

# 删除
sl.delete(5)
print(5 in sl)   # 输出: False

九、跳表的变体与优化

9.1 可索引跳表（Indexable Skip List）

在标准跳表的基础上，每个节点的指针额外记录"跨度"信息（如 Redis 所做的那样），可以在 O(log n) 时间内按排名访问元素，相当于同时支持了"按值查找"和"按排名查找"两种访问模式。

9.2 确定型跳表（Deterministic Skip List）

也称为 1-2-3 跳表，它使用确定性的层数分配策略（而不是随机化）来保证 O(log n) 的最坏时间复杂度。但代价是实现复杂度增加，失去了跳表"实现简单"的核心优势。

9.3 无锁跳表（Lock-Free Skip List）

利用 CAS（Compare-And-Swap）原子操作实现并发安全的跳表，是高性能并发系统中的重要数据结构。无锁跳表的关键挑战在于确保指针更新的原子性和可见性。Java 标准库中的 ConcurrentSkipListMap 就是无锁跳表的经典实现。

9.4 压缩跳表（Compressed Skip List）

针对特定场景优化指针存储，例如使用位图表示层数分布，或使用变长编码存储指针指向的目标偏移量，以降低内存占用。

工程实践：在实际项目中，跳表的 p 值通常取 0.25 或 0.5，最大层数取 32 或 64。这些参数的选取需要在搜索效率和空间开销之间做出权衡。对于大多数场景，p=0.25 是推荐值。

十、跳表的适用场景

场景	推荐数据结构	原因
需要频繁范围查询	跳表	底层链表天然支持高效范围遍历
对最坏时间有严格约束	红黑树 / B树	确定性平衡保证严格 O(log n)
内存极度受限（嵌入式）	红黑树 / 有序数组	跳表指针开销更大
需要按排名访问	可索引跳表	跨度信息支持 O(log n) 排名查询
高并发读写	无锁跳表	指针更新粒度细，适合 CAS 操作
需要实现简单、快速迭代	跳表	实现代码少，调试和扩展成本低

十一、核心要点总结

核心原理：跳表通过"多层有序链表 + 随机化层数"的机制，将有序链表的 O(n) 查找加速为 O(log n)。

概率平衡：跳表不追求严格的平衡，而是通过随机化使得数据结构的形态在概率意义上接近平衡。层数服从几何分布，高层节点指数级减少。
操作流程：搜索/插入/删除都遵循"从高到低、每层向右"的二维搜索模式。插入和删除需要记录每层的前驱节点。
时间复杂度：平均 O(log n)，最坏 O(n)（概率极低）。空间复杂度 O(n)，平均每个节点约 1/(1-p) 个指针。
参数选择：p=0.25 是空间和搜索效率的较好平衡点，Redis 即选用了此值。最大层数建议取 max(16, ceil(log₂(n)))。
核心竞争力：实现简单、范围查询高效、并发友好。这些特性使其在 Redis、LevelDB、Java ConcurrentSkipListMap 等系统中得到广泛应用。

面试要点：跳表是高频面试题。重点掌握：跳表的原理与结构、搜索过程可视化、层数随机化策略、与红黑树的对比、Redis 中跳表的应用和优化。

十二、进一步思考

跳表的设计哲学体现了计算机科学中一个重要的思想：用随机化来简化确定性复杂问题。红黑树通过精妙的旋转规则保证平衡，而跳表通过简单的"抛硬币"就实现了同样的效果。这种"概率方法"在算法设计中有着广泛的应用——从哈希表到跳表，从快速排序到蒙特卡洛算法。

深入思考以下问题，有助于更好地理解跳表：

如果 p 取不同值（如 0.1 或 0.9），跳表的性能会如何变化？能否找出最优的 p 值？
跳表的"概率平衡"特性是否会随着插入和删除操作的交替执行而退化？为什么？
如果底层数据结构不是链表而是数组（即使用多层有序数组），会得到什么数据结构？它和跳表有何异同？
在什么业务场景下，跳表的范围查询优势不可替代？
跳表的随机化策略能否用确定性策略替代，同时保持代码的简洁性？

"跳表的美在于它用最简单的随机化思想解决了一个看似复杂的问题。当你理解了跳表，你就理解了概率方法在算法设计中的力量。"