← 返回首页 📚 实战课程
📑 本篇章节导航 (共5章,点击直达)
本节目标(学完能回答的面试题)核心知识(1小时精讲内容)面试速记卡(考前30秒速看)练习题(自测)学习资料

L13 - Redis数据结构底层实现

本节目标(学完能回答的面试题)

核心知识(1小时精讲内容)

一、Redis对象与编码概述

Redis中每个键值对都是一个redisObject,包含type(类型)和encoding(编码)两个字段。同一种type在不同条件下使用不同的encoding,这是Redis内存优化的核心设计。


redisObject {
    unsigned type:4;        // 类型: STRING/LIST/HASH/SET/ZSET
    unsigned encoding:4;    // 编码: int/embstr/raw/ziplist/quicklist/
                            //       intset/hashtable/skiplist/...
    unsigned lru:24;        // LRU时间
    int refcount;           // 引用计数
    void *ptr;              // 指向底层数据结构的指针
}

二、五种基础数据类型底层编码

2.1 String — int / embstr / raw


编码选择逻辑:
┌──────────────────────────────┐
│ 值是整数 且 <= LONG_MAX ?    │
│   是 → int 编码(直接存在ptr) │
│   否 ↓                       │
│ 字符串长度 <= 44字节 ?       │
│   是 → embstr 编码           │
│   否 → raw 编码(SDS)         │
└──────────────────────────────┘

embstr vs raw:
┌─────────────────────────────────┐
│ embstr (≤44字节):                │
│ ┌─────────────────────────────┐ │
│ │ redisObject | sdshdr | data │ │  ← 一次内存分配,连续内存
│ └─────────────────────────────┘ │
│ 优点: 一次分配、缓存友好        │
│ 缺点: 只读,修改会转为raw       │
├─────────────────────────────────┤
│ raw (>44字节):                   │
│ ┌──────────┐    ┌─────────────┐│
│ │redisObject│─→ │ SDS | data  ││  ← 两次内存分配
│ └──────────┘    └─────────────┘│
└─────────────────────────────────┘

SDS(Simple Dynamic String)结构:


struct sdshdr {
    int len;    // 已用长度
    int free;   // 剩余空间
    char buf[]; // 字节数组
};

SDS vs C字符串:
| 维度       | C字符串        | SDS             |
|-----------|---------------|-----------------|
| 获取长度   | O(N)遍历       | O(1)直接读len   |
| 缓冲区溢出 | 可能溢出       | 空间预分配,安全  |
| 修改内存   | 每次realloc    | 预分配+惰性释放  |
| 二进制安全 | \0结尾,不安全   | len判断,二进制安全|

2.2 List — quicklist

Redis 3.2之后,List底层统一使用quicklist(双向链表 + ziplist)。


quicklist结构:
┌──────────────────────────────────────────────────┐
│ quicklist                                         │
│ head                                              │
│   ↓                                               │
│ ┌─────────────┐    ┌─────────────┐               │
│ │ quicklistNode│⇄→│ quicklistNode│⇄→ ...         │
│ │ ziplist:     │    │ ziplist:     │              │
│ │ [e1][e2][e3] │    │ [e4][e5][e6] │              │
│ └─────────────┘    └─────────────┘               │
│                                                   │
│ 每个节点是一个ziplist(压缩列表)                    │
│ 节点间双向链表连接                                 │
└──────────────────────────────────────────────────┘

设计思想:
- 单纯链表: 内存碎片多,指针占用大(前驱+后继=16字节/节点)
- 单纯ziplist: 数据量大时realloc性能差
- quicklist: 折中方案,每个节点存一个ziplist,兼顾内存和性能

配置参数:
list-max-ziplist-size -2     # 每个ziplist不超过8KB
list-compress-depth 1        # 中间节点LZF压缩

2.3 Hash — ziplist / hashtable


编码转换条件:
field数量 ≤ 512 且 每个value ≤ 64字节 → ziplist
否则 → hashtable(字典)

ziplist存储Hash:
┌──────────────────────────────────────────┐
│ ziplist: [field1][value1][field2][value2]│  ← key-value紧挨存储
└──────────────────────────────────────────┘
查找: 顺序遍历,field数量少时足够快

hashtable存储Hash:
┌──────────────────────────────────────────┐
│ dict                                     │
│ ht[0]: ┌─────┬─────┬─────┬─────┐       │
│        │ k/v │ k/v │ k/v │ ... │       │  ← O(1)查找
│        └─────┴─────┴─────┴─────┘       │
│ rehash时用ht[1]逐步迁移                  │
└──────────────────────────────────────────┘

渐进式rehash:
1. 分配ht[1]空间(2倍ht[0])
2. 每次CRUD操作迁移ht[0]中一个桶到ht[1]
3. 全部迁移完成后,ht[0]←ht[1],释放旧ht[0]
4. 避免一次性rehash导致服务卡顿

2.4 Set — intset / hashtable


编码转换条件:
所有元素都是整数 且 数量 ≤ 512 → intset
否则 → hashtable

intset结构(整数集合):
┌──────────────────────────────────┐
│ encoding: INT16/INT32/INT64      │
│ length: 3                        │
│ contents: [1][5][9]              │  ← 有序数组,二分查找O(logN)
└──────────────────────────────────┘

升级过程(小→大):
1. 新加入一个INT64值,当前encoding是INT16
2. 扩展数组大小(length × INT64大小)
3. 将已有元素从INT16转为INT64(从后往前转换)
4. 插入新元素
注意: 不支持降级

hashtable存储Set:
只存key,value为NULL → 类似Java的HashSet

