Redis 数据结构

一、 数据结构是什么

redis常用的数据类型有五种：String（字符串），Hash（哈希），List（列表），Set（无序集合），SortedSet(有序集合)

Redis 里说的 数据结构，不是单纯的“存储的数据类型”（比如 string、list、set），而是 它在内存中是如何组织和存放这些数据的

Redis 类型	底层数据结构
String	SDS
List	quicklist
Hash	ziplist（小数据） / dict（大数据）
Set	intset（小数据） / dict（大数据）
Sorted Set	ziplist（小数据） / skiplist + dict（大数据）

二、 数据结构

SDS

1. SDS 的结构

   在 Redis 源码里，SDS 本质上就是一个结构体 + 一个真正的 char 数组：

   struct sdshdr {int len;    // 已使用的长度int free;   // 剩余的可用空间char buf[]; // 实际存储数据的数组，最后有个 '\0'
   };
   

   例如：存储 “hello”

   len = 5
   free = 3
   buf = ['h','e','l','l','o','\0']
   

2. SDS与C语言相比的优点

   Redis 并没有直接用 C 语言自带的 char* 来存字符串，而是自己实现了一套 SDS

   （1） 避免 O(n) 获取长度

   • C 的字符串结尾靠 \0 标识，获取长度必须遍历一遍，时间复杂度是 O(n)

   • SDS 直接记录 len，获取长度就是 O(1)

   （2） 避免缓冲区溢出

   • C 的 char* 如果追加字符串，很容易超过原本分配的内存，造成溢出

   • SDS 通过记录 len 和 free（已分配但未使用的空间），能安全扩容

   （3） 减少内存分配次数

   • SDS 有预分配策略：扩容时不只分配需要的，还会多留一点空间，下次写入更快

   • 缩小字符串时，采用惰性释放，不立刻还给系统，避免频繁 malloc/free

3. 主要特性

   (1) O(1) 获取长度

   • C语言：strlen(“hello”) 在 C 里要一个个数，O(n)

   • SDS：sdslen(s) 直接返回 len，O(1)

   (2) 动态扩容（预分配策略）

   如果追加 " world"，SDS 会判断空间是否够，不够就扩容：

   • 如果扩展后长度 < 1MB，就分配 新长度 × 2 的空间

   • 如果扩展后长度 ≥ 1MB，就每次加 1MB

   这样避免了每次都 malloc

   (3) 惰性空间释放

   如果你把 “hello world” 改成 “hi”，

   len=2

   free=9（原来的空间没立刻释放，下次还能用）

   Redis 有 sdsRemoveFreeSpace() 可以手动回收

   (4) 二进制安全

   • C语言： 字符串必须以 \0 结尾，不然 API 会误判

   • SDS： 可以存任意二进制数据（即使里面有 \0），因为它靠 len 来判断（所以 SDS 不仅能存 “hello”，还能存图片、序列化对象）

4. SDS 在 Redis 里的应用

   所有 key 都是 SDS

   String 类型的 value 也是 SDS

   其他类型（List、Hash 等）里存的元素，也常常是 SDS

5. 对比 C 字符串

特性	C 字符串 (char*)	Redis SDS
长度获取	O(n)，要遍历 \0	O(1)，直接读 len
扩容 手动	malloc，容易溢出	自动扩容，安全
内存效率	精确分配	预分配、惰性释放
二进制安全	不行（遇到 \0 截断）	可以存任意二进制
性能	简单，但低效	较复杂，但高效

---

ziplist（压缩列表）

1. 定义

   压缩列表（ziplist）是 Redis 为了节省内存而设计的一种顺序存储结构，本质上就是一块连续的内存区域，用来存放多个数据节点

   它主要用于存储：

   • 小的 list （列表）

   • 小的 hash （哈希）

   • 小的 sorted set （有序集合）

   当数据量小、元素小的时候，Redis 会用 ziplist 来存，节省内存开销

2. 整体结构

   一个 ziplist 的内存布局大概是这样：

   < zlbytes>< zltail>< zllen>< entry1>< entry2>…< entryN>< zlend>

   逐个解释：

   zlbytes：记录整个 ziplist 占用的字节数（方便一次性 realloc）

   zltail：记录最后一个 entry 的偏移量（方便从尾部快速定位）

   zllen：记录 entry 的个数

   entry1…entryN：真正存的数据，每个 entry 的结构下面讲

   zlend：，固定值 0xFF，标志 ziplist 结束

   —> 可以类比成一个“紧凑型数组”，前面写上总大小、尾部指针、元素数量，最后加一个“结束符”

3. entry（节点）的结构

   每个 entry 是压缩列表的基本单元，一个 entry 包含：

   < prevlen><encoding+len>< content>

   • prevlen：前一个 entry 的长度，用来支持从后往前遍历

     • 如果前一个 entry 小于 254 字节，那么 prevlen 用 1 个字节存

     • 否则用 5 个字节存（第一个字节 254，后 4 个字节是长度）

   • encoding+len：存储当前 entry 的数据类型和长度

     • 如果是字符串：会记录字符串长度

     • 如果是整数：会记录整数的类型（int16、int32、int64 等）

   • content：真正的数据内容，比如字符串 “hello” 或整数 123

