WAN
←Java 面试笔记VI · 03 / 06

Lesson 62 · 数据库与中间件实战

Redis 五大核心数据结构与应用场景

中级·⭐ 必问·#Redis·#数据结构
中级 · 面试必问

Redis 五大核心数据结构与应用场景

String/List/Hash/Set/ZSet 的底层编码（SDS、ziplist、skiplist、hashtable、intset）。每种结构的典型应用场景。

SDSziplistskiplisthashtableintset编码转换
第 1 站

String——SDS 动态字符串

Redis 的 String 不是 C 语言的原生字符串，而是自定义的 SDS（Simple Dynamic String）。SDS 在 C 字符串基础上增加了长度记录、预分配空间等特性。

SDS 内存结构（sdshdr8 为例） flags: 0x08 类型=sdshdr8 len: 5 已使用长度 alloc: 10 总分配长度 buf: "hello\0xxxxx" 字符数组 + \0 结尾 + 预留空间 SDS 相比 C 字符串的优势 ① O(1) 获取长度 — len 字段直接读取，无需 strlen() 遍历 ② 二进制安全 — 可以存任意二进制数据（包括 \0），以 len 为准而非 \0 截断 ③ 预分配 + 惰性释放 — 追加操作不需要每次 realloc，减少内存分配次数
图 1-1 SDS 内部结构：元信息头 + 字符数组 + 预分配空间

SDS 的预分配策略是什么？

当新长度 < 1MB 时，分配 2 倍空间；当新长度 >= 1MB 时，多分配 1MB。这种策略保证了连续追加 N 次，最多触发 O(logN) 次内存分配。

String 的三种编码
String 底层有三种编码：

int:     当值是整数时（如 SET counter 100）
         直接存储在 redisObject.val 中，无 SDS 开销

embstr:  当字符串长度 <= 44 字节时
         redisObject 和 SDS 分配在一次 malloc 中（连续内存）
         优点: 一次分配一次释放，减少碎片，缓存友好
         缺点: 不可修改（追加操作会转为 raw）

raw:     当字符串长度 > 44 字节时
         redisObject 和 SDS 分别分配内存
         支持修改操作（APPEND、SET 新值等）

OBJECT ENCODING mykey → 返回 "int" / "embstr" / "raw"
String 典型应用场景
1. 缓存对象
SET user:1001 '{"name":"Alice","age":25}' EX 3600

2. 分布式计数器
INCR article:views:1001        -- 原子递增
INCRBY stock:1001 -1          -- 原子递减（扣库存）

3. 分布式锁
SET lock:order uuid NX EX 30  -- 不存在则设置，30 秒过期

4. 分布式 Session 共享
SET session:token123 '{"userId":1001}' EX 1800
第 2 站

List——quicklist = ziplist + 双向链表

Redis 3.2+ 的 List 底层使用 quicklist，它是 ziplist 和双向链表的混合体：双向链表的每个节点是一个 ziplist。

quicklist 结构 quicklist Node 1 ziplist [A, B, C, D] prev=null, next→Node2 quicklist Node 2 ziplist [E, F, G, H] prev→Node1, next→Node3 quicklist Node 3 ziplist [I, J, K] prev→Node2, next=null 为什么不用纯链表或纯 ziplist？ 纯链表：每个节点一个元素 → 指针开销大，内存碎片多，CPU 缓存不友好 纯 ziplist：太长时更新操作 O(N) 连锁更新概率增大。quicklist 折中：ziplist 控制大小 + 链表串联
图 2-1 quicklist：双向链表节点存 ziplist，兼顾内存效率和操作性能
ziplist 压缩列表结构
ziplist 是一块连续内存：
zlbytes | zltail | zllen | entry1 | entry2 | ... | zlend

每个 entry 的结构：
prevlen  // 前一个 entry 的长度（用于反向遍历）
encoding // 编码方式（字符串 or 整数）
data     // 实际数据

优点：连续内存 → CPU cache friendly，无指针开销
缺点：插入/删除可能引发连锁更新（prevlen 字段从 1 字节变 5 字节）
关键结论

List 底层是 quicklist（Redis 3.2+）。quicklist = 双向链表，每个节点是一个 ziplist。LPUSH/RPUSH 是 O(1)，LINDEX 是 O(N)。ziplist 用连续内存存储，对 CPU 缓存友好。

第 3 站

Hash——ziplist vs hashtable

Hash 类型有两种底层编码：ziplist（数据少时）和 hashtable（数据多时）。

Hash 的两种编码 ziplist 编码（数据少时） field1, value1, field2, value2, ... 连续内存，field-value 相邻存放 优点：内存紧凑，无指针开销 优点：适合小数据量（默认 < 512 个 field 缺点：查找 O(N)，数据多时性能差 hashtable 编码（数据多时） dict 结构，和 Redis 全局 dict 一样 dictEntry → key SDS + value SDS 优点：查找/插入/删除 O(1) 缺点：指针开销大（dictEntry 24 字节） 缺点：内存碎片，CPU 缓存不友好 hash-max-ziplist-entries 512 / hash-max-ziplist-value 64
图 3-1 Hash 类型 ziplist 与 hashtable 编码对比
编码转换条件
ziplist → hashtable 转换条件（满足任一即转换）：
1. Hash 中 field 数量 > hash-max-ziplist-entries（默认 512）
2. 任一 field 或 value 长度 > hash-max-ziplist-value（默认 64 字节）

注意：转换是单向的，hashtable 不会退化为 ziplist
第 4 站

Set——intset vs hashtable

Set（集合）的底层编码也有两种：intset（全是整数且数量少时）和 hashtable。

