跳表数据结构
目录
跳表数据结构
跳表（Skip List）是一种 支持高效插入、删除和查找 的 链表结构 ，用于加速查找操作，特别适用于 有序数据集合 。它在 Redis、LevelDB 等系统中被用于**有序集合（Sorted Set）**的实现。
1. 跳表的结构
跳表的核心思想是：
在链表的基础上，引入多级索引，类似于高速公路的匝道，提高查找效率。
一个跳表通常由多层索引构成：
- 最底层（Level 0） 是一个 有序单链表 ，存储所有数据；
- 上层索引（Level > 0） 由 部分节点 构成，起到“跳跃”的作用，加速查找；
- 最上层索引 由 少量节点 构成，使得查找可以迅速缩小范围。
示例跳表（3 层）：
Level 2: 1 --------------> 9 ----------------> 19
Level 1: 1 ----> 5 -----> 9 ----> 13 -------> 19
Level 0: 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19每一层都是上一层的子集，节点的“晋升”是 概率性 的（通常是 1/2）。
2. 跳表的基本操作
查找
跳表的查找过程类似于二分查找：
- 从最高层索引 开始，查找小于目标值的最大节点；
- 向下移动 到下一层索引，继续查找；
- 直到底层 （Level 0），最终在普通链表中找到目标节点或确认其不存在。
时间复杂度：
O ( log n ) O(\log n)
O
(
lo g
n
) —— 因为跳表的高度是 O(log n) ，查找路径长度也大约是 O(log n) 。
插入
- 查找插入位置 ，找到前驱节点；
- 随机决定新节点的层数 （常见做法：掷硬币，每次有 50% 概率提升一层）；
- 在每一层进行插入 ，更新索引。
时间复杂度：
- 平均 O(log n) ，因为最多遍历 log n 层；
- 最坏 O(n) （所有元素都在同一层）。
删除
- 查找目标节点 （与查找操作类似）；
- 在每一层移除节点 ；
- 如果某层为空，则删除该层 。
时间复杂度：
O ( log n ) O(\log n)
O
(
lo g
n
)
3. 跳表 vs. 其他数据结构
| 数据结构 | 查找时间复杂度 | 插入时间复杂度 | 删除时间复杂度 | 额外空间 | 适用场景 |
|---|---|---|---|---|---|
| 跳表 | O(log n) | O(log n) | O(log n) | O(n) | 有序数据、高效查找 |
| 平衡二叉搜索树 (AVL, 红黑树) | O(log n) | O(log n) | O(log n) | O(n) | 适用于动态数据 |
| 哈希表 | O(1) | O(1) | O(1) | O(n) | 适用于无序数据、频繁查询 |
| 链表 | O(n) | O(1) | O(n) | O(n) | 适用于插入、删除较多 |
跳表 vs. 红黑树
- 跳表实现更简单 ，只需维护索引，而红黑树需要复杂的旋转操作；
- 跳表在分布式环境中更友好 ，如 Redis 的有序集合（ZSet）采用跳表；
- 红黑树适用于内存受限的场景 ，因为跳表的索引层需要额外存储空间。
4. 实际应用
Redis
Redis 有序集合（Sorted Set） 的底层结构是 跳表 + 哈希表 ：
- 跳表：用于
范围查询
（
ZRANGE、ZREVRANGE） - 哈希表：用于
O(1) 查找
（
ZADD）
LevelDB
Google 的 LevelDB 用跳表存储 MemTable ，然后刷盘成 SSTable 。
5. 代码实现（Java）
跳表节点
class SkipListNode {
int val;
SkipListNode[] next; // 指向不同层级的下一个节点
public SkipListNode(int val, int level) {
this.val = val;
this.next = new SkipListNode[level];
}
}跳表类
import java.util.Random;
class SkipList {
private static final int MAX_LEVEL = 16; // 最大层数
private final SkipListNode head; // 头节点
private int levelCount = 1; // 当前最大层数
private final Random random = new Random();
public SkipList() {
head = new SkipListNode(-1, MAX_LEVEL); // 初始化头节点
}
// 查找
public boolean search(int target) {
SkipListNode cur = head;
for (int i = levelCount - 1; i >= 0; i--) {
while (cur.next[i] != null && cur.next[i].val < target) {
cur = cur.next[i];
}
}
cur = cur.next[0]; // 进入最底层
return cur != null && cur.val == target;
}
// 插入
public void insert(int num) {
SkipListNode[] update = new SkipListNode[MAX_LEVEL]; // 记录每层的前驱节点
SkipListNode cur = head;
for (int i = levelCount - 1; i >= 0; i--) {
while (cur.next[i] != null && cur.next[i].val < num) {
cur = cur.next[i];
}
update[i] = cur; // 记录前驱节点
}
int newLevel = randomLevel();
levelCount = Math.max(levelCount, newLevel);
SkipListNode newNode = new SkipListNode(num, newLevel);
for (int i = 0; i < newLevel; i++) {
newNode.next[i] = update[i].next[i];
update[i].next[i] = newNode;
}
}
// 删除
public void delete(int num) {
SkipListNode cur = head;
SkipListNode[] update = new SkipListNode[MAX_LEVEL];
for (int i = levelCount - 1; i >= 0; i--) {
while (cur.next[i] != null && cur.next[i].val < num) {
cur = cur.next[i];
}
update[i] = cur;
}
SkipListNode target = cur.next[0];
if (target == null || target.val != num) return;
for (int i = 0; i < levelCount; i++) {
if (update[i].next[i] != target) break;
update[i].next[i] = target.next[i];
}
}
// 随机生成层数
private int randomLevel() {
int level = 1;
while (random.nextDouble() < 0.5 && level < MAX_LEVEL) {
level++;
}
return level;
}
}6. 总结
- 跳表通过多层索引加速查询 ，时间复杂度接近 O(log n) ；
- 插入/删除时动态调整索引 ，比红黑树实现简单；
- Redis、LevelDB 等系统采用跳表 ，适用于 有序集合、范围查询 等场景；
- 比红黑树占用更多空间 ，但 更适合并发和分布式环境 。