本文将结合 Redis 原理，深入剖析 String、List、Hash、Set、ZSet 这五种核心数据类型的底层实现，以及它们在不同场景下的编码转换机制

【原理篇】

1.Redis数据结构

1.1动态字符串SDS

Redis中保存的key是字符串，value往往是字符串或者字符串的集合

Redis是用C语言编写的，但是没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

• 获取字符串长度需要通过运算
• 非二进制安全
• 不可修改

Redis构建了一种新的字符串结构，称为简单动态字符串SDS

例如我们执行命令set name 张三Redis将在底层创建两个SDS，其中一个包含"name"的SDS，另一个是包含"张三"的SDS

SDS本质是C语言中的结构体

为了节省内存，SDS（简单动态字符串）不再使用单一的结构，而是根据字符串的长度设计了 5 种不同的头部结构

SDS 类型	最大存储长度	头部占用空间	适用场景
sdshdr5		1 字节 (仅 flags)	几乎未被使用 (Redis 源码中仅定义了结构，实际很少用到)
sdshdr8		3 字节	存储短字符串（如 Key、短的 Value）
sdshdr16		5 字节	存储中等长度字符串
sdshdr32		9 字节	存储大字符串（如长文本、JSON）
sdshdr64		17 字节	存储超大字符串

预分配：防止内存频繁申请，消耗资源

优点：

1. 获取字符串长度的时间复杂度为O(1)
2. 支持动态扩容
3. 减少内存分配次数
4. 二进制安全

1.2IntSet

是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征

1. contents 是起始地址
   它指向了存储数据的连续内存块的开头。虽然代码里写的是 int8_t（1字节），可以理解为这块内存的起始坐标

2. encoding 是步长
   它决定了每个元素占多宽（是2字节、4字节还是8字节）

Encoding 宏定义	含义	元素宽度 (步长)	数据范围 (近似值)
INTSET_ENC_INT16	16位整数	2 字节	-32,768 ~ 32,767
INTSET_ENC_INT32	32位整数	4 字节	-21亿 ~ 21亿
INTSET_ENC_INT64	64位整数	8 字节	极大的数值范围

3. 查找公式
   当 Redis 想找第 i 个元素时，目标地址=contents起始地址+(i×encoding决定的步长)

怎么保证内存地址就是连续的？

在 Redis 的 intset 实现中，内存连续性是绝对保证的这主要归功于 C 语言的内存分配机制和 intset 的结构设计：创建数据时，操作系统返回的是一块连续的、未被分割的内存区域。这块区域里，除了 intset 自己的数据，没有“别人”能插进来

为了方便查找，Redis会将intSet中所有的整数按照升序依次保存在contents数组里

如果元素大小超过int16，intSet会自动升级

总结：

1. Redis会确保intSet中的元素唯一、有序
2. 具备类型升级机制，可以节省内存空间
3. 底层采用二分查找来查询

1.3Dict

Redis是一个键值型的数据库，可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict实现的

Dict由三部分组成，分别是：哈希表、哈希节点、字典

哈希表size大小size必须是2的幂次方

sizemask用于计算索引

当我们 向Dict添加键值对时，Redis先根据key计算出hash值(h)，然后利用h&sizemask来计算元素应该存储到数组的哪个索引位置

当哈希表的大小是 2 的幂次方时，h & (size - 1) 在数学上完全等价于 h % size，但在计算机底层，位运算 & 的速度要比取余运算 % 快得多

1.4Dict的渐进式rehash

Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然会导致哈希冲突增多，链表过长查询效率会大大减低

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size），满足以下情况就会触发哈希扩容：

• 哈希表的LoadFactor >= 1，并且服务器没有执行BGSAVE获取BGREWRITEAOF等后台进程

  如果还有后台进程，Redis会推迟扩容

• 哈希表的LoadFactor > 5

  这是一个安全底线，如果负载因子超过5，Redis会无条件、立刻进行扩容

Dict的收缩

除了扩容，每次删除元素时，也会对负载因子做检查，如果LoadFactor < 0.1时，会做哈希表收缩

Dict的rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。

