Redis数据结构详解

Redis 有五大基础数据类型（String、List、Hash、Set、ZSet），antirez 在设计时做了十分精准的抽象：

  • 单一标量 对应 String
  • 线性序列 对应 List
  • 键值映射 对应 Hash
  • 无序且不重复的集合 对应 Set
  • 带权重的排序集合 对应 ZSet

这五种类型是“正交”的（互相不可替代），且构成了图灵完备级别的数据表达能力，能够映射 99% 的业务数据模型。

Redis 并没有直接将对外暴露的数据类型直接映射为单一的底层实现，而是采用了“多态”的设计：每种对象都由 redisObject 结构体表示，内部通过 encoding 属性决定实际使用哪种底层数据结构。这种设计使得 Redis 可以根据存储数据的数量和类型，在“内存占用”与“计算性能”之间动态寻找平衡点。

String：SDS

Redis 的 String 类型并没有使用 C 语言原生的 char* 字符串，而是设计了 简单动态字符串（Simple Dynamic String, SDS）。

SDS 内部维护了 len（已用长度）和 alloc（分配总空间）两个字段。相比 C 的原生字符串，SDS 具有以下优点：

  • O(1) 获取长度
  • 杜绝缓冲区溢出与二进制安全：在修改字符串时，SDS 会预先检查空间是否充足。如果不足，会自动扩容，杜绝了 C 语言中常见的缓冲区溢出风险。通过 len 字段来判断字符串的实际长度，而不是依赖空字符 \0 来判断结尾，可安全存储图片、序列化对象等二进制数据。
  • 空间预分配与惰性释放：SDS 采用了空间预分配策略。当字符串增长时，会分配比实际需要更多的额外空间。减少了连续追加操作时的内存重分配次数，提高了性能。
    • 当修改后的长度 len < 1MB：分配与 len 等量的 free 空间。
    • 当修改后的长度 len >= 1MB：额外分配 1MB 的 free 空间。
    • 惰性空间释放：当字符串缩短时，程序不立即回收内存，而是增加 free 的值。避免缩短后再次追加导致的频繁内存分配。

List：Quicklist

在 Redis 3.2 之后，List 的底层统一从之前的 Ziplist 和 Linked List 换成了 Quicklist。

Quicklist 是一个由 Ziplist 构成的双向链表，它结合了两者的优点：既像 linkedlist 一样易于在两端增删，又通过 ziplist 极大地优化了内存使用率。

Ziplist

一种为节省内存而设计的顺序型数据结构。由一系列特殊编码的连续内存块组成，没有指针开销。

要理解 Ziplist，必须先懂传统的 Linked List（双向链表）有多么“浪费”。

一个标准的双向链表节点大概长这样：

1
2
3
4
5
struct Node {
    String data;       // 真正的数据，比如存个 "hi"（占 2 字节）
    struct Node* prev; // 指向上一个节点的指针（64 位系统占 8 字节）
    struct Node* next; // 指向下一个节点的指针（64 位系统占 8 字节）
};

发现问题了吗？ 你为了存一个只有 2 字节的单词 "hi"，居然要额外花 16 个字节 去存 prev 和 next 指针！这就是所谓的 “指针开销（Overhead）”。而且，链表的节点在内存中是 随机散落 的，这会导致严重的内存碎片，且对 Cache Line 极不友好。

为了省钱（省内存），Redis 作者 antirez 发明了 Ziplist。

Ziplist 是一个被极其压缩的字节数组。它向操作系统申请 一整块连续的内存，把所有的数据严丝合缝地挤在一起。内部没有任何指针。

Ziplist 里的一个节点（Entry）严格由三部分组成：[prevlen] [encoding] [data]

  1. prevlen (Previous Entry Length)：记录 上一个节点的物理总字节数。
  2. encoding：一个变长字段。它的最高几位二进制用于标识数据的类型（字符串或整数），剩下的二进制位记录 当前节点的 data 部分占用的字节数（数据长度）。
  3. data：实际存储的数据内容。

