Redis常规指令及跳表
第一部分：Redis 常规指令
Redis 是一个键值存储系统，其指令通常以 COMMAND KEY_NAME [ARGUMENTS...] 的形式存在。下面我们按照数据结构和功能来分类。
1. 全局/键操作指令
这些指令不特定于某一数据类型，适用于所有键。
| 指令 | 描述 | 示例 |
|---|---|---|
KEYS pattern | 查找所有符合给定模式（pattern）的键。（生产环境慎用，会阻塞） | KEYS user:* |
EXISTS key | 检查键是否存在。 | EXISTS mykey |
TYPE key | 返回键所存储的值的类型。 | TYPE mylist |
DEL key [key ...] | 删除一个或多个键。 | DEL key1 key2 |
EXPIRE key seconds | 为键设置过期时间（单位：秒）。 | EXPIRE session:123 3600 |
TTL key | 返回键的剩余生存时间。 | TTL session:123 |
RENAME key newkey | 重命名键。 | RENAME oldkey newkey |
2. 字符串
String 是 Redis 最基本的数据类型，可以存储文本、JSON、序列化对象，甚至是二进制数据（如图片）。
| 指令 | 描述 | 示例 |
|---|---|---|
SET key value | 设置键的值。 | SET name "Alice" |
GET key | 获取键的值。 | GET name |
SETEX key seconds value | 设置键的值和过期时间（原子操作）。 | SETEX cache:page1 60 "..." |
SETNX key value | 只有键不存在时，才设置键的值（分布式锁常用）。 | SETNX lock:myjob 1 |
INCR key | 将键中存储的数字值增一。 | INCR counter |
DECR key | 将键中存储的数字值减一。 | DECR counter |
INCRBY key increment | 将键中存储的数字值增加指定的增量。 | INCRBY counter 10 |
APPEND key value | 将指定值追加到键的原始值末尾。 | APPEND greeting " World!" |
3. 哈希
Hash 是一个键值对集合，特别适合存储对象信息。例如，一个用户对象。
| 指令 | 描述 | 示例 |
|---|---|---|
HSET key field value | 设置哈希表 key 中的字段 field 的值。 | HSET user:1001 name "Bob" age 30 |
HGET key field | 获取哈希表 key 中给定字段 field 的值。 | HGET user:1001 name |
HGETALL key | 获取在哈希表 key 中的所有字段和值。 | HGETALL user:1001 |
HDEL key field [field ...] | 删除哈希表 key 中的一个或多个指定字段。 | HDEL user:1001 age |
HEXISTS key field | 查看哈希表 key 中，指定的字段是否存在。 | HEXISTS user:1001 email |
HINCRBY key field increment | 为哈希表 key 中的字段 field 的值加上增量 increment。 | HINCRBY user:1001 score 5 |
4. 列表
List 是一个字符串元素的有序集合，按插入顺序排序。底层是双向链表或快速列表（ziplist/quicklist）。
| 指令 | 描述 | 示例 |
|---|---|---|
LPUSH key value [value ...] | 将一个或多个值插入到列表头部。 | LPUSH mylist "world" "hello" |
RPUSH key value [value ...] | 将一个或多个值插入到列表尾部。 | RPUSH mylist "redis" |
LPOP key | 移除并返回列表头部元素。 | LPOP mylist |
RPOP key | 移除并返回列表尾部元素。 | RPOP mylist |
LLEN key | 获取列表长度。 | LLEN mylist |
LRANGE key start stop | 获取列表指定范围内的元素（0表示第一个，-1表示最后一个）。 | LRANGE mylist 0 -1 |
LINDEX key index | 通过索引获取列表中的元素。 | LINDEX mylist 0 |
5. 集合
Set 是一个无序、唯一的字符串元素集合。常用于标签、共同好友等场景。
| 指令 | 描述 | 示例 |
|---|---|---|
SADD key member [member ...] | 向集合添加一个或多个成员。 | SADD mytags "redis" "database" "nosql" |
SMEMBERS key | 返回集合中的所有成员。 | SMEMBERS mytags |
SISMEMBER key member | 判断成员元素是否是集合的成员。 | SISMEMBER mytags "redis" |
SREM key member [member ...] | 移除集合中一个或多个成员。 | SREM mytags "nosql" |
SCARD key | 获取集合的成员数。 | SCARD mytags |
SINTER key [key ...] | 返回给定所有集合的交集。 | SINTER set1 set2 |
SUNION key [key ...] | 返回给定所有集合的并集。 | SUNION set1 set2 |
SDIFF key [key ...] | 返回给定所有集合的差集。 | SDIFF set1 set2 |
6. 有序集合
这是跳表的核心应用场景。Sorted Set 和 Set 一样，也是元素唯一的集合。但每个元素都会关联一个 double 类型的分数。Redis 正是通过这个分数来为集合中的成员进行从小到大的排序。
| 指令 | 描述 | 示例 |
|---|---|---|
ZADD key score member [score member ...] | 向有序集合添加一个或多个成员，或更新已存在成员的分数。 | ZADD leaderboard 100 "player1" 200 "player2" |
ZRANGE key start stop [WITHSCORES] | 通过索引区间返回有序集合中指定区间内的成员（分数从低到高）。 | ZRANGE leaderboard 0 -1 WITHSCORES |
ZREVRANGE key start stop [WITHSCORES] | 通过索引区间返回有序集合中指定区间内的成员（分数从高到低）。 | ZREVRANGE leaderboard 0 2 |
ZRANK key member | 返回有序集合中指定成员的排名（分数从低到高排序）。 | ZRANK leaderboard "player2" |
ZREVRANK key member | 返回有序集合中指定成员的排名（分数从高到低排序）。 | ZREVRANK leaderboard "player2" |
ZSCORE key member | 返回有序集合中指定成员的分数值。 | ZSCORE leaderboard "player1" |
ZREM key member [member ...] | 移除有序集合中的一个或多个成员。 | ZREM leaderboard "player1" |
ZCARD key | 获取有序集合的成员数。 | ZCARD leaderboard |
ZCOUNT key min max | 计算在有序集合中指定区间分数的成员数。 | ZCOUNT leaderboard 0 150 |
第二部分：跳表
1. 什么是跳表？
跳表是一种概率平衡的数据结构，可以看作是带有“快速通道”的有序链表。它通过在原始有序链表之上建立多级索引，来实现快速的查找、插入和删除操作，其平均时间复杂度为 O(log N)，最坏情况为 O(N)。
为什么需要跳表？
- 普通有序链表的查找效率是 O(N)，因为必须从头开始逐个遍历。
- 平衡二叉树（如红黑树）虽然能实现 O(log N) 的查找，但实现复杂，且在并发环境下需要复杂的锁机制来保证平衡。
- 跳表提供了一种在实现上比平衡树更简单，且性能与之媲美的方案。
2. 跳表的底层原理
让我们通过一个例子来理解跳表是如何工作的。
第0步：原始有序链表
假设我们有一个有序链表：1 <-> 7 <-> 20 <-> 35 <-> 50 <-> 80。
如果要查找 35，我们需要从头节点 1 开始，依次比较 7, 20，最后找到 35，共比较3次。
1 -> 7 -> 20 -> 35 -> 50 -> 80
第1步：建立一级索引（“快车道”）
我们从链表中抽取部分节点（例如，每隔一个节点）组成一个新的一级索引链表。
- 索引层：
1 -> 20 -> 50 - 原始层：
1 -> 7 -> 20 -> 35 -> 50 -> 80
现在查找 35：
- 从索引层
1开始，比较20，35 > 20，继续在索引层找。 - 找到
50，35 < 50，说明35在20和50之间。 - 从索引层的
20节点下降到原始层的20节点。 - 在原始层从
20开始向后遍历，立刻找到35。
这次我们只比较了 20, 50, 35，共3次。虽然在这个小例子中优势不明显，但当数据量巨大时，效率提升是惊人的。
第2步：建立多级索引
我们可以在一级索引的基础上，再抽取部分节点建立二级索引。
- 二级索引：
1 -> 50 - 一级索引：
1 -> 20 -> 50 - 原始层：
1 -> 7 -> 20 -> 35 -> 50 -> 80
现在查找 35：
- 从二级索引
1开始，比较50，35 < 50。 - 从二级索引的
1节点下降到一级索引的1节点。 - 在一级索引从
1开始，比较20，35 > 20，继续找。 - 找到
50，35 < 50。 - 从一级索引的
20节点下降到原始层的20节点。 - 在原始层找到
35。
比较次数依然是 50, 20, 35。但想象一下，如果链表有上百万个节点，多级索引可以让你“大步跨越”，迅速缩小查找范围。
如何保持平衡？
跳表不像平衡树那样有严格的旋转规则。它通过随机函数来决定一个节点应该被提升到多少级索引。
- 当一个新节点插入时，会调用一个随机函数（例如，抛硬币）。
- 如果结果是“正面”，就将该节点提升到一级索引。
- 再次抛硬币，如果是“正面”，就提升到二级索引。
- …直到出现“反面”为止。
这种随机化的方法使得跳表在宏观上保持平衡，避免了最坏情况，同时实现非常简单。
3. 为什么 Redis 选择使用跳表？
在 Redis 中，Sorted Set（ZSET）需要同时满足两个核心需求：
- 能按分数（score）进行排序。
- 能快速进行范围查找（例如，查找分数在 100 到 200 之间的所有成员）。
Redis 在实现 ZSET 时，实际上使用了两种数据结构：
- 哈希表：用于存储
member到score的映射。这使得ZSCORE操作的时间复杂度为 O(1)。 - 跳表：按
score排序存储所有member和score。
选择跳表而不是平衡树（如红黑树）的原因主要有以下几点：
- 实现简单：跳表的实现逻辑远比红黑树等平衡树要简单、直观。Redis 的作者 Salvatore Sanfilippo 曾表示，他选择跳表就是因为代码更容易写、更不容易出错。
- 范围查找性能优异：跳表本身就是基于链表的，进行范围操作（如
ZRANGE）非常自然和高效。只需找到范围的起始点，然后沿着链表顺序遍历即可。平衡树的范围查找需要通过中序遍历，虽然也是 O(log N + M)，但实现上跳表更直接。 - 内存占用：跳表通过随机化建立索引，其平均空间复杂度为 O(N)，与平衡树相当。但在实践中，通过调整概率参数（如 Redis 中 p=0.25），可以很好地控制内存使用。
- 并发友好：跳表的修改操作（插入、删除）通常只影响局部节点，而平衡树的旋转操作可能影响较大范围的子树，这使得跳表在并发环境下（虽然 Redis 是单线程模型，但设计理念上）更容易实现无锁或细粒度锁。
4. 跳表在 Redis 中的应用
跳表是 Redis 中 Sorted Set (ZSET) 的核心数据结构。
ZADD：插入一个新元素时，Redis 会先通过哈希表检查 member 是否已存在。如果存在，则更新其 score 并在跳表中调整位置；如果不存在，则创建新节点，并通过随机算法决定其索引层数，然后将其插入到跳表的相应位置。时间复杂度平均为 O(log N)。ZRANGE/ZREVRANGE：通过跳表快速定位到范围的起始节点，然后沿着prev或next指针顺序遍历，直到范围的结束节点。时间复杂度为 O(log N + M)，其中 N 是 ZSET 的元素总数，M 是返回的元素个数。ZRANK/ZREVRANK：查找某个 member 的排名。跳表需要维护一个span（跨度）属性，表示当前指针指向的下一个节点之间，在原始链表中有多少个节点。通过累加span，可以快速计算出排名。时间复杂度为 O(log N)。ZREM：删除一个元素，需要从哈希表和跳表中同时删除。在跳表中删除一个节点后，需要更新其上层所有索引中指向它的指针。时间复杂度平均为 O(log N)。
总结
- Redis 常规指令是操作 Redis 的基础，理解不同数据类型（String, Hash, List, Set, Sorted Set）及其对应指令是使用 Redis 的前提。
- 跳表是一种高效且实现相对简单的有序数据结构。Redis 在 Sorted Set 中巧妙地结合了哈希表和跳表，哈希表负责 O(1) 的单点查找，跳表负责 O(log N) 的排序和范围操作，这使得 Sorted Set 成为了 Redis 中功能最强大、最常用的数据结构之一。选择跳表而非平衡树，体现了 Redis 追求简洁、高效和可靠的设计理念。