跳表¶

概述¶

跳表（Skip List）是由William Pugh于1990年提出的一种基于有序链表的概率数据结构。通过在有序链表上建立多层索引，实现对数级别的查找效率，同时保持实现简单的优点。

跳表的重要性

跳表是Redis有序集合（ZSET）和LevelDB MemTable的底层实现。它在保持平衡树O(log n)查找效率的同时，实现更简单，并发支持更好，是工程实践中非常成功的数据结构。

跳表的设计思想¶

从有序链表说起¶

普通有序链表查找需要O(n)时间：

有序链表

1

→

3

→

5

→

7

→

9

→

11

→

13

→

15

→

17

→

19

查找13需要遍历: 1→ 3→ 5→ 7→ 9→ 11→ 13 (7次比较)

建立索引加速¶

借鉴二分查找思想，建立多级索引：

graph LR
    subgraph "跳表结构示意"
        L3["Level 3:     1---------------------> 13"]
        L2["Level 2:     1-----------> 7-------> 13"]
        L1["Level 1:     1-----> 4----> 7-------> 13-----> 17"]
        L0["Level 0:     1-> 3-> 4-> 5-> 7-> 9-> 11-> 13-> 15-> 17-> 19"]
    end
    
    L3 --> L2 --> L1 --> L0

Text Only

完整跳表结构:

Level 3:     1 ────────────────────────→ 13 ────────────→ NULL
             │                           │
Level 2:     1 ───────────→ 7 ─────────→ 13 ────────────→ NULL
             │             │             │
Level 1:     1 ────→ 4 ───→ 7 ─────────→ 13 ────→ 17 ───→ NULL
             │       │     │             │       │
Level 0:     1 → 3 → 4 → 5 → 7 → 9 → 11 → 13 → 15 → 17 → 19 → NULL
             ↑
            头节点

查找13的过程:
1. Level 3: 1 → 13 (找到!)  仅需2次比较

✓ 查找优化效果

原链表: 7次比较
跳表: 仅需2次比较
提升: 3.5倍

查找效率分析¶

查找效率推导

假设每层节点数是下一层的1/2:

Level 0: n 个节点
Level 1: n/2 个节点
Level 2: n/4 个节点
...
Level k: n/2^k 个节点

当 n/2^k = 1 时，k = log₂n

查找时，每层最多跳过2个节点

共需比较 2 × log₂n 次

时间复杂度: O(log n)

跳表结构详解¶

多层索引结构¶

graph TB
    subgraph "跳表的节点和指针"
        A["节点1<br/>key=1<br/>forward: [→, →, →]"]
        B["节点7<br/>key=7<br/>forward: [→, →]"]
        C["节点13<br/>key=13<br/>forward: [→, →, →]"]
    end
    
    A -->|"forward[0]"| D["节点3"]
    A -->|"forward[1]"| B
    A -->|"forward[2]"| C
    
    style A fill:#E3F2FD
    style B fill:#E8F5E9
    style C fill:#FFF3E0

随机层数机制¶

跳表通过随机决定节点层数来维持平衡：

graph TB
    A["插入新节点"] --> B["随机生成层数"]
    B --> C{"以概率P=0.5<br/>继续增加层数?"}
    C -->|"是"| C
    C -->|"否"| D["确定最终层数"]
    
    style D fill:#E8F5E9

Text Only

层数概率分布:

P(层数 = 0) = 1 - P = 0.5
P(层数 = 1) = P × (1 - P) = 0.25
P(层数 = 2) = P² × (1 - P) = 0.125
P(层数 = k) = P^k × (1 - P)

期望层数 = 1 / (1 - P) = 2 (当P=0.5时)

每个节点的期望指针数 = 1 + 1/(1-P) = 3
空间复杂度: O(n)

跳表实现¶

节点与数据结构定义¶

C
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_LEVEL 16    // 最大层数
#define P 0.5           // 概率因子

// 跳表节点
typedef struct SkipNode {
    int key;                    // 键值
    int value;                  // 关联值
    struct SkipNode **forward;  // 各层前向指针数组
} SkipNode;

// 跳表结构
typedef struct {
    int level;          // 当前最大层数
    SkipNode *header;   // 头节点
} SkipList;

