跳表 (Skip List) 详解

跳表 (Skip List) 是一种概率性数据结构，由 William Pugh 于 1990 年发明。它是一种用于存储有序元素的数据结构，可以在平均 O(log N) 的时间复杂度内完成搜索、插入和删除操作。跳表的性能与平衡二叉树（如 AVL 树、红黑树）相当，但其实现更为简单，尤其是在并发环境下，它通常比平衡二叉树更容易实现高效的并发控制。跳表通过维护多层链表，并使用随机化方法来决定每个节点的高度，从而实现快速查找。

核心思想：在有序链表的基础上，增加多级索引（多层链表）。通过随机化算法决定每个节点在不同层级中出现的概率，使得大部分搜索可以跳过大量节点，从而达到对数级的查找速度。

---

一、为什么需要跳表？传统数据结构的局限性

在计算机科学中，我们需要高效地存储和检索有序数据。常见的几种数据结构：

1. 有序数组：
   • 优势：查找（二分查找）O(log N)，按顺序遍历 O(N)。
   • 劣势：插入和删除元素需要移动大量元素，时间复杂度 O(N)。
2. 有序链表：
   • 优势：插入和删除元素 O(1) (找到位置后)。
   • 劣势：查找 O(N)，因为只能从头遍历。
3. 平衡二叉搜索树 (如 AVL 树、红黑树)：
   • 优势：查找、插入、删除操作的平均和最坏时间复杂度都是 O(log N)。
   • 劣势：
     • 实现复杂，维护平衡需要进行旋转和颜色调整等复杂操作。
     • 在并发环境下，实现无锁或细粒度锁的平衡二叉树非常困难，容易引入复杂性或性能瓶颈。

跳表的出现，正是为了在实现难度和性能之间找到一个平衡点。它拥有平衡二叉搜索树相似的性能，但实现起来要简单得多，并且更易于进行并发控制。

二、跳表的核心概念

2.1 多层链表 (Multi-level Linked List)

跳表的核心思想是在一个基本的有序链表之上，构建多层“快速通道”索引。

• 底层 (Level 0)：最底层是一个完整的有序链表，包含所有元素。
• 上层 (Level 1, Level 2, …)：每一层都是其下一层的一个“子序列”，跳过了一些元素。层数越高，链表中的元素越少，节点之间的“跳跃”距离越大。
• 头节点 (Head Node)：通常有一个特殊的头节点，它包含指向每一层起始节点的指针。

2.2 随机高度 (Random Height)

跳表使用一种随机化算法来决定每个节点会“晋升”到多少层。这是跳表能够保持平衡（即 O(log N) 性能）的关键。

• 机制：当插入一个新节点时，会通过抛硬币（或生成随机数）的方式，决定这个节点除了在 Level 0 外，还会出现在 Level 1, Level 2, … 等哪些更高的层。
• 概率：通常，一个节点有 1/2 的概率出现在 Level 1，有 1/4 的概率出现在 Level 2，有 1/8 的概率出现在 Level 3，以此类推。这意味着层数越高的链表，节点越稀疏。
• 最大层数 (Max Level)：为了避免无限高，通常会设置一个最大层数限制 (例如 32 或 64)。

2.3 节点结构

跳表中的每个节点至少包含以下信息：

• value (或 key)：节点存储的实际数据。
• forward 数组 (或 next 指针数组)：一个指针数组，forward[i] 指向当前节点在第 i 层上的下一个节点。数组的大小就是该节点的高度。

跳表结构示意图

说明：图中的 H 是头节点，A1 (值为 10) 是一个高层节点，它出现在 Level 0, 1, 2, 3。B1 (值为 20) 出现在 Level 0, 1, 2。C1 (值为 30) 出现在 Level 0, 1。D1 (值为 40) 和 E1 (值为 50) 只出现在 Level 0。ZZZ 代表链表末尾的 nil。

三、跳表的基本操作原理

跳表支持三种主要操作：搜索 (Search)、插入 (Insert) 和删除 (Delete)。