4. 特点

   优点

   • 内存紧凑，节省空间

   • 支持双向遍历（prevlen + 顺序存储）

   缺点

   • 插入/删除元素时，可能触发连锁更新（因为 prevlen 的长度可能从 1 字节变 5 字节，导致后面所有 entry 都要整体移动）

   • 适合元素少、元素小的场景，不适合大数据量

---

quicklist

1. 什么是 quicklist

quicklist 是 Redis list 类型的底层实现
它是 双向链表 + 压缩列表（ziplist） 的结合体

• 链表：插入/删除快，但内存碎片多

• 压缩列表：节省内存，但插入/删除复杂度高

• quicklist：用链表把多个 ziplist 串起来，兼顾两者优点

2. quicklist 的结构

quicklist 是一个 双向链表，链表的每个节点（quicklistNode）存放一个 ziplist

大致结构如下

quicklist
├── head 指针
├── tail 指针
├── count 元素总数
├── len 节点个数
└── quicklistNode 链表节点们
↓
quicklistNode1 ── quicklistNode2 ── quicklistNode3 …
(ziplist) (ziplist) (ziplist)

---

intset（整数集合）

1. IntSet 是什么

   IntSet 是 Redis 专门 为只包含整数的集合 设计的一种紧凑型数据结构
   比如你往一个集合（set 类型）里面放的元素都是数字：{1, 2, 3, 100}，Redis 就会用 IntSet 来存储

   特点：

   • 只存整数（int16、int32、int64 三种格式）

   • 内存布局紧凑，省空间

   • 内部元素自动排序，不会有重复

   可以理解成 Redis 给整数集合专门优化的一个“小型数组结构”，和 Go 里用 []int 存放一组数据有点类似，但它还会根据数据大小自动选择存储的整数类型

2. IntSet 的内部结构

   源码（伪代码）：

   struct intset {uint32 encoding;   // 编码方式：16/32/64 位整数uint32 length;     // 集合中的元素个数int8 contents[];   // 真正存放整数的地方，按有序数组排好
   };
   

   解释：

   • encoding
     决定数组里存放的是 int16、int32 还是 int64

   • length
     当前一共存了多少个元素

   • contents[]
     真正的数据区，是一个有序数组，保证元素从小到大排列

3. 升级机制

   其中比较高级的是 动态升级

   • 如果你先往集合里放了 1, 2, 3，这几个数字都能用 int16 表示，那么 encoding 就是 16

   • 如果你后来又插入一个大数 65536（超过了 int16 的范围），那么整个 intset 会升级成 int32：

     • 把原来 contents[] 里的所有元素从 2 字节扩展为 4 字节

     • encoding 改为 32

   • 如果再来个更大的数字（超过 int32），它还会继续升级为 int64

   注：只会升级，不会降级（避免频繁的内存拷贝）

   这有点像 Go 里的切片扩容，容量不够了会整体搬迁，只不过 intset 是根据数字大小升级存储格式。

4. 使用场景

Redis 默认会在集合满足条件时使用 IntSet，比如：

集合类型 set，所有元素都是整数，且数量不超过 set-max-intset-entries（默认 512）

超过这个数量，或者插入了非整数元素，Redis 会自动把底层编码从 IntSet 转为 hashtable

---

skiplist（跳表）

1. 什么是 Skiplist（跳表）？

   跳表是一种有序数据结构，Redis 主要用它来实现 有序集合 SortedSet（Zset）

   它本质上是 一个多层链表结构，在查找时通过多层索引加快搜索速度，性能接近平衡树，但实现更简单

   可以理解为：

   普通链表查找元素必须从头到尾遍历，时间复杂度是 O(n)，跳表在链表的基础上增加了“索引层”，相当于给链表加了“电梯”，查找时先从高层快速跳跃，再逐层向下，直到找到目标元素，平均查找效率 O(log n)，插入/删除也是 O(log n)

2. 跳表的结构

   跳表不是简单的链表，而是多层链表堆叠在一起
   Redis 跳表节点定义（伪代码）：

   typedef struct zskiplistNode {double score;               // 排序用的分值sds ele;                    // 成员对象（字符串）struct zskiplistNode *backward; // 后退指针（用于双向遍历）struct zskiplistLevel {struct zskiplistNode *forward; // 指向前进节点unsigned int span;             // 跨度，用于排名计算} level[];
   } zskiplistNode;
   

   ele：实际存储的值（比如 “user:1001”）

   score：排序的权重（浮点数，比如积分、权重值等）

   level 数组：存放多个层级的 forward 指针，相当于多层索引

   span：记录跨过多少个节点，用于快速计算排名

   backward：指向前一个节点，方便倒序遍历

   例如：

   假设我们要存储有序集合：

   (“Alice”, 5)
   (“Bob”, 10)
   (“Carol”, 15)
   (“Dave”, 20)

   普通链表存储时：

   Alice -> Bob -> Carol -> Dave

   查找 “Dave” 必须从头依次遍历

   跳表可能长这样（假设是 3 层索引）：

   Level 3: Alice ---------> Carol
   Level 2: Alice -> Bob -> Carol
   Level 1: Alice -> Bob -> Carol -> Dave

   查找 “Dave” 时，先在 Level 3 找到 “Carol”，再下到 Level 1，继续往后就找到 “Dave”

   这样跳跃式查找，大大减少了遍历节点数量