skiplist跳表原理及实现(跳表原理与实现)

跳表（Skip List）：平衡二叉树的优雅替代者——原理深度解析与实现

在高性能数据结构的世界中，红黑树（Red-Black Tree）和 AVL 树常常被视为有序集合的标准实现。然而，在 Redis 的 ZSet、LevelDB 的 SSTable 等知名系统中，我们却能看到另一种结构的身影——跳表（Skip List）。 为什么在树结构如此成熟的今天，跳表依然占据一席之地？本文将从原理、复杂度分析到代码实现，带你深入理解跳表这一“看似简单，实则精妙”的数据结构。

---

1. 什么是跳表？

跳表是一种概率性平衡的多层链表结构。它通过在每个节点中维护多个指向后继节点的指针（即“层”），使得在查找、插入和删除操作时，能够跳过大量不必要的节点，从而将对数级的时间复杂度控制在 。

核心思想：二分查找的链表化

想象一下你在一个巨大的有序数组中查找某个元素。如果使用线性扫描，复杂度是 ；如果使用二分查找，复杂度是 。但二分查找依赖随机访问，链表不支持。 跳表的核心灵感正是将二分查找的思想应用到链表上： 1. 建立多层链表。 2. 高层链表包含的节点较少，但跨度大，用于快速“跳跃”。 3. 底层链表包含所有节点，用于精确匹配。

---

2. 跳表的结构与原理

2.1 层级结构

一个典型的跳表由多层链表组成：

• 第 0 层（底层）：包含所有数据节点，构成一个完整的有序链表。
• 第 1 层及以上：是第 0 层的“快速通道”。第 层的节点是第 层节点的子集。

2.2 节点结构

每个节点包含：

• Value：存储的实际数据。
• Forward 数组：一个指针数组，`forward[i]` 指向第 层链表中该节点的直接后继节点。

```text Node: value: int forward: [Pointer, Pointer, Pointer, ...] ```

2.3 随机化高度

跳表是概率平衡的。新插入节点的高度不是固定的，而是通过随机算法决定。

• 通常做法：以 50% 的概率，节点高度增加 1。
• 例如：生成一个随机数，如果为偶数，高度+1，继续判断，直到为奇数为止。
• 这种随机性保证了跳表在统计意义上保持平衡，无需像红黑树那样进行复杂的旋转操作。

---

3. 核心操作详解

3.1 查找操作（Search）

查找过程类似于二分查找，从最高层开始： 1. 从最高层的头节点（Head）开始。 2. 比较当前节点后继的值与目标值：

• 如果后继值 小于 目标值，则沿当前层向右移动（`forward`）。
• 如果后继值 大于或等于 目标值，则沿当前层向下移动（`down` 到下一层），并在下一层继续比较。

3. 重复直到到达第 0 层。 4. 在第 0 层检查是否找到目标值。 时间复杂度：由于每层大约覆盖一半的节点，查找过程类似于二分查找，期望时间为 。

3.2 插入操作（Insert）

插入分为两步： 1. 查找插入位置：

• 使用与查找相同的逻辑，记录每一层中最后一个小于目标值的节点（即前驱节点）。
• 生成一个随机高度 `level`。

2. 更新指针：

• 创建新节点，高度为 `level`。
• 对于每一层 （从 0 到 `level-1`）：
• 如果前驱节点在第 层存在，则将新节点插入到前驱节点之后。
• 如果前驱节点在第 层不存在（即前驱节点高度小于 ），则从当前层的头节点开始查找该层的前驱。

时间复杂度：查找位置 ，插入操作 （假设已找到位置），总体期望 。

3.3 删除操作（Delete）

删除类似插入： 1. 查找节点：确认节点存在，并记录每一层的前驱节点。 2. 更新指针：

• 对于每一层，将前驱节点的 `forward` 指针指向待删除节点的后继。
• 释放节点内存。

时间复杂度：。

---

4. 跳表 vs. 平衡二叉树