向后遍历：假设指针站在当前节点的起点。

  1. 指针读取 prevlen 的第一个字节，判断出 prevlen 字段本身占用了几个字节（1 字节或 5 字节）。
  2. 指针接着读取 encoding 的第一个字节，通过最高位判断出 encoding 字段本身占用了几个字节，并从中解析出 data 的长度。
  3. 指针执行加法：当前地址 + prevlen自身大小 + encoding自身大小 + data长度，完美跳到下一个节点的起点。

向前遍历：假设指针站在当前节点的起点，需要回到上一个节点。指针直接读取脚下的 prevlen 字段，得出上一个节点的物理总长度 $L$。然后执行 当前地址 - L，精确回到上一个节点的起点。

为了把内存省到极致，Redis 给 prevlen 定了一个极其抠门的变长规则：

  • 如果前一个节点的总大小 < 254 字节，prevlen 自身只占 1 个字节。
  • 如果前一个节点的总大小 >= 254 字节，prevlen 自身必须扩容到 5 个字节。

假设你的 Ziplist 里，有连续的多个节点：e1, e2, e3, e4。巧合的是，它们每个节点的总大小，刚好都是 253 字节。

因为 253 < 254，所以 e2 的 prevlen 是 1 字节；e3 的 prevlen 是 1 字节……大家相安无事。

突然，你要在表头插入一个超大的新节点 NEW，大小是 300 字节！

开始失控了：

  1. e1 发现前面的节点变成了 300 字节（>= 254），其 prevlen 必须从 1 字节扩容到 5 字节。
  2. 这导致 e1 自己的物理总大小从 253 字节增加到了 257 字节。
  3. e2 发现前面的 e1 变成了 257 字节（>= 254），e2 的 prevlen 也被迫扩容到 5 字节。
  4. 这导致 e2 的总大小也变成了 257 字节，进而引发 e3 扩容……

就像 多米诺骨牌 一样，一个节点的插入，导致后续成百上千个节点全部被迫扩大容量。

又因为 Ziplist 是一块 连续内存，哪怕只要扩大 4 个字节，Redis 也必须向操作系统重新申请一块更大的内存，把所有数据拷贝过去。这会导致这一次的插入操作，性能从极其极速的 O(1) 直接暴跌到惨不忍睹的 $O(N^2)$。

这就是 ziplist 的 连锁更新（Cascade Update） 问题。

可以发现，这个问题出现其实是因为 ziplist 的设计违背了设计的一个重要原则：高内聚，低耦合。当前节点的内容，居然被前一个节点的长度所控制！前一个节点变胖了，当前节点就必须跟着变胖。这就是连锁更新的万恶之源。

由于连锁更新过于致命，Redis 7.0 彻底废弃了 Ziplist，全面替换为 Listpack。

Listpack 的设计目标非常明确：

  1. 继续省内存：依然是一块连续的内存，依然没有 prev 和 next 指针。
  2. 彻底消灭连锁更新：任何节点的修改，绝不能影响其他节点的长度。

怎么做到呢？思路其实非常简单粗暴：每个节点，只记录自己的长度，绝不记录别人的长度！

Listpack 中一个节点（Entry）的结构变更为：[encoding] [data] [backlen]

  1. encoding：当前节点的编码类型（是字符串还是整数）。
  2. data：当前节点的实际数据。
  3. backlen (Back Length)：记录 当前节点的 encoding 自身大小 + data 大小之和。（注意：它不包含 backlen 自身的大小）。

向后遍历：指针站在节点起点，解析 encoding 得知其自身大小和 data 长度。指针向右跳过 encoding 和 data，此时来到 backlen 的起点。接着解析 backlen 自身占用的大小并跳过它，即可到达下一个节点。

没有了 prevlen，怎么从后往前遍历？我们把两个节点连起来看：... [A的编码] [A的数据] [A的backlen] | [B的编码] [B的数据] [B的backlen] ...

向前遍历：假设指针站在节点 B 的起点（即节点 A 的尾部外侧），想要回到节点 A 的起点。

  1. 指针向左退 1 个字节，接触到节点 A 的 backlen 的最后一个字节。
  2. backlen 采用了一种特殊的 从右向左解析的变长编码（Varint）：每个字节的最高位是标志位（0 表示这是 backlen 的首个字节，1 表示前面还有字节）。指针不断向左读取，直到遇到最高位为 0 的字节，从而完整解析出 backlen 记录的数值（即 A 的 encoding + data 的总长度）。
  3. 指针再向左跨越这个数值的长度，完美命中节点 A 的起点！

