什么是跳表？（Skip List）
跳表（Skip List）完整讲解
跳表是一种基于链表的有序数据结构，通过多层索引提高查找速度。它的核心思想是：“用多个层级的索引来加速查找”，从而达到类似二分查找的效果，同时保留链表的动态性。
1. 跳表的基本概念
跳表的结构类似于一个多层高速公路：
- 底层（Level 0）是一个 有序链表，存储所有元素。
- 上层索引（Level 1、2、3…）是一些“跳跃”节点，帮助快速定位元素，就像高速公路上的“快速通道”。
- 层数越高，跳过的元素越多，查找效率越快。
示例： 假设有一组有序数据 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}，如果直接用链表存储，查找 9 需要走 9 步：
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10
如果用跳表，有多个索引层：
Level 2: 1 ------------- 5 ------------- 9
Level 1: 1 ---- 3 ---- 5 ---- 7 ---- 9 ---- 10
Level 0: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10
🔹 查找 9：
- 从
Level 2开始：1 → 5 → 9✅ 只走 2 步。 - 如果没找到，再往下到
Level 1或Level 0。
结论： ✅ 跳表比单链表快很多，查找 O(log n)，而普通链表是 O(n)。
2. 跳表的时间复杂度
| 操作 | 平均时间复杂度 | 最坏情况 |
|---|---|---|
| 查询 | O(log n) | O(n)（如果跳表退化成链表） |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
为什么是 O(log n)？
- 跳表的每层跳过一半的元素，类似二分查找。
- 如果有
n个元素，总共大约有log n层，每次查找最多经过log n步。
最坏情况：
- 如果随机化索引层失败，跳表可能会退化成普通链表，最坏情况下查找变成
O(n)。 - 但概率极低，通常不会发生。
3. 跳表的空间复杂度
- 空间复杂度：O(n) ~ O(n log n)（具体取决于索引层的个数）
- 每个元素会随机出现在多个索引层，但大部分只在底层，整体空间消耗比平衡树略高，但比完全索引（如 B+ 树）低。
4. 跳表的操作
（1）数据查询
🔹 步骤：
- 从最高索引层开始，查找接近目标值的节点。
- 如果该层的当前节点值
>= target，则往下移动一层。 - 在 底层链表（Level 0） 找到目标节点。
🔹 示例：查找 7
Level 2: 1 ------------- 5 ------------- 9
Level 1: 1 ---- 3 ---- 5 ---- 7 ---- 9 ---- 10
Level 0: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10
- 从
Level 2开始：1 → 5，发现9太大，回退到5，然后下到 Level 1。 - 在
Level 1：5 → 7，找到了7✅ 只走 2 步。
✅ 查询时间复杂度 O(log n)。
（2）数据插入
🔹 步骤：
- 从最高层往下找到要插入的位置。
- 随机生成层数（50% 概率晋升到下一层）。
- 插入新节点，并调整指针。
🔹 示例：插入 6
- 查找插入位置（在
5和7之间）。 - 随机生成层数（假设
6出现在Level 0 和 Level 1）。 - 插入
6并更新指针：
Level 1: 1 ---- 3 ---- 5 ---- 6 ---- 7 ---- 9 ---- 10
Level 0: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10
✅ 插入时间复杂度 O(log n)。
（3）数据删除
🔹 步骤：
- 从最高层向下查找目标节点。
- 删除该节点，并更新前后指针。
- 如果某一层的索引为空，则删除该层。
✅ 删除时间复杂度 O(log n)。
5. Redis 为什么使用跳表？
Redis 的有序集合（ZSet）*支持*快速插入、删除、范围查询，需要一个高效的有序数据结构**。
🔹 跳表 vs. 红黑树
| 对比项 | 跳表（Skip List） | 红黑树（Red-Black Tree） |
|---|---|---|
| 查找 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
| 删除 | O(log n) | O(log n) |
| 范围查询 | 快（链表结构遍历） ✅ | 较慢（树结构遍历） ❌ |
| 实现难度 | 简单 ✅ | 复杂（旋转、调整） ❌ |
| 插入/删除成本 | 只改指针 ✅ | 涉及旋转 ❌ |
| 空间占用 | 稍高 ❌ | 更紧凑 ✅ |
🔹 Redis 选择跳表的原因
- 范围查询更快（链表可直接遍历）。
- 代码更简单（比红黑树易实现）。
- 插入、删除操作不会有额外的平衡成本（红黑树需要旋转）。
✅ 跳表更适合 Redis 的场景，所以 Redis 有序集合（ZSet） 使用跳表 + 哈希表实现。
6. 其他工业级应用
- 数据库索引（LevelDB、RocksDB）：跳表可以用于存储引擎的索引，比 B+ 树更适合 LSM 树（Log-Structured Merge Tree）。
- 搜索引擎（Elasticsearch）：用于倒排索引的存储结构。
- 分布式存储（BigTable）：Google BigTable 采用跳表 + SSTable 结构。
7. 结论
- 跳表是“多层索引的有序链表”，查询、插入、删除都是
O(log n)。 - Redis 选择跳表而不是红黑树，因为跳表的范围查询更快、实现更简单。
- 跳表适用于高效的排序存储和索引结构，被广泛用于数据库、搜索引擎、缓存系统。