特性	跳表 (Skip List)	平衡二叉树 (Red-Black/AVL)
实现复杂度	低，代码简洁，易于维护	高，需处理旋转、颜色等复杂逻辑
并发友好性	高，细粒度锁，适合多线程	低，通常需整树锁或复杂锁机制
范围查询	优秀，底层链表天然支持顺序遍历	一般，需中序遍历
缓存局部性	较差，节点分散在堆中	较好，节点相对集中
最坏情况	概率极小（指数级下降）	严格保证

结论：在需要高并发、范围查询频繁的场景下（如 Redis），跳表更具优势；在对内存敏感且追求严格最坏情况保证的场景下，平衡树更合适。

---

5. Python 实现

下面是一个简洁、可运行的跳表 Python 实现，包含查找、插入和删除功能。 ```python import random class SkipListNode: def init(self, value, level): self.value = value # forward[i] 指向第 i 层的前驱节点 self.forward = [None] (level + 1) class SkipList: def init(self, max_level=4, p=0.5): self.max_level = max_level self.p = p self.head = SkipListNode(None, max_level) self.level = 0 # 当前跳表的实际高度 def _random_level(self): """生成随机高度，以概率 p 增加层级""" lvl = 0 while random.random() < self.p and lvl < self.max_level: lvl += 1 return lvl def search(self, target): """查找目标值""" node = self.head # 从最高层开始查找 for i in range(self.level, -1, -1): while node.forward[i] and node.forward[i].value < target: node = node.forward[i] # 移动到下一层的前驱节点 node = node.forward[0] return node if node and node.value target else None def insert(self, value): """插入新值""" update = [None] (self.max_level + 1) node = self.head # 1. 查找插入位置，并记录每一层的前驱节点 for i in range(self.level, -1, -1): while node.forward[i] and node.forward[i].value < value: node = node.forward[i] update[i] = node node = node.forward[0] # 如果值已存在，不插入（假设唯一键） if node and node.value value: return # 2. 生成随机高度 new_level = self._random_level() # 如果新高度超过当前最大高度，更新头节点 if new_level > self.level: for i in range(self.level + 1, new_level + 1): update[i] = self.head self.level = new_level # 3. 创建新节点并更新指针 new_node = SkipListNode(value, new_level) for i in range(new_level + 1): new_node.forward[i] = update[i].forward[i] update[i].forward[i] = new_node def delete(self, target): """删除目标值""" update = [None] (self.max_level + 1) node = self.head # 1. 查找节点及前驱 for i in range(self.level, -1, -1): while node.forward[i] and node.forward[i].value < target: node = node.forward[i] update[i] = node node = node.forward[0] # 如果节点不存在，直接返回 if not node or node.value != target: return False # 2. 更新指针，跳过该节点 for i in range(self.level + 1): if update[i].forward[i] is node: update[i].forward[i] = node.forward[i] # 3. 清理空层 while self.level > 0 and self.head.forward[self.level] is None: self.level -= 1 return True def display(self): """可视化跳表结构""" for i in range(self.level, -1, -1): node = self.head.forward[i] layer_values = [] while node: layer_values.append(node.value) node = node.forward[i] print(f"Layer {i}: {layer_values}") ```

测试示例

```python if name "main": sl = SkipList(max_level=4) # 插入数据 for val in [3, 7, 1, 9, 2, 5, 8, 4, 6]: sl.insert(val) print("插入后跳表结构:") sl.display() # 查找 print(f"nSearch 5: {sl.search(5).value if sl.search(5) else 'Not Found'}") print(f"Search 10: {sl.search(10)}") # 删除 sl.delete(5) print("n删除 5 后:") sl.display() ```

---

6. 总结

跳表以其简洁的实现、高效的性能和对并发的天然友好性，成为现代高性能系统中不可或缺的数据结构。尽管它在最坏情况下的理论保证不如平衡树严格，但其概率平衡特性在实际应用中表现优异，且代码易于理解和维护。 对于开发者而言，理解跳表不仅有助于掌握一种高效的数据结构，更能启发我们在设计系统时权衡复杂度、性能与可维护性。 延伸思考：在分布式系统中，跳表的随机化特性如何影响数据分片？如果将跳表与 B+ 树结合，会诞生怎样的混合结构？这些问题值得进一步探索。