3.1 搜索 (Search) 操作

搜索一个值 target 的过程类似于在一个单链表上进行二分查找：

1. 从最高层开始：从头节点的最高层指针开始。
2. 向右查找：在当前层，沿着 forward 指针向右遍历，直到找到第一个节点，其值大于或等于 target。
3. 向下移动：如果找到的节点值等于 target，则搜索成功。如果找到的节点值大于 target，或者已经到达当前层的末尾，则从前一个节点（即值小于 target 的最右侧节点）开始，向下移动一层，重复步骤 2。
4. 到达 Level 0：重复上述过程，直到到达 Level 0。如果在 Level 0 找到了 target，则搜索成功；否则，target 不存在。

3.2 插入 (Insert) 操作

插入一个新值 newValue 的步骤：

1. 搜索插入点：首先执行一次搜索操作，找出在每一层上，newValue 应该插入到哪个节点之后。将这些节点记录在一个 update 数组中。
2. 随机决定新节点高度：通过随机算法（抛硬币），确定新节点的高度 newLevel。如果 newLevel 大于当前跳表的最高层数，则更新跳表的最高层数，并调整 update 数组。
3. 创建新节点：创建具有 newValue 和 newLevel 高度的新节点。
4. 链接新节点：从 Level 0 到 newLevel，遍历 update 数组。对于每一层 i：
   • 将新节点的 forward[i] 指向 update[i] 原本指向的节点。
   • 将 update[i] 的 forward[i] 指向新节点。

3.3 删除 (Delete) 操作

删除一个值 target 的步骤：

1. 搜索目标节点：执行一次搜索操作，找出 target 节点在每一层的前一个节点。将这些节点记录在 update 数组中。
2. 判断是否存在：如果在 Level 0 找到了 target 节点，则表示 target 存在。
3. 解除链接：从 Level 0 到跳表的最高层数，遍历 update 数组。对于每一层 i：
   • 如果 update[i] 指向 target 节点，则将 update[i] 的 forward[i] 指向 target 的 forward[i] (即跳过 target)。
4. 更新跳表高度：检查跳表的最高层，如果头节点在该层不再有任何节点（即该层只剩头节点），则降低跳表的最高层数。

四、时间与空间复杂度分析

4.1 时间复杂度

• 搜索、插入、删除：
  • 平均情况：O(log N)
  • 最坏情况：O(N) (理论上可能出现所有节点高度都相同或高度分布极其不均匀，但概率极低)
• 原因：由于随机化的层级结构，每次向上移动或向右跳跃都有效地将搜索空间减半或减少一个常数因子，从而达到对数级的性能。

4.2 空间复杂度

• 平均情况：O(N)
• 原因：每个节点平均会出现在 $1 + 1/2 + 1/4 + \dots \approx 2$ 层。因此，总的指针数量是线性的，总空间占用也是线性的。

五、跳表与平衡二叉树的比较

特性	跳表 (Skip List)	平衡二叉树 (AVL / 红黑树)
平均复杂度	O(log N)	O(log N)
最坏复杂度	O(N) (概率极低)	O(log N)
实现难度	相对简单 (基于链表和随机数)	复杂 (涉及旋转、颜色调整等)
内存占用	略高 (每个节点多指针)	略低 (通常每个节点 2 个指针)
并发控制	相对容易实现无锁或细粒度锁	极其困难，容易引入复杂性或性能瓶颈
有序遍历	简单，直接遍历最底层链表	中序遍历

结论：在需要高性能并发控制和实现简洁性的场景下，跳表往往是比平衡二叉树更好的选择。

六、跳表的并发控制

这是跳表的一大亮点。由于其链式结构和随机化特性，它比平衡二叉树更容易实现高效的并发。

• 无锁 (Lock-Free) 实现：
  • 可以通过原子操作 (CAS, Compare-And-Swap) 来实现无锁的跳表。
  • 在插入和删除时，只需要更新局部指针，而不会像平衡二叉树那样引起全局的结构性调整。
  • 这使得不同的线程可以同时修改跳表的不同部分，大大提高了并发性能。
