Redis篇（二）：数据结构

一、Redis 数据类型全景图

Redis 不是简单的 Key-Value 存储，它提供了丰富的数据类型，每种类型都针对特定场景做了深度优化。理解这些数据类型的底层实现，是写出高效 Redis 代码的前提。

1.1 五大基础数据类型

1.2 四大特殊数据类型

二、String 类型：不只是字符串

2.1 应用场景深度解析

String 是 Redis 最常用的数据类型，但很多人只把它当作字符串缓存。实际上，String 在 Redis 中是一个"万能容器"：

1. 缓存对象

# 直接存储 JSON 字符串SET user:1001'{"id":1001,"name":"Alice","age":25}'GET user:1001# 或使用 Hash 拆分存储（字段频繁变化时推荐）HSET user:1001 name Alice age25

2. 计数器（原子操作）

# 文章阅读计数INCR article:1001:views# 库存扣减（配合 WATCH 实现乐观锁）WATCH stock:1001 GET stock:1001 MULTI DECR stock:1001 EXEC

为什么计数器是原子的？Redis 命令执行是单线程的，INCR/DECR 等操作天然具备原子性，无需额外加锁。

3. 分布式锁（SETNX 的演进）

# Redis 2.6 之前的写法（存在死锁风险）SETNX lock:order:10011EXPIRE lock:order:100130# Redis 2.6+ 推荐写法（原子设置值+过期时间）SET lock:order:1001 request_id NX EX30# 释放锁（Lua 脚本保证原子性）EVAL"if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end"1lock:order:1001 request_id

4. 共享 Session

在分布式系统中，用户的 Session 信息存储在 Redis 中，所有服务器实例共享同一份 Session 数据，解决了传统 Session 粘滞的问题。

2.2 底层实现：SDS（Simple Dynamic String）

Redis 没有直接使用 C 语言原生的字符串，而是自定义了 SDS 结构。这是 Redis 设计中最精妙的细节之一。

SDS 结构定义（源码简化版）：

