跳表（Skip List）数据结构详解与实现

31 Views
数据结构算法数据结构算法redis
深入剖析跳表的原理、特性与实现方法，以及在Redis等系统中的实际应用
跳表（Skip List）数据结构详解与实现基本原理从有序链表到跳表跳表节点结构核心操作查找操作插入操作删除操作跳表分析性能特性跳表与平衡树比较跳表的实际应用Redis中的有序集合（Sorted Set）LevelDB的MemTable跳表Go语言实现示例总结

跳表（Skip List）数据结构详解与实现

跳表（Skip List）是一种随机化的数据结构，基于并联的有序链表，实现了类似平衡树的高效搜索性能，但更简单易实现。本文将深入介绍跳表的原理、特性及其实现方法。

基本原理

从有序链表到跳表

普通有序链表的查找需要O(n)时间复杂度，跳表通过建立多层索引来加速查找：

Level 3: -∞ -----------------------> ∞
Level 2: -∞ ----------> 30 --------> ∞
Level 1: -∞ ----> 20 --> 30 -------> ∞
Level 0: -∞ -> 10 -> 20 -> 30 -> 40 -> ∞

这种结构使得查找过程类似于二分查找，能够跳过许多不必要的节点。

跳表节点结构

每个跳表节点包含以下成员：

typedef struct skiplistNode {
    // 节点值
    void *obj;
    // 分值，用于排序
    double score;
    // 后向指针
    struct skiplistNode *backward;
    // 层级结构
    struct skiplistLevel {
        // 前向指针
        struct skiplistNode *forward;
        // 跨度
        unsigned long span;
    } level[];
} skiplistNode;

核心操作

查找操作

跳表的查找从最高层开始，逐层向下：

查找23的过程:
1. 从最高层Level 3的-∞开始
2. 向右移动，发现没有节点，降至Level 2
3. 在Level 2发现30 > 23，降至Level 1
4. 在Level 1找到20，向右移动，遇到30 > 23，降至Level 0
5. 在Level 0，从20向右移动，找到30 > 23
6. 由于未找到23，且已到达最底层，确认23不在跳表中

查找的时间复杂度为O(log n)。

插入操作

插入节点时，需要：

  1. 确定插入位置（类似查找）
  2. 随机生成节点高度
  3. 更新前向、后向指针及跨度
def randomLevel():
    level = 1
    # SKIPLIST_P = 0.25
    while random() < SKIPLIST_P and level < MAX_LEVEL:
        level += 1
    return level

随机层数的设计保证了跳表期望空间复杂度为O(n)。

删除操作

删除节点时，需要：

  1. 找到目标节点
  2. 更新相关指针和跨度
  3. 释放节点内存

跳表分析

性能特性

操作平均时间复杂度最坏时间复杂度
查找O(log n)O(n)
插入O(log n)O(n)
删除O(log n)O(n)
空间复杂度O(n)O(n log n)

跳表与平衡树比较

优势：

  • 实现简单，代码量小
  • 插入/删除只需修改相邻节点指针，不需要复杂的旋转操作
  • 更适合并发环境（修改局部性好）
  • 平均性能与平衡树相当

劣势：

  • 空间占用稍大
  • 范围查询不如B+树高效
  • 随机化可能导致性能波动

跳表的实际应用

Redis中的有序集合（Sorted Set）

Redis的有序集合（Zset）主要由跳表和哈希表组成：

  • 跳表：保证元素有序性，支持范围操作
  • 哈希表：提供O(1)的成员查找
ZADD leaderboard 89 "张三"
ZADD leaderboard 78 "李四"
ZADD leaderboard 95 "王五"

// 获取分数前两名
ZREVRANGE leaderboard 0 1
// 结果: 1) "王五" 2) "张三"

LevelDB的MemTable

Google的LevelDB使用跳表作为内存表（MemTable）的实现，用于存储最近写入的键值对。

跳表Go语言实现示例

package main
 
import (
    "fmt"
    "math/rand"
)
 
const (
    MaxLevel    = 16    // 最大层数
    Probability = 0.25  // 层级提升概率
)
 
// 跳表节点
type Node struct {
    key     int       // 键
    value   interface{} // 值
    forward []*Node   // 前向指针
}
 
// 跳表
type SkipList struct {
    header  *Node  // 头节点
    level   int    // 当前最大层数
    length  int    // 元素个数
}
 
// 创建跳表
func NewSkipList() *SkipList {
    return &SkipList{
        header: &Node{forward: make([]*Node, MaxLevel)},
        level:  1,
    }
}
 
// 随机层数
func randomLevel() int {
    level := 1
    for rand.Float64() < Probability && level < MaxLevel {
        level++
    }
    return level
}
 
// 查找元素
func (sl *SkipList) Search(key int) interface{} {
    x := sl.header
    
    // 从最高层开始查找
    for i := sl.level - 1; i >= 0; i-- {
        // 找到第i层小于目标key的最大节点
        for x.forward[i] != nil && x.forward[i].key < key {
            x = x.forward[i]
        }
    }
    
    // 检查是否找到
    x = x.forward[0]
    if x != nil && x.key == key {
        return x.value
    }
    return nil
}
 
// 插入元素
func (sl *SkipList) Insert(key int, value interface{}) {
    update := make([]*Node, MaxLevel)
    x := sl.header
    
    // 找到每一层的插入位置
    for i := sl.level - 1; i >= 0; i-- {
        for x.forward[i] != nil && x.forward[i].key < key {
            x = x.forward[i]
        }
        update[i] = x
    }
    
    // 到达第0层，检查key是否已存在
    x = x.forward[0]
    if x != nil && x.key == key {
        x.value = value  // 更新已有值
        return
    }
    
    // 获取随机层数
    level := randomLevel()
    if level > sl.level {
        for i := sl.level; i < level; i++ {
            update[i] = sl.header
        }
        sl.level = level
    }
    
    // 创建新节点
    newNode := &Node{
        key:     key,
        value:   value,
        forward: make([]*Node, level),
    }
    
    // 更新前向指针
    for i := 0; i < level; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }
    
    sl.length++
}

总结

跳表是一种兼具简单性和高效性的数据结构，其随机化的特性使其在期望上能达到与平衡树相当的性能，同时具有实现简单、易于维护的优势。跳表在Redis、LevelDB等系统中的成功应用，证明了其在实际工程中的价值。

对于需要高效有序数据结构且希望避免平衡树复杂性的场景，跳表是一个优秀的选择。它不仅提供了O(log n)的查找效率，还支持高效的插入和删除操作，使其成为构建高性能系统的有力工具。

31 Views