但是rehash是在执行增删操作时判断是否要执行rehash，而这些操作是在Redis的主进程中进行的，若一次迁移太多的entry会导致主进程阻塞，直至完成rehash后才能处理新命令。

因此，Dict的rehash并不是一次性完成的。Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash。流程如下：

1. 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
   • 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的
   • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的 （不得小于4）
2. 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
3. 设置dict.rehashidx = 0，标示开始rehash
4. 每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entryl链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]
5. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
6. 将rehashidx赋值为-1，代表rehash结束
7. 在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

总结：

Dict的结构：

• 类似java的HashTable，底层时数组加链表来解决哈西冲突
• Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash

Dict的伸缩：

• 当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容
• 当LoadFactor小于0.1时，Dict收缩
• 扩容大小为第一个大于等于used + 1的2的n次方
• 收缩大小为第一个大于等于used 的2的n次方
• Dict采用渐进式rehash，每次访问Dict时执行一次rehash
• rehash时ht[0]只减不增，新增操作只在ht[1]执行，其他操作在两个哈希表

1.5ZipList

ZipList是一种特殊的双端链表，由一系列特殊编码的连续内存组成。可以在任意一端进行压入/弹出操作，操作的时间复杂度是O(1)

ZipListEntry

ZipList中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：

• previous_entry_length：前一节点的长度，占1个或5个字节。
  • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
• encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
• contents：负责保存节点的数据，可以是字符串或整数

Encoding编码

ZipListEntry中的encoding编码分为字符串和整数：

• 字符串：encoding以"00"、“01”、"10"开头

  

• 整数：encoding以"11"开头，且只占用1个字节

  

1.6ZipList的连锁更新问题

ZipList的每个Entry都包含previous_entry_length字段来记录上一个节点的大小。这个字段的长度是1个或5个字节：

• 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
• 如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，其中第一个字节为0xfe，后四个字节才是真实长度数据

连锁更新就是：当插入或删除一个节点导致其前后节点因空间不足而需要重新分配内存时，这种重分配会像多米诺骨牌一样向后传递，导致后续所有节点都需要依次进行内存重分配。

“概率低”指的是，在真实的业务数据中，恰好出现一长串（比如成百上千个）长度都精准地落在 250-253 字节这个狭窄区间内的节点，这种情况是极其罕见的

总结：

1. 压缩列表的可以看做一种连续内存空间的”双向链表“
2. 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
3. 如果列表数据过多，导致链表过长，可能影响查询性能
4. 增或删较大数据时有可能发生连续更新问题

1.7QuickList

QuickList就是一个双端链表，链表的每个节点都是一个ZipList

为了避免QuickList中每个ZipList中的Entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。

• 如果值为正，则代表ZipList的允许的entry个数的最大值

• 如果值为负，则代表ZipList的最大内存大小，分5种情况：

  • -1：每个ZipList的内存占用不能超过4kb

  • -2：每个ZipList的内存占用不能超过8kb

  • -3：每个ZipList的内存占用不能超过16kb4

  • -4：每个ZipList的内存占用不能超过32kb

  • -5：每个ZipList的内存占用不能超过64kb

其默认值为：-2

除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：

• 0：特殊值，代表不压缩
• 1：标示QuickList的首尾各有1个节点不压缩，中间节点压缩
• 2：标示QuickList的首尾各有2个节点不压缩，中间节点压缩
• 以此类推

默认值为0，默认不进行压缩

Redis 使用了一种叫 LZF 的压缩算法。

• 动作：它会把节点里原本占用的内存空间（比如 100KB），通过算法计算，变成一段更小的二进制数据（比如 60KB）。

总结

QuickList的特点：

• 是一个节点为ZipList的双端链表
• 节点采用ZipList，解决了传统链表的内存占用问题
• 控制了ZipList大小，解决连续内存申请效率问题
• 中间节点可以压缩，进一步节省了内存

1.8SkipList

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同

SkipList的特点：

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

1.9RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫Redis对象

Redis会根据存储的数据类型不同，选择不同的编码方式：

五种数据结构：