由于 Listpack 极其完美地解决了连锁更新的问题，同时在内存紧凑度上几乎和 Ziplist 一模一样（甚至因为少了一点状态信息，还稍微省了一点点），Redis 官方开始了一场浩浩荡荡的“替换运动”：

  1. Redis 5.0：引入了全新的数据结构 Stream。Stream 底层用来存储消息的结构，直接抛弃了 Ziplist，使用了全新的 Listpack。
  2. Redis 6.2：把 Hash 和 ZSet 的底层极度压缩结构，从 Ziplist 替换成了 Listpack。
  3. Redis 7.0（大结局）：把 List 底层的 Quicklist 中包含的 Ziplist 节点，也全部替换成了 Listpack。至此，Ziplist 完成了它的历史使命，从 Redis 的源码中被彻底移除。

Hash：Dict

当一个 Hash 对象包含的键值对极少（默认小于 512 个），且所有的键和值的字符串长度都很短（默认小于 64 字节）时，Redis 会使用 Listpack 来充当 Hash（以前是 ziplist）。

等等，Listpack 不是线性结构吗？怎么能当 Hash 用？

非常简单粗暴：Redis 直接把 Hash 的 Key 和 Value 作为两个连续的节点，紧挨着塞进 Listpack 中。

物理内存长这样：[Key1] [Value1] [Key2] [Value2] [Key3] [Value3] ...

  • 查询（HGET）：遍历 Listpack，每次跳过两个节点。比较当前节点的 Key 是否匹配，匹配则取下一个节点的值。虽然是 $O(N)$ 复杂度，但因为数据量极小，且 Listpack 是一块连续内存，CPU 缓存命中率极高，在微观层面它的速度甚至不亚于计算哈希值去查哈希表。
  • 好处：极度省内存！没有任何哈希冲突处理逻辑，没有任何指针开销。

当数据量突破阈值，Hash 会发生 底层编码转换，蜕变为真正的哈希表（Dict）。

Redis 的哈希表使用 链地址法 解决哈希冲突。

值得一提的是，为了抵御“哈希洪水攻击（HashDoS）”（黑客故意构造大量哈希值相同的 Key 让哈希表退化为单链表，耗尽 CPU），Redis 6.0 开始将哈希函数从 MurmurHash2 换成了具备加密强度的 SipHash。

最核心的设计：渐进式 Rehash

传统的哈希表在扩容时，会申请一块更大的新数组，然后把老数组里的所有数据重新计算哈希并搬运过去。如果 Redis 也这么干，会面临灭顶之灾，因为 Redis 处理命令是单线程的！

假设你的 Hash 里有 500 万个键值对，一次性搬运可能需要耗时数秒。在这几秒内，整个 Redis 将处于假死状态，任何其他命令都无法执行。

为了打破这个僵局，Redis 结构体 dict 内部并不是只有一个哈希表，而是 永远维护着两个哈希表：ht[0] 和 ht[1]，并附带一个索引变量 rehashidx（默认值为 -1）。

扩容过程：

  1. 准备新家：为 ht[1] 分配足够大的空间（通常是 ht[0] 当前容量的 2 倍）。将 rehashidx 设置为 0，标志着 Rehash 正式开始。
  2. 分摊搬运成本（事件驱动）：在此期间，每次对该 Hash 执行 HADD、HDEL、HGET 等命令时，Redis 除了执行本来要做的操作，还会顺手把 ht[0] 在 rehashidx 索引位置上的所有键值对，搬运到 ht[1] 中。搬完后，rehashidx 加 1。
  3. 兜底搬运（定时任务）：如果服务器很闲，没人来访问这个 Hash 怎么办？Redis 的后台定时任务 serverCron（每秒执行 10 次）会主动介入，每次给它 1 毫秒的时间去悄悄搬运。
  4. 大功告成：当 ht[0] 的所有数据都被搬空后，释放 ht[0]，将 ht[1] 篡位变成新的 ht[0]，并把 rehashidx 重置为 -1。