2.5 ZSet — ziplist / skiplist+hashtable


编码转换条件:
元素数量 ≤ 128 且 每个元素 ≤ 64字节 → ziplist
否则 → skiplist + hashtable

ziplist存储ZSet:
[element1][score1][element2][score2]  ← 紧凑存储,按score有序

skiplist + hashtable:
hashtable: member → score  (O(1)查分数)
skiplist:  按score排序     (O(logN)查排名/范围查询)

三、跳表(SkipList)深度解析


跳表结构示意:

Level 4:  1 ────────────────────────────────────── 9
Level 3:  1 ──────────────────── 5 ──────────────── 9
Level 2:  1 ────── 3 ────── 5 ────── 7 ────────── 9
Level 1:  1 ─ 2 ─ 3 ─ 4 ─ 5 ─ 6 ─ 7 ─ 8 ─ 9

查找score=7的过程:
Level 4: 1→9(9>7,下移)
Level 3: 1→5(5<7,右移)→9(9>7,下移)
Level 2: 5→7(7=7,命中!)
总共4次比较,而链表需要7次

每个节点随机建索引层(约25%概率,即1/4):
0层: 所有节点
1层: 约25%节点
2层: 约6.25%节点
k层: 约(1/4)^k节点

空间复杂度: O(N),每个节点平均1.33个指针

ZSet为什么用跳表不用红黑树?

对比维度跳表红黑树
查找O(logN)O(logN)
插入/删除O(logN)O(logN)
范围查询O(logN+M),直接遍历底层链表需要中序遍历,实现复杂
实现难度简单,代码量少复杂,旋转操作多
内存占用每节点约1.33指针每节点2指针+颜色位
并发友好局部锁容易实现旋转影响范围大

面试话术: "ZSet用跳表是因为范围查询更方便。ZRANGEBYSCORE只需要在底层链表上遍历即可,而红黑树范围查询需要中序遍历,实现复杂。跳表代码简单,内存可以接受(每个节点约1.33个指针)。虽然理论上和红黑树复杂度相同,但工程实现上优势明显。"

四、三种高级数据结构

4.1 HyperLogLog


原理: 概率算法,基于伯努利试验
内存: 固定12KB(16384个桶,每桶6bit)
误差: 0.81%标准误差
用途: UV统计、DAU统计

命令:
PFADD uv:20260523 "user1" "user2" "user3"
PFCOUNT uv:20260523            # 返回估算基数
PFMERGE uv:all uv:20260523 uv:20260522  # 合并

4.2 Bitmap


原理: bit位数组,底层就是String
操作: SETBIT/GETBIT/BITCOUNT/BITOP
内存: 1亿用户在线状态 ≈ 100M/8 ≈ 12.5MB

场景:
- 签到打卡: SETBIT sign:uid:202605 22 1  (22号签到)
- 在线状态: SETBIT online uid 1
- 统计活跃: BITCOUNT active:20260523

4.3 Stream (Redis 5.0+)


原理: radix tree + listpack
特点: 支持消费者组模型(类似Kafka)
命令: XADD/XREAD/XGROUP/XACK
用途: 消息队列、审计日志

Stream vs List:
- Stream支持消费者组,List不支持
- Stream消息可ACK,List不能
- Stream支持消息回溯,List不能

五、时间复杂度对比表

操作数据类型底层编码时间复杂度说明
GET/SETStringint/embstr/rawO(1)直接寻址
LPUSH/RPOPListquicklistO(1)头尾操作
LINDEXListquicklistO(N)需遍历ziplist
HGET/HSETHashziplistO(N)顺序查找
HGET/HSETHashhashtableO(1)哈希定位
SADD/SISMEMBERSetintsetO(logN)二分查找
SADD/SISMEMBERSethashtableO(1)哈希定位
ZADDZSetziplistO(N)插入需移动
ZADDZSetskiplistO(logN)跳表查找
ZRANGEZSetskiplistO(logN+M)链表遍历
ZRANKZSetskiplistO(logN)跳表查找

六、编码转换阈值速查表

类型小数据编码转换条件(满足全部)大数据编码
Stringint值为整数且<=LONG_MAX-
Stringembstr长度<=44字节raw
Hashziplistfield<=512 且 val<=64Bhashtable
Listquicklist始终quicklist
Setintset全整数 且 数量<=512hashtable
ZSetziplist元素<=128 且 val<=64Bskiplist+ht

面试话术: "Redis数据结构有自动编码转换机制。String短于44字节用embstr一次分配,长了转raw两次分配。Hash在field不超过512且value不超过64字节时用ziplist省内存,否则转hashtable保证性能。Set元素全是整数且不超过512个时用intset有序数组,否则转hashtable。ZSet元素不超过128且value不超过64字节时用ziplist,否则用跳表+哈希表。这些阈值都可以通过配置调整。"

面试速记卡(考前30秒速看)

练习题(自测)

1. 一个key的值是"hello world"(11字节),它底层是什么编码?如果执行APPEND追加到50字节,编码会发生什么变化?

2. 为什么Redis 3.2以后用quicklist替代了ziplist和linkedlist两种编码?quicklist的设计取舍是什么?

3. ZSet实现排行榜,当成员数为50时底层是什么编码?当成员增长到200时呢?为什么?

4. 解释SDS的"空间预分配"和"惰性释放"策略,它们分别解决了什么问题?

5. 如果面试官问"为什么Redis不用B树或红黑树做有序集合",你该怎么回答?请从范围查询、实现复杂度、并发友好三个维度分析。

学习资料