// 创建新节点
SkipNode* createNode(int level, int key, int value) {
    SkipNode *node = (SkipNode*)malloc(sizeof(SkipNode));
    node->key = key;
    node->value = value;
    // 分配level+1层指针（从0到level）
    node->forward = (SkipNode**)calloc(level + 1, sizeof(SkipNode*));
    return node;
}

// 创建跳表
SkipList* createSkipList() {
    SkipList *list = (SkipList*)malloc(sizeof(SkipList));
    list->level = 0;
    // 头节点拥有所有层
    list->header = createNode(MAX_LEVEL, -1, -1);
    
    for (int i = 0; i <= MAX_LEVEL; i++) {
        list->header->forward[i] = NULL;
    }
    
    srand(time(NULL));
    return list;
}

随机层数生成¶

C
// 生成随机层数
int randomLevel() {
    int level = 0;
    // 以概率P继续增加层数
    while ((double)rand() / RAND_MAX < P && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

/*
随机层数示意:

rand() = 0.3 → 0.3 < 0.5 → level = 1
rand() = 0.7 → 0.7 >= 0.5 → 停止
最终层数: 1

rand() = 0.3 → 0.3 < 0.5 → level = 1
rand() = 0.4 → 0.4 < 0.5 → level = 2
rand() = 0.8 → 0.8 >= 0.5 → 停止
最终层数: 2
*/

查找操作详解¶

graph TB
    subgraph "查找key=13的过程"
        A["从最高层Level 3开始"] --> B["1 < 13, 前进到13"]
        B --> C["13 == 13, 找到!"]
    end
    
    subgraph "查找key=9的过程"
        D["Level 3: 1 → 13 > 9, 停在1"] --> E["Level 2: 1 → 7 < 9, 继续"]
        E --> F["Level 2: 7 → 13 > 9, 停在7"]
        F --> G["Level 1: 7 → 13 > 9, 停在7"]
        G --> H["Level 0: 7 → 9 == 9, 找到!"]
    end
    
    style C fill:#E8F5E9
    style H fill:#E8F5E9

C
// 查找元素
SkipNode* search(SkipList *list, int key) {
    SkipNode *curr = list->header;
    
    // 从最高层向下查找
    for (int i = list->level; i >= 0; i--) {
        // 在当前层向右移动，直到找到 >= key 的位置
        while (curr->forward[i] && curr->forward[i]->key < key) {
            curr = curr->forward[i];
        }
    }
    
    // 移动到第0层的下一个节点
    curr = curr->forward[0];
    
    // 检查是否找到
    if (curr && curr->key == key) {
        return curr;
    }
    
    return NULL;
}

/*
查找key=9示例:

初始: curr = header

Level 3: header.forward[3] = 节点1
         1.forward[3] = 节点13, 13.key=13 >= 9
         停在节点1

Level 2: 1.forward[2] = 节点7, 7.key=7 < 9
         移动到节点7
         7.forward[2] = 节点13, 13.key=13 >= 9
         停在节点7

Level 1: 7.forward[1] = 节点13, 13.key=13 >= 9
         停在节点7

Level 0: 7.forward[0] = 节点9
         移动到节点9

返回: 节点9
*/

插入操作详解¶

graph TB
    subgraph "插入key=6的过程"
        A["1. 查找插入位置，记录update数组"] --> B["2. 随机生成层数，假设为2"]
        B --> C["3. 创建新节点，连接各层指针"]
        C --> D["4. 更新update节点的forward指针"]
    end
    
    style D fill:#E8F5E9

Text Only

插入key=6示意:

插入前:
Level 2:     1 ───────────→ 7
Level 1:     1 ────→ 4 ───→ 7
Level 0:     1 → 3 → 4 → 5 → 7

查找位置后的update数组:
update[2] = 节点1
update[1] = 节点4
update[0] = 节点5

假设随机层数为2:
新节点6的forward:
forward[2] = NULL
forward[1] = 节点7
forward[0] = 节点7

更新后:
Level 2:     1 ───────→ 6 ─→ 7
Level 1:     1 ────→ 4 → 6 → 7
Level 0:     1 → 3 → 4 → 5 → 6 → 7

C
// 插入元素
void insert(SkipList *list, int key, int value) {
    SkipNode *update[MAX_LEVEL + 1];  // 记录各层的前驱节点
    SkipNode *curr = list->header;
    
    // 查找插入位置，记录每层的前驱节点
    for (int i = list->level; i >= 0; i--) {
        while (curr->forward[i] && curr->forward[i]->key < key) {
            curr = curr->forward[i];
        }
        update[i] = curr;  // 记录当前层的前驱
    }
    
    curr = curr->forward[0];
    
    // 如果key已存在，更新value
    if (curr && curr->key == key) {
        curr->value = value;
        return;
    }
    
    // 随机生成新节点层数
    int level = randomLevel();
    
    // 如果新层数大于当前最大层数，初始化高层
    if (level > list->level) {
        for (int i = list->level + 1; i <= level; i++) {
            update[i] = list->header;
        }
        list->level = level;
    }
    
    // 创建新节点
    SkipNode *newNode = createNode(level, key, value);
    
    // 插入新节点，更新各层指针
    for (int i = 0; i <= level; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

删除操作¶

C
// 删除元素
void delete(SkipList *list, int key) {
    SkipNode *update[MAX_LEVEL + 1];
    SkipNode *curr = list->header;
    
    // 查找删除位置
    for (int i = list->level; i >= 0; i--) {
        while (curr->forward[i] && curr->forward[i]->key < key) {
            curr = curr->forward[i];
        }
        update[i] = curr;
    }
    
    curr = curr->forward[0];
    
    // 如果没找到，直接返回
    if (!curr || curr->key != key) {
        return;
    }
    
    // 更新各层指针
    for (int i = 0; i <= list->level; i++) {
        if (update[i]->forward[i] != curr) {
            break;
        }
        update[i]->forward[i] = curr->forward[i];
    }
    
    // 降低层数
    while (list->level > 0 && list->header->forward[list->level] == NULL) {
        list->level--;
    }
    
    // 释放节点内存
    free(curr->forward);
    free(curr);
}

范围查询¶

C
// 范围查询 [minKey, maxKey]
void rangeQuery(SkipList *list, int minKey, int maxKey) {
    SkipNode *curr = list->header;
    
    // 定位到 >= minKey 的位置
    for (int i = list->level; i >= 0; i--) {
        while (curr->forward[i] && curr->forward[i]->key < minKey) {
            curr = curr->forward[i];
        }
    }
    
    curr = curr->forward[0];
    
    // 在底层遍历范围内的元素
    printf("范围查询 [%d, %d]: ", minKey, maxKey);
    while (curr && curr->key <= maxKey) {
        printf("(%d, %d) ", curr->key, curr->value);
        curr = curr->forward[0];
    }
    printf("\n");
}

C++ 实现¶

C++
#include <vector>
#include <random>
#include <iostream>

template<typename K, typename V>
class SkipList {
private:
    static const int MAX_LEVEL = 16;
    static constexpr double P = 0.5;
    
    struct Node {
        K key;
        V value;
        std::vector<Node*> forward;
        
        Node(K k, V v, int level) 
            : key(k), value(v), forward(level + 1, nullptr) {}
    };
    
    Node *header;
    int level;
    std::mt19937 rng;
    std::uniform_real_distribution<double> dist;
    
    int randomLevel() {
        int lvl = 0;
        while (dist(rng) < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }
    
public:
    SkipList() : level(0), rng(std::random_device{}()), dist(0, 1) {
        header = new Node(K{}, V{}, MAX_LEVEL);
    }
    
    ~SkipList() {
        Node *curr = header->forward[0];
        while (curr) {
            Node *temp = curr;
            curr = curr->forward[0];
            delete temp;
        }
        delete header;
    }
    
    // 查找
    V* search(const K& key) {
        Node *curr = header;
        
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->key < key) {
                curr = curr->forward[i];
            }
        }
        
        curr = curr->forward[0];
        return (curr && curr->key == key) ? &curr->value : nullptr;
    }
    
    // 插入
    void insert(const K& key, const V& value) {
        std::vector<Node*> update(MAX_LEVEL + 1, nullptr);
        Node *curr = header;
        
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->key < key) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        
        curr = curr->forward[0];
        
        if (curr && curr->key == key) {
            curr->value = value;
            return;
        }
        
        int lvl = randomLevel();
        
        if (lvl > level) {
            for (int i = level + 1; i <= lvl; i++) {
                update[i] = header;
            }
            level = lvl;
        }
        
        Node *newNode = new Node(key, value, lvl);
        
        for (int i = 0; i <= lvl; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }
    
    // 删除
    bool remove(const K& key) {
        std::vector<Node*> update(MAX_LEVEL + 1, nullptr);
        Node *curr = header;
        
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->key < key) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        
        curr = curr->forward[0];
        
        if (!curr || curr->key != key) {
            return false;
        }
        
        for (int i = 0; i <= level; i++) {
            if (update[i]->forward[i] != curr) break;
            update[i]->forward[i] = curr->forward[i];
        }
        
        delete curr;
        
        while (level > 0 && header->forward[level] == nullptr) {
            level--;
        }
        
        return true;
    }
    
    // 打印结构
    void print() {
        for (int i = level; i >= 0; i--) {
            std::cout << "Level " << i << ": ";
            Node *curr = header->forward[i];
            while (curr) {
                std::cout << curr->key << " ";
                curr = curr->forward[i];
            }
            std::cout << std::endl;
        }
    }
};

复杂度分析¶

时间复杂度¶

操作	平均时间复杂度	最坏时间复杂度	说明
查找	O(log n)	O(n)	最坏情况所有节点都在第0层
插入	O(log n)	O(n)	包含查找和指针更新
删除	O(log n)	O(n)	包含查找和指针更新
范围查询	O(log n + k)	O(n)	k为结果数量

空间复杂度¶

Text Only

每个节点的期望指针数 = 1 + 1/(1-P) = 1 + 2 = 3 (当P=0.5)

总空间 = n × 平均指针数 = O(n)

详细计算:
E[指针数] = Σ(k=0 to ∞) P(层数≥k)
         = Σ(k=0 to ∞) P^k
         = 1/(1-P)
         = 2 (当P=0.5)

每个节点平均: 1个key + 1个value + 2个forward指针 = O(1)
总空间: O(n)

跳表 vs 平衡树对比¶

特性	跳表	平衡树（AVL/红黑树）
查找效率	O(log n)	O(log n)
插入效率	O(log n)	O(log n)
删除效率	O(log n)	O(log n)
实现难度	简单 ✓	复杂 ✗
范围查询	高效 ✓	需要中序遍历
并发支持	容易 ✓	困难 ✗
空间开销	较大 (O(n)×3)	较小 (O(n))
有序遍历	直接遍历第0层	中序遍历
最坏保证	概率保证	确定性保证

跳表的优势¶

1. 实现简单¶

Text Only

平衡树需要:
- 复杂的旋转操作
- 多种情况的分类讨论
- 维护平衡因子/颜色

跳表只需要:
- 简单的指针操作
- 随机层数生成
- 无需复杂的平衡逻辑

2. 范围查询高效¶

C
// 跳表：直接在第0层遍历
void rangeQuery(int min, int max) {
    Node *curr = findPosition(min);  // O(log n)
    while (curr->key <= max) {       // O(k)
        process(curr);
        curr = curr->forward[0];
    }
}

// 平衡树：需要中序遍历，更复杂

3. 并发友好¶

Text Only

跳表并发优势:
- 插入/删除只影响局部节点
- 无需全局重平衡（旋转）
- 易于实现无锁版本

平衡树并发困难:
- 旋转可能影响大量节点
- 需要复杂的锁策略

应用场景¶

1. Redis 有序集合（ZSET）¶

C
// Redis ZSET 使用跳表实现
// 支持的操作:
ZADD key score member     // 插入/更新
ZREM key member           // 删除
ZRANK key member          // 获取排名
ZRANGE key start stop     // 范围查询
ZSCORE key member         // 获取分数

2. LevelDB MemTable¶

C
// LevelDB 内存表使用跳表
// 特点:
// - 内存中的有序键值存储
// - 快速查找和范围扫描
// - 写入效率高

3. 时间序列数据¶

C
// 存储带时间戳的数据
SkipList<Timestamp, Data> timeSeries;

// 高效查询时间范围
timeSeries.rangeQuery(startTime, endTime);

跳表变体¶

1. 确定性跳表¶

使用确定性方法决定层数，而非随机。

2. 并发跳表¶

无锁或细粒度锁的并发实现。

C++
// 无锁跳表核心思想:
// 1. 使用CAS操作更新指针
// 2. 节点标记删除而非物理删除
// 3. 延迟删除无效节点

3. 可持久化跳表¶

支持访问历史版本。

参考资料¶

William Pugh (1990). "Skip Lists: A Probabilistic Alternative to Balanced Trees"
Redis ZSET Implementation
LevelDB Skiplist
Skip List - Wikipedia