搬运期间的读写规则：

  • 查、删、改：先去 ht[0] 找，找不到再去 ht[1] 找。
  • 增（极其关键）：所有的新增数据，直接且只写入 ht[1]！ 这就保证了 ht[0] 里的数据只会越来越少，永远不会增加，最终一定会完成搬运的任务。

在很多介绍 Redis 的文章中，Dict（字典）和 Hashtable（哈希表）这两个词经常被混着讲，让人感觉它们是同一个东西。但它们完全不是一回事，而是严格的“包含（Has-A）”与“被包含”的关系。

用一句话总结：Hashtable 是纯粹的底层数据结构（负责物理存储），而 Dict 是一个更高级的面向对象封装（负责逻辑管理、多态和渐进式 Rehash）。

dictht（Dictionary Hash Table）就是我们在计算机基础课上学到的标准哈希表。它的唯一职责就是 存数据 和 解决哈希冲突。它非常纯粹，就是一个“数组 + 链表”的物理结构。如果有两个 Key 的哈希值算出来一样，它就用链表把它们串起来（链地址法）。它本身没有任何扩容（Rehash）的逻辑，也不知道存进来的 Key 和 Value 到底是什么类型。

1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table;      // 哈希表数组（指针的数组），真正装数据的地方
    unsigned long size;     // 哈希表当前的大小（比如 4, 8, 16...）
    unsigned long sizemask; // 掩码，总是等于 size - 1，用于计算哈希索引
    unsigned long used;     // 哈希表里已有的节点数量
} dictht;

dict（字典）才是 Redis 真正在业务层面使用的核心结构。它不直接存数据，而是管理着 Hashtable。

1
2
3
4
5
6
7
typedef struct dict {
    dictType *type;     // 指向不同类型字典的“方法大礼包”（实现多态的关键）
    void *privdata;     // 传给那些方法的私有参数
    dictht ht[2];       // 重点来了！这里直接包含了 2 个 Hashtable！
    long rehashidx;     // 记录渐进式 Rehash 进行到了哪个索引位置（-1 表示没在 Rehash）
    unsigned long iterators; // 当前正在遍历这个字典的迭代器数量
} dict;

发现了吗？一个 Dict 里面，塞了两个 Hashtable (ht[0] 和 ht[1])！

Set：Dict

Set 同样有两副面孔：Intset（整数集合） 和 Dict（字典）。

如果你往 Set 里存的都是数字，并且数量不多，Redis 会使用一种非常特殊的结构：Intset。

Intset 内部根本没有哈希表，它本质上是一个 严格递增排序的连续整数数组。

1
2
3
4
5
struct intset {
    uint32_t encoding; // 编码方式（决定每个元素占几个字节：16 位、32 位还是 64 位）
    uint32_t length;   // 元素数量
    int8_t contents[]; // 保存元素的连续数组
};
  • 查询性能（SISMEMBER）：因为数组是严格有序的，Redis 使用 Binary Search，时间复杂度 $O(\log N)$。
  • 动态升级：假设你一开始存的数字都是 1, 2, 3，Redis 发现它们用 16 位整数（int16_t，2 字节）就能装下，于是 encoding 被设为 16 位，数组里每个元素只占 2 字节。突然，你往里面 SADD 5000000000（一个超出 32 位范围的超大数字）。Redis 发现 int16_t 装不下了，会触发 数组升级：
    1. 将 encoding 修改为 int64_t（8 字节）。
    2. 按照 8 字节的大小重新计算并分配整个数组的内存。
    3. 将原来 2 字节的旧数据，在内存中从后向前移动，扩展为 8 字节，最后把新来的超大数字放到末尾。

Intset 只支持升级，不支持降级！ 即使你后来把那个超大数字删了，数组依然保持 8 字节的步长。

当满足以下两个条件之一时，Set 会从 Intset 转换为 Dict（哈希表）：

  1. 你试图插入一个非数字的字符串。
  2. 集合中的元素数量超过了阈值（set-max-intset-entries，默认 512 个）。

