Redis 跳表原理详解

一、引言

在 Redis 中，有序集合（Sorted Set）是一种非常重要的数据结构，它可以实现元素的有序存储和高效查找。而实现有序集合的底层数据结构之一就是跳表（Skip List）。跳表是一种随机化的数据结构，它通过在链表的基础上增加多层索引来提高查找效率。本文将详细介绍 Redis 跳表的原理，并结合图文进行说明。

二、链表的局限性

在介绍跳表之前，我们先来回顾一下普通链表的查找操作。假设我们有一个有序链表，要查找其中的某个元素，需要从链表的头节点开始，依次遍历每个节点，直到找到目标元素或者遍历到链表的末尾。这种查找方式的时间复杂度是 (O(n))，其中 n 是链表的长度。当链表长度很大时，查找效率会非常低。

下面是一个简单的有序链表示例：

+---+    +---+    +---+    +---+
| 1 | -> | 3 | -> | 5 | -> | 7 |
+---+    +---+    +---+    +---+

如果要查找元素 5，需要从头节点开始，依次比较 1、3，直到找到 5，总共需要比较 3 次。

三、跳表的基本思想

跳表的基本思想是在链表的基础上增加多层索引，通过这些索引可以快速跳过一些不必要的节点，从而减少查找的时间复杂度。具体来说，跳表会为每个节点随机分配一个层数，层数越高的节点越稀疏。在查找时，从最高层的索引开始，快速定位到一个大致的范围，然后逐渐向下层移动，直到找到目标节点或者确定目标节点不存在。

下面是一个简单的跳表示例：

Level 3: +---------------------+|                     |v                     v
Level 2: +---+         +---+    +---+| 1 | -------> | 5 | -> | 7 |+---+         +---+    +---+|             |        |v             v        v
Level 1: +---+    +---+ +---+    +---+| 1 | -> | 3 | | 5 | -> | 7 |+---+    +---+ +---+    +---+

在这个跳表中，有三层索引。当我们要查找元素 5 时，从最高层（Level 3）开始，由于最高层只有一个节点 1，它小于 5，所以继续在这一层向右查找，发现没有其他节点了，于是向下移动到 Level 2。在 Level 2 中，节点 1 小于 5，继续向右查找，找到节点 5，此时已经找到了目标元素，查找结束。总共只需要比较 2 次，比普通链表的查找效率更高。

四、跳表的结构

节点结构

Redis 跳表的节点结构包含以下几个部分：

成员对象（member）：即有序集合中的元素，是一个字符串对象。
分值（score）：用于对元素进行排序的数值，类型为双精度浮点数。
后退指针（backward）：指向前一个节点，用于从后向前遍历跳表。
层（level）：每个节点包含多个层，每层都有一个前进指针（forward）和一个跨度（span）。前进指针指向下一个节点，跨度表示从当前节点到下一个节点跨越的节点数量。

下面是一个简化的节点结构示意图：

+-----------------+
| member: "apple" |
| score: 3.5      |
| backward: prev  |
| level: [        |
|   { forward: n1, span: 2 }, |
|   { forward: n2, span: 3 }, |
|   ...                      |
| ]               |
+-----------------+

跳表结构

Redis 跳表由一个头节点和一个尾节点组成，头节点的层数通常是最大层数，尾节点的分值为正无穷大。跳表还记录了节点的数量和最大层数。

下面是一个简化的跳表结构示意图：

+-----------------+
| header:         |
|   level: [      |
|     { forward: n1, span: 1 }, |
|     { forward: n2, span: 2 }, |
|     ...                      |
|   ]               |
| length: 5        |
| level: 3         |
+-----------------+

五、跳表的操作

查找操作

查找操作是跳表的核心操作之一。具体步骤如下：

从最高层的链表开始，沿着当前层的链表向前比较节点的分值。如果当前节点的下一个节点的分值小于目标分值，则继续在当前层向前移动；如果下一个节点的分值大于目标分值，则向下移动一层。
重复步骤 1，直到找到目标节点或者到达底层链表且遍历完所有可能的节点。

下面是一个查找元素的示例：

Level 3: +---------------------+|                     |v                     v
Level 2: +---+         +---+    +---+| 1 | -------> | 5 | -> | 7 |+---+         +---+    +---+|             |        |v             v        v
Level 1: +---+    +---+ +---+    +---+| 1 | -> | 3 | | 5 | -> | 7 |+---+    +---+ +---+    +---+查找元素 5：
1. 从 Level 3 开始，头节点 1 小于 5，继续向右查找，没有其他节点，向下移动到 Level 2。
2. 在 Level 2 中，节点 1 小于 5，继续向右查找，找到节点 5，查找结束。

插入操作

插入操作的步骤如下：

按照查找操作的方式，找到要插入的位置。
在底层链表中插入新节点。
根据一定的概率决定是否将新节点提升到更高层。通常，一个节点有 1/2 的概率出现在第 1 层，有 1/4 的概率出现在第 2 层，有 1/8 的概率出现在第 3 层，依此类推。

下面是一个插入元素的示例：