不同的数据结构也有不同的编码方式

只有最外层的那个 Key 和 最外层的那个 Value 才是 RedisObject。

举个例子，当你执行 ZADD myzset 1 "member1" 时：

• Key (myzset)：是一个 RedisObject。
• Value (整个有序集合)：是一个 RedisObject
• 这个 Value 对象的 ptr 指针指向底层的 zset 结构。
• 而这个 zset 结构里，包含了 SkipList 或 ZipList。

1.10五种数据类型

可以使用 OBJECT ENCODING <key> 命令来查看某个键当前的实际编码

String

String是Redis中最常见的数据存储类型，基于**简单动态字符串（SDS）**实现。String类型的底层编码方式有三种，分别是raw、embstr和int。

• raw

  当存储的字符串长度超过44字节时，会采用raw编码方式，存储上限为512mb

  RedisObject对象头和SDS对象在内存地址分别在两块不同的内存中分配，需要分配两次内存，性能较差

• embstr

  当存储的字符串长度小于等于44字节时，Redis使用embstr编码

  RedisObject 对象头和字符串数据（SDS）在一块连续的内存中分配。这种编码方式只需一次内存分配和释放，对于短字符串非常高效

• int

  当字符串的值是一个可以用 long 类型表示的整数时，使用int编码

  直接将整数值存储在 RedisObject 的 ptr 指针字段中，无需额外分配内存，效率极高

List

列表是有序的字符串集合，可以从头部或尾部进行快速的插入和删除操作

在Redis3.2之后，统一用QuickList来实现List

• quicklist

  quicklist 是双向链表和压缩列表 (ziplist) 的混合结构。链表中的每个节点都指向一个 ziplist。这种设计既保留了链表快速增删的优点，又通过 ziplist 实现了内存的紧凑存储，在性能和内存占用之间取得了很好的平衡

Set

集合是无序且元素唯一的字符串集合，支持交集、并集、差集等操作，对效率要求极高

• intset

  当集合对象同时满足以下两个条件时：

  1. 集合中所有元素都是整数
  2. 元素数量小于 set-max-intset-entries (默认 512)
  • 特点：使用整数集合存储，内存效率极高，并支持二分查找。一旦加入非整数元素或数量超标，编码会自动升级为 hashtable。

• Dict

  • 何时使用：当不满足 intset 的条件时。
  • 特点：使用标准的哈希表（字典）实现，可以存储任意类型的字符串。

ZSet

也就是SortedSet，每个元素需要指定一个score值和member值

可以根据score排序，member必须唯一

• ziplist 编码

  • 当有序集合对象同时满足以下两个条件时：
    1. 元素数量小于 zset-max-ziplist-entries (默认 128)。
    2. 所有元素的字符串长度都小于 zset-max-ziplist-value (默认 64 字节)。
  • 特点：使用压缩列表存储，元素和分数交替存放，非常节省内存。一旦不满足条件，编码会自动升级

• skiplist 编码

  • 当不满足 ziplist 的条件时。
  • 特点：这是 Redis 的招牌数据结构，由跳跃表 (skiplist) 和字典 (dict) 组合而成。跳跃表负责按分数排序，字典负责存储成员到分数的映射，保证了高效的范围查询和精确查找。

当元素数量不多时，Dict和SkipList的优势不明显，而且更耗内存，因此会采用ZipList结构来节省内存

Hash

与ZSet类似，都是键值存储，都需要根据键获取值，键必须唯一，但是无需排序

• **ziplist **
  • 当哈希对象同时满足以下两个条件时：
    1. 键值对的数量小于 hash-max-ziplist-entries (默认 512)。
    2. 所有键和值的字符串长度都小于 hash-max-listpack-value (默认 64 字节)。
  • 特点：使用压缩列表存储，内存非常紧凑。一旦不满足上述任一条件，编码会自动升级为 Dict。ZipList中相邻的两个Entry分别保存field和value
• Dict
  • 当数据量较大，不满足 ziplist 的条件时。
  • 特点：使用标准的哈希表（字典）实现，增删改查的时间复杂度为 O(1)，但内存开销相对较大