• 读写锁 (Read-Write Lock)：
  • 也可以使用读写锁，读操作之间不互斥，写操作与读写操作互斥。
  • 由于跳表的读操作通常只修改一个 update 数组，写操作也只修改几个指针，锁的粒度可以很细。

七、实际应用

跳表在工业界有很多成功的应用：

1. Redis (键值存储)：
   • Redis 的有序集合 (Sorted Set) 底层就使用了跳表。
   • 有序集合需要同时支持快速按分数范围查找、按排名查找以及插入/删除操作，跳表是完美的匹配。
2. LevelDB / RocksDB (键值存储)：
   • 这些嵌入式 KV 存储引擎内部的 MemTable（内存表）通常使用跳表来存储和维护有序数据。
   • MemTable 频繁进行插入、查找，且需要高效地迭代，跳表非常适合。
3. 其他数据库和分布式系统：
   • 一些数据库索引、分布式缓存等也可能采用跳表或其变种来实现高性能的有序数据管理。

八、Go 语言实现示例 (简化版)

以下是一个简化版的 Go 语言跳表实现，主要展示其核心结构和查找逻辑。为了简洁，省略了并发安全和一些边缘情况处理。

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const MAX_LEVEL = 16 // 跳表的最大层数
const P = 0.5        // 节点晋升的概率

// Node 表示跳表中的一个节点
type Node struct {
	value   int
	forward []*Node // forward[i] 指向在第 i 层上的下一个节点
}

// SkipList 表示跳表本身
type SkipList struct {
	head  *Node // 头节点
	level int   // 跳表当前的最大层数
	count int   // 元素数量
}

// NewSkipList 创建一个新的跳表
func NewSkipList() *SkipList {
	// 头节点的值不重要，其forward指针数组的大小是MAX_LEVEL
	head := &Node{
		value:   -1, // 哨兵值
		forward: make([]*Node, MAX_LEVEL),
	}
	return &SkipList{
		head:  head,
		level: 0,
		count: 0,
	}
}

// randomLevel 随机生成新节点的高度
func (sl *SkipList) randomLevel() int {
	level := 0
	for rand.Float64() < P && level < MAX_LEVEL-1 { // P=0.5 意味着 1/2 概率升一级
		level++
	}
	return level
}

// Insert 插入一个值到跳表
func (sl *SkipList) Insert(value int) {
	update := make([]*Node, MAX_LEVEL) // 记录每一层需要更新的节点

	current := sl.head
	// 从最高层开始查找插入点
	for i := sl.level; i >= 0; i-- {
		for current.forward[i] != nil && current.forward[i].value < value {
			current = current.forward[i]
		}
		update[i] = current // 记录当前层需要更新的节点
	}

	// current 现在是Level 0上，插入点的前一个节点
	// 检查是否已经存在该值
	current = current.forward[0]
	if current != nil && current.value == value {
		// 值已存在，可以选择更新或直接返回
		// fmt.Printf("Value %d already exists.\n", value)
		return
	}

	// 随机生成新节点的高度
	newLevel := sl.randomLevel()
	if newLevel > sl.level {
		// 如果新节点的高度超过了当前跳表的最高层，需要更新update数组
		for i := sl.level + 1; i <= newLevel; i++ {
			update[i] = sl.head // 新的更高层，头节点是唯一的前置节点
		}
		sl.level = newLevel // 更新跳表的最高层数
	}

	// 创建新节点
	newNode := &Node{
		value:   value,
		forward: make([]*Node, newLevel+1), // 节点的高度决定了其forward数组的大小
	}

	// 链接新节点
	for i := 0; i <= newLevel; i++ {
		newNode.forward[i] = update[i].forward[i]
		update[i].forward[i] = newNode
	}
	sl.count++
}