原始跳表：
Level 2: +---+         +---+    +---+| 1 | -------> | 5 | -> | 7 |+---+         +---+    +---+|             |        |v             v        v
Level 1: +---+    +---+ +---+    +---+| 1 | -> | 3 | | 5 | -> | 7 |+---+    +---+ +---+    +---+插入元素 4：
1. 按照查找操作，找到插入位置在 3 和 5 之间。
2. 在底层链表中插入节点 4。
3. 假设节点 4 有 1/2 的概率提升到第 2 层，这里假设提升成功。插入后的跳表：
Level 2: +---+    +---+    +---+    +---+| 1 | -> | 4 | -> | 5 | -> | 7 |+---+    +---+    +---+    +---+|        |        |        |v        v        v        v
Level 1: +---+    +---+    +---+    +---+    +---+| 1 | -> | 3 | -> | 4 | -> | 5 | -> | 7 |+---+    +---+    +---+    +---+    +---+

删除操作

删除操作的步骤如下：

按照查找操作的方式，找到要删除的节点。
将该节点从每一层链表中移除，并更新相应的指针。

下面是一个删除元素的示例：

原始跳表：
Level 2: +---+    +---+    +---+    +---+| 1 | -> | 4 | -> | 5 | -> | 7 |+---+    +---+    +---+    +---+|        |        |        |v        v        v        v
Level 1: +---+    +---+    +---+    +---+    +---+| 1 | -> | 3 | -> | 4 | -> | 5 | -> | 7 |+---+    +---+    +---+    +---+    +---+删除元素 4：
1. 按照查找操作，找到节点 4。
2. 将节点 4 从每一层链表中移除，并更新指针。删除后的跳表：
Level 2: +---+         +---+    +---+| 1 | -------> | 5 | -> | 7 |+---+         +---+    +---+|             |        |v             v        v
Level 1: +---+    +---+ +---+    +---+| 1 | -> | 3 | | 5 | -> | 7 |+---+    +---+ +---+    +---+

六、跳表的复杂度分析

时间复杂度

跳表的查找、插入和删除操作的平均时间复杂度都是 (O(log n))，其中 n 是跳表中节点的数量。这是因为跳表通过多层索引的方式，每次可以跳过一部分节点，使得查找过程类似于二分查找，从而将时间复杂度从普通链表的(O(n)) 降低到了 (O(log n))。

空间复杂度

跳表的空间复杂度是 (O(n))，因为每个节点除了存储本身的数据外，还需要额外的指针来维护多层索引。不过，由于每个节点的层数是随机分配的，平均情况下每个节点的层数是常数级别的，所以空间复杂度仍然是线性的。

七、场景应用

跳表（Skip List）因其高效的动态操作（插入、删除、查询均为 O (log n) 平均时间复杂度）和实现简单性，被广泛应用于以下场景：

1. 数据库索引

LevelDB/RocksDB：
Google 开发的高性能键值存储引擎 LevelDB 及其衍生项目 RocksDB，均使用跳表（称为 SkipList）作为内存索引结构（MemTable）。跳表的有序性和高效插入删除能力，使其适合管理高频更新的内存数据。
HBase：
HBase 的内存存储组件 MemStore 底层也依赖跳表实现，用于快速查询和维护数据。

2. 分布式系统

Apache Kafka：
Kafka 的日志分段索引（LogSegment）使用跳表来维护偏移量（Offset）到物理位置的映射，确保消息的有序性和快速检索。
Consistent Hashing：
跳表可用于分布式哈希表（DHT）的一致性哈希环管理，支持节点动态加入 / 退出时的高效调整。

3. 网络设备

路由表管理：
网络设备（如路由器）的路由表需高效匹配目的 IP，跳表的多层索引结构可加速最长前缀匹配（Longest Prefix Match）。
Nginx 负载均衡：
Nginx 的一致性哈希负载均衡算法中，跳表被用于维护虚拟节点的有序分布。

4. 编程语言与框架

Java ConcurrentSkipListMap：
Java 并发包中的 ConcurrentSkipListMap 基于跳表实现，提供线程安全的有序键值存储，适合高并发场景。
Python 的 sortedcontainers 库：
第三方库 sortedcontainers 中的 SortedList 基于跳表，支持高效的插入、删除和排序操作。

5. 文件系统与存储

元数据管理：
分布式文件系统（如 Ceph）的元数据服务器（MDS）可能使用跳表管理目录结构或文件属性的有序索引。
日志结构化存储：
日志系统（如 ELK Stack）的索引层可能借助跳表优化日志查询性能。

6. 其他场景

游戏开发：
用于管理游戏对象的空间索引（如二维网格中的动态碰撞检测）。
区块链：
某些区块链项目（如 Hyperledger Fabric）的账本索引可能采用跳表优化交易查询。

跳表的优势与适用场景总结

场景	跳表优势
动态数据管理	插入、删除高效，无需频繁调整树结构（对比红黑树）。
并发场景	实现简单，锁粒度小（如无锁跳表），适合高并发环境。
有序数据结构需求	天然支持有序遍历，无需额外排序操作。
内存敏感场景	相比平衡树，跳表的节点结构更简单，内存占用较低。

对比：跳表 vs 平衡二叉树

特性	跳表	平衡二叉树（如红黑树）
时间复杂度	平均 O (log n)，最坏 O (n)	平均 / 最坏均为 O (log n)
实现难度	简单，无需复杂的旋转操作	复杂，需维护平衡因子
并发支持	容易实现无锁或细粒度锁	锁粒度较大，并发性能受限
适用场景	动态数据、高并发、内存敏感	静态数据、低并发、需要严格 O (log n) 保证