intset 内部结构 encoding: INTSET_ENC_INT32 编码类型 length: 5 元素个数 contents: [3, 7, 15, 42, 99] 有序整数数组（升序排列） intset 的操作复杂度 SADD: 二分查找 O(logN) 定位 + 数组移动 O(N) SMEMBERS: O(N) 遍历。整数数组连续存储 → 内存高效、CPU 缓存友好
图 4-1 intset：有序整数数组，适合全整数的小集合
intset 的编码升级
intset 支持三种整数编码：
INTSET_ENC_INT16  → 每个元素 2 字节
INTSET_ENC_INT32  → 每个元素 4 字节
INTSET_ENC_INT64  → 每个元素 8 字节

当插入一个超出当前编码范围的整数时，intset 会"升级"：
例如从 INT16 升级到 INT32 → 所有已有元素都要重新编码
升级是单向的，不会降级

intset → hashtable 转换条件（满足任一）：
1. 元素个数 > set-max-intset-entries（默认 512）
2. 插入了非整数元素（如字符串）
关键结论

Set 全整数且 < 512 个时用 intset（有序数组，紧凑高效），否则用 hashtable（value 为 NULL 的 dict，O(1) 查找）。SISMEMBER 在 intset 中是 O(logN) 二分，在 hashtable 中是 O(1)。

第 5 站

ZSet——ziplist vs skiplist + hashtable

有序集合（ZSet）是最复杂的数据结构，有两种编码：ziplist（数据少时）和 skiplist + hashtable。

skiplist 跳表结构 header level 4 → level 3 → level 2 → level 1 → score=1.5 member="alice" level 2 → level 1 → backward → score=3.0 member="bob" level 3 → level 2 → level 1 → score=5.2 member="carol" level 1 → score=8.1 member="dave" level 2 → level 1 → ZSet 两种编码 ziplist: field-value 相邻存放，按 score 排序。适合 < 128 个元素且 value < 64 字节 skiplist + hashtable: skiplist 按 score 排序查范围，hashtable 按 member O(1) 查分数
图 5-1 skiplist 跳表：多层索引实现 O(logN) 查找，比平衡树更适合范围查询

为什么 ZSet 用 skiplist 而不用红黑树？

三个原因：① skiplist 实现简单（随机层级，不用旋转）；② skiplist 天然支持范围查询（ZRANGEBYSCORE），从高层快速定位起点后沿 level 0 遍历即可，红黑树做范围查询需要中序遍历；③ skiplist 的并发友好性更好（虽然 Redis 单线程不关心这个）。

关键结论

ZSet 底层：少量数据用 ziplist，大量数据用 skiplist（排序 + 范围查询）+ hashtable（按 member 查 score，O(1)）。skiplist 每个节点随机生成 1~64 层，平均 O(logN) 查找。

第 6 站

编码转换——Redis 什么时候"升级"底层结构？

Redis 会根据数据量和元素大小，自动将底层编码从"紧凑"升级到"高效"。转换是单向的，不会降级。

数据类型紧凑编码高效编码升级触发条件
Stringint (embstr)raw (SDS)值长度 > 44 字节 / 执行追加操作
ListziplistquicklistRedis 3.2+ 默认就用 quicklist
Hashziplisthashtablefield > 512 或 value > 64 字节
Setintsethashtable元素 > 512 或含非整数
ZSetziplistskiplist + hashtable元素 > 128 或 value > 64 字节
查看与调优编码
-- 查看 key 的底层编码
OBJECT ENCODING myhash
-- 返回 "ziplist" 或 "hashtable"

-- 调优阈值（redis.conf）
hash-max-ziplist-entries 512
hash-max-ziplist-value   64
zset-max-ziplist-entries 128
zset-max-ziplist-value   64
set-max-intset-entries   512

-- 如果业务中 Hash 经常只有少量 field，可以调大阈值来节省内存
面试一招鲜

"Redis 会自动根据数据量选择最优编码。小数据用连续内存（ziplist/intset）节省空间，大数据用哈希表/跳表保证性能。OBJECT ENCODING 命令可以查看当前编码。"——这段话能展示你对底层的理解。

第 7 站

应用场景总结

数据类型典型应用场景核心命令
String缓存、计数器、分布式锁、Session 共享、验证码SET/GET/INCR/EXPIRE
List消息队列（LPUSH + BRPOP）、最新列表、朋友圈时间线LPUSH/RPUSH/LPOP/RPOP/LRANGE
Hash用户信息（field-value）、商品属性、配置项HSET/HGET/HMSET/HGETALL
Set标签系统、共同好友、去重、抽奖（SRANDMEMBER）SADD/SMEMBERS/SINTER/SUNION
ZSet排行榜、延迟队列、带权重的任务调度ZADD/ZRANGE/ZRANGEBYSCORE/ZRANK
选型决策树 数据是什么结构？ 简单KV → String 有序队列 → List 对象属性 → Hash 去重/交并 → Set 排序/排名 → ZSet 先根据业务语义选型，再根据数据量调整编码阈值
图 7-1 Redis 数据类型选型决策

全篇回顾

  1. String：底层 SDS，O(1) 获取长度，二进制安全，预分配空间
  2. List：底层 quicklist = 双向链表 + ziplist 节点，兼顾内存效率和操作性能
  3. Hash：少量用 ziplist，多用 hashtable。field-value 存储对象属性首选
  4. Set：全整数少量用 intset（有序数组），否则 hashtable。去重/集合运算
  5. ZSet：少量用 ziplist，多用 skiplist + hashtable。排行榜/延迟队列
  6. 编码转换：自动单向升级，可通过 redis.conf 调阈值优化内存
  7. 选型：按业务语义选类型，按数据量调编码