// Search 搜索跳表中的一个值
func (sl *SkipList) Search(value int) *Node {
	current := sl.head
	// 从最高层开始查找
	for i := sl.level; i >= 0; i-- {
		for current.forward[i] != nil && current.forward[i].value < value {
			current = current.forward[i]
		}
	}
	// 移动到Level 0，检查下一个节点是否是目标值
	current = current.forward[0]
	if current != nil && current.value == value {
		return current
	}
	return nil
}

// Delete 从跳表中删除一个值
func (sl *SkipList) Delete(value int) {
	update := make([]*Node, MAX_LEVEL)
	current := sl.head

	for i := sl.level; i >= 0; i-- {
		for current.forward[i] != nil && current.forward[i].value < value {
			current = current.forward[i]
		}
		update[i] = current
	}

	current = current.forward[0] // 待删除的节点
	if current != nil && current.value == value {
		// 找到目标节点，进行删除
		for i := 0; i <= sl.level; i++ {
			if update[i].forward[i] != current { // 如果update[i]的下一个不是当前节点，说明当前层没有这个节点，跳过
				continue
			}
			update[i].forward[i] = current.forward[i] // 跳过当前节点
		}

		// 检查并更新跳表的最高层数
		for sl.level > 0 && sl.head.forward[sl.level] == nil {
			sl.level--
		}
		sl.count--
	}
}

// Print 打印跳表内容（最底层）
func (sl *SkipList) Print() {
	fmt.Print("SkipList (Level 0): ")
	current := sl.head.forward[0]
	for current != nil {
		fmt.Printf("%d -> ", current.value)
		current = current.forward[0]
	}
	fmt.Println("nil")
}

func main() {
	rand.Seed(time.Now().UnixNano()) // 初始化随机数种子

	sl := NewSkipList()
	values := []int{30, 10, 50, 20, 40, 60, 5, 25, 35, 15}

	fmt.Println("--- 插入操作 ---")
	for _, v := range values {
		sl.Insert(v)
		fmt.Printf("插入 %d. 当前元素数量: %d, 最高层: %d\n", v, sl.count, sl.level)
	}
	sl.Print()

	fmt.Println("\n--- 搜索操作 ---")
	searchValues := []int{20, 55, 30, 5}
	for _, v := range searchValues {
		node := sl.Search(v)
		if node != nil {
			fmt.Printf("找到值: %d\n", v)
		} else {
			fmt.Printf("未找到值: %d\n", v)
		}
	}

	fmt.Println("\n--- 删除操作 ---")
	deleteValues := []int{30, 5, 100}
	for _, v := range deleteValues {
		sl.Delete(v)
		fmt.Printf("删除 %d. 当前元素数量: %d, 最高层: %d\n", v, sl.count, sl.level)
		sl.Print()
	}

	fmt.Println("\n--- 最终跳表 ---")
	sl.Print()
}

示例解读：

• Node 结构：包含 value 和 forward 数组，forward[i] 指向第 i 层的下一个节点。
• SkipList 结构：包含 head 节点、当前跳表的 level (最高层数) 和 count (元素数量)。
• randomLevel()：通过 rand.Float64() < P 来模拟抛硬币，决定节点的高度。
• Insert()：
  • 首先通过从高层向低层查找，构建 update 数组，记录每一层插入点的前一个节点。
  • 然后随机生成新节点的高度，并更新跳表的 level。
  • 最后，从 Level 0 到 newLevel，调整指针，将新节点链接到跳表中。
• Search()：从最高层开始，向右查找，然后向下移动，直到在 Level 0 找到或确认不存在。
• Delete()：与 Insert 类似，先找到待删除节点的前驱节点，然后解除链接，并可能更新跳表的 level。
• Print()：只打印最底层 (Level 0) 的内容，方便查看跳表的有序性。

九、总结

跳表是一种兼具高效性能和实现简洁性的概率性数据结构。它通过多层链表和随机高度的巧妙设计，在平均情况下实现了与平衡二叉树相同的时间复杂度，但在并发场景下展现出更优越的控制能力。理解跳表的核心原理和其在实际系统中的应用，对于设计高性能、高并发的数据存储和检索系统至关重要。