structsdshdr{uint32_tlen;// 当前字符串长度（O(1) 获取）uint32_talloc;// 已分配的总容量charflags;// SDS 类型标识（5/8/16/32/64 位）charbuf[];// 柔性数组，实际存储数据};

SDS 相比 C 字符串的四大优势：

SDS 扩容策略：

• 当新长度< 1MB时，扩容为2 倍新长度
• 当新长度≥ 1MB时，扩容为新长度 + 1MB
• 这种策略在节省内存和减少 realloc 之间取得了平衡

三、List 类型：从双向链表到 quicklist 的演进

3.1 应用场景

1. 消息队列（LPUSH + BRPOP）

# 生产者LPUSH queue:tasks'{"task":"send_email","to":"user@example.com"}'# 消费者（阻塞等待，超时 30 秒）BRPOP queue:tasks30

2. 时间线/朋友圈点赞

# 点赞（LPUSH 保证最新在前）LPUSH moment:1001:likes user:2001 LPUSH moment:1001:likes user:2002# 取消点赞（LREM 移除指定元素）LREM moment:1001:likes1user:2001# 获取前 10 个点赞用户LRANGE moment:1001:likes09

3.2 底层实现演进

Redis 的 List 底层经历了三次重大演进：

quicklist 的核心设计：

structquicklist{quicklistNode*head;// 头节点quicklistNode*tail;// 尾节点unsignedlongcount;// 总元素数intfill;// 每个 ziplist/listpack 节点的最大容量};structquicklistNode{quicklistNode*prev;quicklistNode*next;unsignedchar*zl;// 指向 ziplist/listpack 的指针unsignedintsz;// ziplist 占用的字节数};

quicklist 通过fill参数控制每个压缩列表节点的大小（默认 -2，即 8KB），当单个节点数据量过大时拆分为多个节点，从而规避了连锁更新的风险。

四、Hash 类型：字段级操作的缓存利器

4.1 应用场景

1. 购物车（经典面试题）

# 用户 1001 的购物车HSET cart:1001 sku:20012# 商品 2001，数量 2HSET cart:1001 sku:20021# 商品 2002，数量 1HINCRBY cart:1001 sku:20011# 商品 2001 数量 +1# 获取购物车所有商品HGETALL cart:1001# 获取商品数量HGET cart:1001 sku:2001

2. 对象缓存的两种方案对比

选型建议：对象字段少且整体读取 → String；字段频繁变化 → Hash。

4.2 底层实现：listpack + hashtable

Hash 的编码转换条件：

• 当字段数< 512且所有字段和值的长度< 64 字节→ 使用listpack（紧凑编码，省内存）
• 否则 → 使用hashtable（标准哈希表，查询 O(1)）

五、Set 类型：去重与集合运算的专家

5.1 应用场景

1. 共同关注（交集运算）

# 用户 A 关注的公众号SADD user:A:follows gzh:tech gzh:finance gzh:sports# 用户 B 关注的公众号SADD user:B:follows gzh:tech gzh:finance gzh:food# 共同关注SINTER user:A:follows user:B:follows# 结果: gzh:tech, gzh:finance# A 关注但 B 未关注的SDIFF user:A:follows user:B:follows# 结果: gzh:sports

2. 抽奖去重

# 记录已中奖用户SADD lottery:winners user:1001 user:1002# 判断用户是否已中奖SISMEMBER lottery:winners user:1003# 返回 0，未中奖# 随机抽取 1 名未中奖用户（从全部用户中排除已中奖）SRANDMEMBER all_users1

5.2 底层实现：intset + hashtable

intset 的升级机制：

intset 中的元素按类型统一存储（int16_t / int32_t / int64_t）。当插入一个更大类型的整数时，整个 intset 会升级为新类型，这是 O(N) 操作，但保证了存储的有序性和内存紧凑性。

六、ZSet 类型：有序集合的王者

6.1 应用场景

1. 实时排行榜

# 添加玩家分数（自动按分数排序）ZADD leaderboard1500player:1001 ZADD leaderboard2300player:1002 ZADD leaderboard1800player:1003# 获取前 10 名（分数从高到低）ZREVRANGE leaderboard09WITHSCORES# 获取玩家排名ZREVRANK leaderboard player:1002# 给玩家加分ZINCRBY leaderboard100player:1001

2. 延时队列

# 任务执行时间作为 score（时间戳）ZADD delay_queue1699123456"task:send_email"ZADD delay_queue1699123500"task:generate_report"# 获取当前时间前应执行的任务ZRANGEBYSCORE delay_queue01699123456

6.2 底层实现：listpack + skiplist + hashtable

ZSet 是 Redis 中最复杂的数据结构，它同时使用了两种数据结构：

• skiplist（跳表）：维护元素的有序性，支持范围查询
• hashtable：存储 member → score 的映射，保证单点查询 O(1)

编码转换条件：

• 元素数< 128且 member 长度< 64 字节→listpack（紧凑编码）
• 否则 →skiplist + hashtable（高效编码）

七、跳表（Skip List）：为什么 Redis 偏爱它？

7.1 跳表的核心思想

跳表是一种基于有序链表的数据结构，通过添加多级索引来实现高效的查找、插入和删除操作。它的平均时间复杂度为O(log N)，接近平衡树的性能，但实现简单得多。

跳表查找过程（以查找 7 为例）：

1. 从最高层开始：层 3 中，1 的下一个节点是 9，9 > 7，向下移动到层 2
2. 在层 2：1 的下一个节点是 5，5 < 7，向右移动到 5
3. 在层 2：5 的下一个节点是 9，9 > 7，向下移动到层 1
4. 在层 1：5 的下一个节点是 7，找到目标

时间复杂度分析：

7.2 为什么 Redis 用跳表而不用平衡树？

这是面试中的高频问题，核心原因有三点：

1. 内存占用更灵活

• 平衡树每个节点包含 2 个指针（左右子树）
• 跳表每个节点平均包含1/(1-p)个指针（p 通常取 0.25，即平均 1.33 个）
• 跳表更节省内存

2. 范围查询更简单

• 平衡树找到范围起点后，需要中序遍历才能获取后续元素，实现复杂
• 跳表找到起点后，只需在第 1 层链表顺序遍历即可，实现简单直观

3. 实现难度低

• 平衡树的插入和删除可能引发子树旋转调整，逻辑复杂，容易出错
• 跳表的插入和删除只需修改相邻节点的指针，操作简单快速

八、压缩列表的连锁更新与 listpack 的救赎

8.1 ziplist 的连锁更新问题

ziplist 是 Redis 早期为节省内存设计的紧凑数据结构，由连续内存块组成。每个节点包含三个字段：

• prevlen：前一个节点的长度（1 字节或 5 字节）
• encoding：当前节点的编码方式
• content：实际数据

连锁更新的触发条件：

假设一个 ziplist 中有多个节点，每个节点的 prevlen 都是 1 字节（表示前一个节点长度 < 254）。当某个节点插入后，其长度变为 254 字节，导致下一个节点的 prevlen 需要从 1 字节扩展为 5 字节。这个扩展又可能导致下一个节点的长度变化，引发连锁反应。

最坏情况下，连锁更新需要O(N²)的内存重分配，严重影响性能。

8.2 listpack：彻底解决连锁更新

listpack 是 Redis 5.0 引入、7.0 全面替换 ziplist 的新数据结构。它的核心改进是：

• 不记录 prevlen，只记录当前节点的长度（len）
• 插入/修改只影响当前节点，不会触发连锁更新
• 通过倒序遍历（从尾部开始，根据 len 向前跳）实现反向遍历

Redis 底层数据结构演进时间线：

九、哈希表：Redis 的 O(1) 查询基石

9.1 哈希表结构

Redis 的哈希表采用拉链法解决冲突，每个桶（bucket）维护一个链表，哈希值相同的 key 串在一起。

核心特性：

• 负载因子 > 1 时自动扩容：扩容为 2 倍，保证查询效率
• 渐进式 rehash：分多次迁移数据，避免阻塞主线程（Redis 是单线程的，阻塞会影响所有请求）
• 查询复杂度：O(1) 平均，最坏 O(N)（所有 key 哈希冲突到同一个桶）

9.2 渐进式 rehash 的精妙设计

Redis 的 rehash 不是一次性完成的，而是分步进行：

// 伪代码：渐进式 rehashdict*d;// 1. 创建新哈希表（2倍大小）d->ht[1]=create_hash_table(d->ht[0].size*2);// 2. 将 rehashidx 置为 0，标志开始 rehashd->rehashidx=0;// 3. 每次执行命令时，迁移少量节点（如 100 个）while(n--&&d->ht[0].used!=0){// 迁移一个桶的所有节点到 ht[1]migrate_bucket(d,d->rehashidx++);}// 4. 全部迁移完成后，交换 ht[0] 和 ht[1]if(d->ht[0].used==0){swap_ht(d);d->rehashidx=-1;// rehash 完成}

这种设计保证了：

• 查询时：先查 ht[0]，再查 ht[1]，不会漏数据
• 写入时：直接写入 ht[1]，保证新数据在新表中
• 无阻塞：每次只迁移少量节点，对性能影响微乎其微

十、特殊数据类型速览

10.1 Bitmap：位级操作的内存杀手

Bitmap 将 String 的每个 bit 作为一个独立的状态位，极省内存：

# 用户签到（第 0 天签到）SETBIT user:1001:sign01SETBIT user:1001:sign11SETBIT user:1001:sign20# 统计本月签到天数BITCOUNT user:1001:sign# 1 亿用户的在线状态仅需 12MB 内存！

10.2 HyperLogLog：概率统计的魔法

HyperLogLog 用固定12KB内存，可以统计2^64个不同元素的基数，标准误差仅0.81%：

# 统计网页 UVPFADD page:home:uv user:1001 user:1002 user:1003 PFCOUNT page:home:uv

10.3 GEO：地理位置服务

GEO 基于 ZSet 实现，使用GeoHash编码将二维经纬度映射为一维字符串：

# 添加位置GEOADD locations116.4039.90"beijing"GEOADD locations121.4731.23"shanghai"# 获取两地距离GEODIST locations beijing shanghai km# 获取北京附近 100km 的城市GEORADIUS locations116.4039.90100km WITHDIST

10.4 Stream：消息队列的终极方案

Stream 是 Redis 5.0 专为消息队列设计的数据类型，相比 List 实现的消息队列：

# 生产者XADD mystream * field1 value1 field2 value2# 消费者组XGROUP CREATE mystream mygroup $ XREADGROUP GROUP mygroup consumer1 COUNT1STREAMS mystream>

十一、总结与选型指南

11.1 数据类型选型速查表

11.2 编码转换的启示

Redis 的每种数据类型都支持多种底层编码，并在运行时根据数据特征自动切换：

• 小数据 → 紧凑编码（listpack、intset）：节省内存
• 大数据 → 高效编码（hashtable、skiplist）：保证性能

这种"自适应编码"的设计思想，是 Redis 在内存效率和执行性能之间取得平衡的关键。