当使用 Dict 时，Dict 的 Key 存储 Set 的元素，而 Dict 的 Value 全部指向 NULL。这也是空间复用的一种典型体现。

ZSet：Dict + Skiplist

ZSet 是 Redis 中最复杂、也是最能体现数据结构之美的地方。它既要支持通过 Member 快速找到 Score，又要支持按照 Score 进行范围排序。这在单一数据结构中是绝对不可能完成的。因此，ZSet 的成年期采用了 “双剑合璧” 的架构：Dict + Skiplist。

老规矩，数据量小的时候（元素少于 128 个且每个长度小于 64 字节），ZSet 使用 Listpack。

物理布局：[Member1] [Score1] [Member2] [Score2] ...。

注意：此时 Listpack 内部会 严格按照 Score 从小到大 维护这串节点的物理顺序。每次插入都要挪动数据，但因为数据量极小，内存拷贝瞬间完成。

当数据量变大，ZSet 会同时创建一个 Dict 和一个 Skiplist。

  • Dict（字典）：存储 Member -> Score 的映射。当你执行 ZSCORE key member 时，直接查字典，$O(1)$ 返回分数。
  • Skiplist（跳跃表）：按照 Score 排序存储所有的 Member。当你执行 ZRANGE 或 ZRANGEBYSCORE 时，在跳表上游走，$O(\log N)$ 定位边界。

等等！同时建两份结构，Member 和 Score 的字符串岂不是要存两份？极其浪费内存？

antirez 早想到了：C 语言是指针的艺术。Dict 和 Skiplist 在底层 共享了 Member 和 Score 对象的内存地址，完全没有产生双份的数据冗余！

Skiplist

跳表是一种基于概率统计的随机化数据结构，在链表基础上增加了多级索引。它是一种典型的 “以空间换时间” 的多层链表结构。

核心特点：

  • 最底层包含所有元素，上层链表是下层的索引
  • 每个节点包含指向前驱、后继的指针，以及多层级的 “跳跃” 指针
  • 平均查找复杂度为 O(log N)，媲美平衡树
  • 相比平衡树，实现更简单，且支持高效的范围查询

概率平衡机制：不同于 AVL 树或红黑树通过旋转来维持严格平衡，跳表通过 “抛硬币” 的方式决定新节点的层数：

  • 插入新节点时，随机生成一个层数（通常幂次定律，层数越高概率越低，最高 32 层）
  • 这种随机性在宏观上能保证查询效率接近 O(log N)

为什么是跳表（Skiplist），而不是红黑树或 B+ 树？

antirez 亲自在邮件列表中给出了选择跳表的三个原因：

  1. 内存灵活性：一棵红黑树，每个节点必须强绑定 2 个指针（左子树、右子树），有时候还需要父节点指针。而在 Redis 的跳表实现中，节点晋升到高层的概率 $p=1/4$。用数学期望可以算出一个跳表节点平均只包含 1.33 个指针！这比红黑树省了大量指针内存。
  2. 高效的的范围查询：假设你要查排行榜第 50 名到 100 名的玩家。如果用红黑树，你找到第 50 名后，接下来需要在一棵复杂的树形结构里不断进行 中序遍历，指针忽上忽下，对 CPU 缓存极度不友好。而跳表的最底层，就是一条完美的 有序双向链表！找到第 50 名后，你只需要沿着底层的 next 指针“无脑”往后顺藤摸瓜即可，极其畅快。
  3. 实现简单：红黑树的插入和删除，伴随着令人抓狂的“左旋”、“右旋”和“颜色翻转”，稍有不慎就有 Bug。而跳表的插入，只需要调用一下随机函数 random() 决定层数，然后像修改普通链表一样改几个指针即可。跳表的 C 语言代码行数远低于红黑树，这非常符合 Redis “Keep It Simple” 的核心哲学。
数据库
#性能优化 #Redis #数据结构
Redis数据结构详解
https://gavinmo1.github.io/2026/02/28/Redis数据结构详解/
作者
Gavin
发布于
2026年2月28日
许可协议