文章目录[隐藏]
Redis 数据结构
1. 简单动态字符串 SDS
我们都知道 Redis 中保存的 Key 是字符串，value 往往是字符串或者字符串的集合。可见字符串是 Redis 中最常用的一种数据结构
不过 Redis 没有直接使用 C 语言中的字符串，因为 C 语言字符串存在很多问题：
- 获取字符串长度的需要通过运算
- 非二进制安全
- 不可修改
Redis 构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称 SDS
例如，我们执行命令：
那么 Redis 将在底层创建两个 SDS，其中一个是包含“name”的 SDS，另一个是包含“虎哥”的 SDS
Redis 是 C 语言实现的，其中 SDS 是一个结构体，SDS 声明了很多对应长度的结构体
例如 SDS 8 位长度的结构体 sdshdr8 源码如下：
sdshdr8 代表该字符串的长度 len 最多由 8 位二进制位表示，也就是最长是 2^8-1 = 255，但是为了兼容 C 语言，最后也要包含一个'\0'，所以最长是 254 个字符，但是 Redis 读取时不会跟 C 语言一样将它作为结束标识来读，而是读取长度 len 个，是二进制安全的。然后还有 sdshdr16、sdshdr32、sdshdr64 等类型的 SDS 结构体，其最大长度各不相同。还有 sdshdr5，但是因为太小，已经弃用
上图右边的数字代表结构体中不同 sds 对应的 flag 的值
例如，一个包含字符串 “name” 的 sds 结构如下：
SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为 “hi” 的 SDS：
假如我们要给 SDS 追加一段字符串 “,Amy”，这里首先会申请新内存空间：
- 如果新字符串小于 1M，则新空间为扩展后字符串长度的两倍 + 1
- 如果新字符串大于 1M，则新空间为扩展后字符串长度 + 1M + 1
这种多扩展一些新空间的方式称为内存预分配
alloc = (2+4)*2 = 12 因为 alloc 不包含结束标识，但是后面的格子是 12+1=13 个
内存预分配：重新分配内存很消耗资源，预分配后若下次还需扩容，若空间足够就不用再分配了，减少内存分配次数
2. 整数集合 IntSet
IntSet 是 Redis 中 set 集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。结构如下：
这里的 contents 整数数组的类型 int8_t 不是只能存储 -128~127 的整数，而是由其 encoding 决定的；其中的 encoding 包含三种模式，表示存储的整数大小不同：
为了方便查找，Redis 会将 intset 中所有的整数按照升序依次保存在 contents 数组中，结构如图：
现在，数组中每个数字都在 int16_t 的范围内，因此采用的编码方式是 INTSET_ENC_INT16，每部分占用的字节大小为：
- encoding：4 字节
- length：4 字节
- contents：2 字节 * 3 = 6 字节（ 每个整数的大小取决于 encoding）
constants 数组是使用指针来指向内存中的地址，地址 = startPtr + (sizeof (int16)*index)，所以为了性能考虑，很多数组的脚标都从 0 开始
IntSet 升级编码：
现在，假设有一个 intset, 元素为 {5,10,20}，采用的编码是 INTSET_ENC INT16，则每个整数占 2 字节：
我们向该其中添加一个数字：50000，这个数字超出了 int16_t 的范围，intset 会自动升级编码方式到合适的大小。以当前案例来说流程如下：
- 升级编码为 INTSET_ENC_INT32, 每个整数占 4 字节，并按照新的编码方式及元素个数扩容数组
- 倒序依次将数组中的元素拷贝到扩容后的正确位置
- 将待添加的元素放入数组末尾
- 最后，将 inset 的 encoding 属性改为 INTSET_ENC_INT32，将 length 属性改为 4
升级源码如下：
小总结：
Intset 可以看做是特殊的整数数组，具备一些特点：
- Redis 会确保 Intset 中的元素唯一、有序
- 具备类型升级机制，可以节省内存空间
- 底层采用二分查找方式来查询
3. 哈希表 Dict
我们知道 Redis 是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过 Dict 来实现的
Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）
entry 的个数 used 是可以大于哈希表的大小 size 的，因为跟 Java 中一样，哈希冲突时，会使用一个链表来存储 hash 值相同的元素
当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash 值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1&3 = 1，因此 k1=v1 要存储到数组角标 1 位置
为什么使用 h & sizemask 与运算，而不使用求余运算？
哈希表的大小 size 初始大小为 4，且必须是 2^n，所以 sizemask = size - 1。在这种情况下，h & sizemask = h % size，并且位运算的速度通常比取模操作 更快
Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）
字典 > 哈希表 > 哈希节点
Dict 的扩容
Dict 中的 HashTable 就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。
Dict 在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：
- 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程
- 哈希表的 LoadFactor > 5
Dict 的收缩
Dict 除了扩容以外，每次删除元素时，也会对负载因子做检查，当 LoadFactor<0.1 时，会做哈希表收缩：
Dict 的 rehash
不管是扩容还是收缩，必定会调用 dictExpand（与下面 rehash 步骤中前 3 步相同）方法，其中会创建新的哈希表，导致哈希表的 size 和 sizemask 变化，而 key 的查询与 sizemask 有关。因此必须对哈希表中的 每一个 key 重新计算索引，插入新的哈希表，这个过程称为 rehash。过程是这样的：
- 计算新 hash 表的 realeSize，值取决于当前要做的是扩容还是收缩：
- 如果是扩容，则新 size 为第一个大于等于 dict.ht [0].used + 1 的 2^n
- 如果是收缩，则新 size 为第一个大于等于 dict.ht [0].used 的 2^n （不得小于 4）
- 按照新的 realeSize 申请内存空间，创建 dictht，并赋值给 dict.ht [1]
- 设置 dict.rehashidx = 0，标示开始 rehash
将 dict.ht [0] 中的每一个 dictEntry 都 rehash 到 dict.ht [1]（非渐进式哈希）
每次执行新增、查询、修改、删除操作时，都检查一下 dict.rehashidx 是否大于 -1，如果是则将 dict.ht [0].table [rehashidx] 的 entry 链表 rehash 到 dict.ht [1]，并且将 rehashidx++。直至 dict.ht [0] 的所有数据都 rehash 到 dict.ht [1]。（每次只 rehash 一个 entry 到 ht [1]）- 将 dict.ht [1] 赋值给 dict.ht [0]，给 dict.ht [1] 初始化为空哈希表，释放原来的 dict.ht [0] 的内存
- 将 rehashidx 赋值为 -1，代表 rehash 结束
- 在 rehash 过程中，新增操作，则直接写入 ht [1]，查询、修改和删除则会在 dict.ht [0] 和 dict.ht [1] 依次查找并执行。这样可以确保 ht [0] 的数据只减不增，随着 rehash 最终为空
Dict 的 rehash 并不是一次性完成的。试想一下，如果 Dict 中包含数百万的 entry, 要在一次 rehash 完成，极有可能导致主线程阻塞。因此 Dict 的 rehash: 是分多次、渐进式的完成，因此称为渐进式 rehash。流程如上列第 4 6 7 步
注：第三步只会在还未开始 rehash 时才会设置为 0 代表开始 rehash，因为用过源码我们可以看到，当正在 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（不得小于 4）
- Dict 采用渐进式 rehash，每次访问 Dict 时执行一次 rehash
- rehash 时 ht [0] 只减不增，新增操作只在 ht [1] 执行，其它操作在两个哈希表
Dict 的缺点：
- Dict 内部大量使用指针，内存空间不连续，通过指针链接，且容易产生内存碎片，造成严重的内存浪费
- 指针也会占据存储空间，大量指针占据很多内存
4. 压缩列表 ZipList
为节省内存，改善 Dict 哈希表的问题，出现了 ZipList
ZipList 是一种特殊的 “双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入 / 弹出操作，并且该操作的时间复杂度为 O (1)
不是双端链表，但有双端链表的特点，且内存块是连续的，不需要通过指针寻址
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4 字节 | 记录整个压缩列表占用的内存字节数 |
| zltail | uint32_t | 4 字节 | 记录压缩列表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址 |
| zllen | uint16_t | 2 字节 | 记录了压缩列表包含的节点数量。 最大值为 UINT16_MAX （65534），如果超过这个值，此处会记录为 65535，但节点的真实数量需要遍历整个压缩列表才能计算得出 |
| entry | 列表节点 | 不定 | 压缩列表包含的各个节点，节点的长度由节点保存的内容决定 |
| zlend | uint8_t | 1 字节 | 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端 |
ZipListEntry
ZipList 中的 Entry 并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用 16 个字节，浪费内存。而是采用了下面的结构：
- previous_entry_length：前一节点的长度，占 1 个或 5 个字节
- 如果前一节点的长度小于 254 字节，则采用 1 个字节来保存这个长度值
- 如果前一节点的长度大于 254 字节，则采用 5 个字节来保存这个长度值， 第一个字节为 0xfe，后四个字节才是真实长度数据
- encoding：编码属性，记录 content 的数据类型（字符串还是整数）以及长度，占用 1 个、2 个或 5 个字节
- contents：负责保存节点的数据，可以是字符串或整数
所以 entry 三个部分的长度都可以知晓，顺序遍历时只需要加上 entry 的长度，倒序遍历时只需要减去 pre_len
ZipList 中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值 0x1234，采用小端字节序后实际存储值为：0x3412
Encoding 编码
ZipListEntry 中的 encoding 编码分为字符串和整数两种：
-
字符串：如果 encoding 是以 “00”、“01” 或者 “10” 开头，则证明 content 是字符串
编码 编码长度 字符串大小 |00pppppp| 1 bytes <= 63 bytes(2^6) |01pppppp|qqqqqqqq| 2 bytes <= 16383 bytes(2^14) |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 5 bytes <= 4294967295 bytes(2^32) 例如，我们要保存字符串：“ab” 和 “bc”
zlbytes、zltail、zllen 等标表示长度的属性使用小端字节序
-
整数：如果 encoding 是以 “11” 开始，则证明 content 是整数，且 encoding 固定只占用 1 个字节
编码 编码长度 整数类型 11000000 1 int16_t（2 bytes） 11010000 1 int32_t（4 bytes） 11100000 1 int64_t（8 bytes） 11110000 1 24 位有符整数 (3 bytes) 11111110 1 8 位有符整数 (1 bytes) 1111xxxx 1 直接在 xxxx 位置保存数值，范围从 0001 ~ 1101 (十进制 1 ~ 13)，减 1 后结果为实际值（0 ~ 12） 例如：一个 ZipList 中包含两个整数值： “2” 和 “5”
连锁更新
ZipList 的每个 Entry 都包含 previous_entry_length 来记录上一个节点的大小，长度是 1 个或 5 个字节：
- 如果前一节点的长度小于 254 字节，则采用 1 个字节来保存这个长度值
- 如果前一节点的长度大于等于 254 字节，则采用 5 个字节来保存这个长度值，第一个字节为 0xfe，后四个字节才是真实长度数据
现在，假设我们有 N 个连续的、长度为 250~253 字节之间的 entry（前提），因此 entry 的 previous_entry_length 属性用 1 个字节即可表示，可是当 突然在前面插入一个长度大于 254 字节的 entry，就会发生连锁更新问题，如图所示：
ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生
概率很低，因为需要 N 个连续的、长度为 250~253 字节之间的 entry，条件较为苛刻
小总结：
ZipList 特性：
- 压缩列表的可以看做一种连续内存空间的” 双向链表”
- 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
- 如果列表数据过多，导致链表过长，可能影响查询性能
- 增或删较大数据时有可能发生连续更新问题
5. 快速列表 QuickList
问题 1：ZipList 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？
答：为了缓解这个问题，我们必须限制 ZipList 的长度和 entry 大小
问题 2：但是我们要存储大量数据，超出了 ZipList 最佳的上限该怎么办？
答：我们可以创建多个 ZipList 来分片存储数据
问题 3：数据拆分后比较分散，不方便管理和查找，这多个 ZipList 如何建立联系？
答：Redis 在 3.2 版本引入了新的数据结构 QuickList，它是一个双端链表，只不过链表中的 每个节点都是一个 ZipList
为了避免 QuickList 中的每个 ZipList 中 entry 过多，Redis 提供了一个配置项：list-max-ziplist-size 来限制
如果值为正，则代表 ZipList 的允许的 entry 个数的最大值
如果值为负，则代表 ZipList 的最大内存大小，分 5 种情况：
- -1：每个 ZipList 的内存占用不能超过 4kb
- -2：每个 ZipList 的内存占用不能超过 8kb
- -3：每个 ZipList 的内存占用不能超过 16kb
- -4：每个 ZipList 的内存占用不能超过 32kb
- -5：每个 ZipList 的内存占用不能超过 64kb
这里的单位是 KB 更为合理，使用 kb 很容易让人产生误解，但是 Redis 配置文件中声明了 1kb = 1024bytes
# Note on units: when memory size is needed, it is possible to specify # it in the usual form of 1k 5GB 4M and so forth: # # 1k => 1000 bytes # 1kb => 1024 bytes # 1m => 1000000 bytes # 1mb => 1024*1024 bytes # 1g => 1000000000 bytes # 1gb => 1024*1024*1024 bytes # # units are case insensitive so 1GB 1Gb 1gB are all the same.
其默认值为 -2：
除了控制 ZipList 的大小，QuickList 还可以对节点的 ZipList 做压缩。通过配置项 list-compress-depth 来控制。因为链表一般都是从首尾访问较多，中间节点的访问次数较少，所以首尾是不压缩的。这个参数是 控制首尾不压缩的节点个数：
- 0: 特殊值，代表不压缩
- 1: 标示 QuickList 的首尾各有 1 个节点不压缩，中间节点压缩
- 2: 标示 QuickList 的首尾各有 2 个节点不压缩，中间节点压缩
- 以此类推
其默认值为：0：
以下是 QuickList 的和 QuickListNode 的结构源码：
我们接下来用一段流程图来描述当前的这个结构
总结：
QuickList 的特点：
- 是一个节点为 ZipList 的双端链表
- 节点采用 ZipList，解决了传统链表的内存占用问题
- 控制了 ZipList 大小，解决连续内存空间申请效率问题（兼具链表和 ZipList 的优点）
- 中间节点可以压缩，进一步节省了内存
6. 跳表 SkipList
SkipList（跳表）首先是链表，但与传统链表相比有几点差异：
- 元素按照升序排列存储
- 节点可能包含多个指针，指针跨度不同，最高跨度可高达 32 层，由底层函数进行具体推算适合多少层跨度的指针
源码如下：
跳表的时间复杂度 是 log2N：
如果链表里有 N 个结点，会有多少级索引呢？
按照我们前面讲的，两两取首。每两个结点会抽出一个结点作为上一级索引的结点，以此估算：
- 第一级索引的结点个数大约就是 n/2，
- 第二级索引的结点个数大约就是 n/4，
- 第三级索引的结点个数大约就是 n/8，依次类推……
也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k 级索引结点的个数就是 n/(2^k)。最高级索引有 2 个，所以 n/(2^k) = 2 –> k = log2n - 1 ，算上原始链表，就是 log2n
跳表的空间复杂度是 O (N)：
比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢？
我们来分析一下跳表的空间复杂度
-
第一步：首先原始链表长度为 n，
-
第二步：两两取首，每层索引的结点数： n/2, n/4, n/8 … , 8, 4, 2 每上升一级就减少一半，直到剩下 2 个结点，以此类推；如果我们把每层索引的结点数写出来，就是一个等比数列
这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n) 。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。
-
第三步：思考三三取首，每层索引的结点数：n/3, n/9, n/27 … , 9, 3, 1 以此类推
第一级索引需要大约 n/3 个结点，第二级索引需要大约 n/9 个结点。每往上一级，索引结点个数都除以 3。为了方便计算，我们假设最高一级的索引结点个数是 1。我们把每级索引的结点个数都写下来，也是一个等比数列n/3+n/9+n/27+…+9+3+1=n/2。尽管空间复杂度还是 O(n) ，但比上面的每两个结点抽一个结点的索引构建方法，要减少了一半的索引结点存储空间。 所以空间复杂度是 O (n)
小总结：
SkipList 的特点：
- 跳跃表是一个双向链表，每个节点都包含 score 和 ele 值
- 节点按照 score 值排序，score 值一样则按照 ele 字典排序
- 每个节点都可以包含多层指针，层数是 1 到 32 之间的随机数
- 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
- 增删改查效率与红黑树基本一致，实现却更简单
7. RedisObject
Redis 中的任意数据类型的键和值都会被封装为一个 RedisObject，也叫做 Redis 对象，源码如下：
所以每个 Redis 对象头就要占据 16 个字节 (0.5+0.5+3+4+8)，所以推荐使用集合的类型来存储数据。比如：存储 10 个字符串需要 10 个对象头，也就浪费 160 个字节，若使用 list 来存储，只需要 1 个对象头
Redis 的编码方式：
Redis 中会根据存储的数据类型不同，选择不同的编码方式，共包含 11 种不同类型：
| 编号 | 编码方式 | 说明 |
|---|---|---|
| 0 | OBJ_ENCODING_RAW | raw 编码动态字符串 |
| 1 | OBJ_ENCODING_INT | long 类型的整数的字符串 |
| 2 | OBJ_ENCODING_HT | hash 表（字典 dict） |
| 3 | OBJ_ENCODING_ZIPMAP | 已废弃 |
| 4 | OBJ_ENCODING_LINKEDLIST | 双端链表（早期 Redis 使用） |
| 5 | OBJ_ENCODING_ZIPLIST | 压缩列表 |
| 6 | OBJ_ENCODING_INTSET | 整数集合 |
| 7 | OBJ_ENCODING_SKIPLIST | 跳表 |
| 8 | OBJ_ENCODING_EMBSTR | embstr 的动态字符串 |
| 9 | OBJ_ENCODING_QUICKLIST | 快速列表 |
| 10 | OBJ_ENCODING_STREAM | Stream 流 |
五种数据类型对应的编码：
Redis 中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：
| 数据类型 | 编码方式 |
|---|---|
| OBJ_STRING | int、embstr、raw |
| OBJ_LIST | LinkedList 和 ZipList（3.2 以前)、QuickList（3.2 以后） |
| OBJ_SET | intset、HT |
| OBJ_ZSET | ZipList、HT 和 SkipList |
| OBJ_HASH | ZipList、HT |
8. String
String 是 Redis 中最常见的数据存储类型：
底层实现⽅式：动态字符串 sds 或者 long
String 的内部存储结构⼀般是 sds（Simple Dynamic String，可以动态扩展内存），但是如果⼀个 String 类型的 value 的值是数字，那么 Redis 内部会把它转成 long 类型来存储，从⽽减少内存的使用
-
其基本编码方式是 RAW，基于简单动态字符串（SDS）实现，存储上限为 512MB
-
如果存储的 SDS 长度小于等于 44 字节，则会采用 EMBSTR 编码，此时 object head 与 SDS 是一段 连续空间。申请内存时只需要调用一次内存分配函数，效率更高
由图：若 SDS 长度为 44 字节，那么 RedisObject (对象头 16 字节)+SDS (采用 sdshdr8：1+1+1+44+1) 的大小刚好为 64 字节，Redis 底层分配内存的算法是 jemalloc，会以 2^n 做内存分配，而 64 字节刚好是 2^6，分配内存时不会产生内存碎片
-
如果存储的字符串是整数值，并且大小在 LONG_MAX 范围内，则会采用 INT 编码：直接将 数据保存在 RedisObject 的 ptr 指针位置（刚好 8 字节），不再需要 SDS 了
总结：
可使用 object encoding key 查看 key 的字符编码
确切地说，String 在 Redis 中是⽤⼀个 robj 来表示的，用来表示 String 的 robj 可能编码成 3 种内部表⽰：OBJ_ENCODING_RAW，OBJ_ENCODING_EMBSTR，OBJ_ENCODING_INT。其中前两种编码使⽤的是 sds 来存储，最后⼀种 OBJ_ENCODING_INT 编码直接把 string 存成了 long 型。在对 string 进行 incr, decr 等操作的时候：
- 如果它内部是 OBJ_ENCODING_INT 编码，那么可以直接进行加减操作
- 如果它内部是 OBJ_ENCODING_RAW 或 OBJ_ENCODING_EMBSTR 编码，那么 Redis 会先试图把 sds 存储的字符串转成 long 型，如果能转成功，再进行加减操作
对⼀个内部表示成 long 型的 string 执行 append, setbit, getrange 这些命令，针对的仍然是 string 的值（即⼗进制表示的字符串），而不是针对内部表⽰的 long 型进⾏操作
比如字符串“32”，如果按照字符数组来解释，它包含两个字符，它们的 ASCII 码分别是 0x33 和 0x32。当我们执行命令 setbit key 7 0 的时候，相当于把字符 0x33 变成了 0x32，这样字符串的值就变成了“22”。⽽如果将字符串“32” 按照内部的 64 位 long 型来解释，那么它是 0x0000000000000020，在这个基础上执⾏ setbit 位操作，结果就完全不对了。因此，在这些命令的实现中，会把 long 型先转成字符串再进行相应的操作
9. List
Redis 的 List 类型可以从首、尾操作列表中的元素：
哪一个数据结构能满足上述特征？
- LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
- ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
- QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个 ZipList，存储上限高（同时具备二者的优点）
Redis 的 List 结构类似一个双端链表，可以从首、尾操作列表中的元素：
在 3.2 版本之前，Redis 采用 ZipList 和 LinkedList 来实现 List，当元素数量小于 512 并且元素大小小于 64 字节时采用 ZipList 编码，超过则采用 LinkedList 编码。
在 3.2 版本之后，Redis 统一采用 QuickList 来实现 List：
10. Set
Set 是 Redis 中的单列集合，满足下列特点：
- 不保证有序性
- 保证元素唯一
- 求交集、并集、差集
可以看出，Set 对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？
HashTable，也就是 Redis 中的 Dict，不过 Dict 是双列集合（可以存键、值对）
Set 是 Redis 中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高
- 为了查询效率和唯一性，set 采用 HT 编码（Dict）。Dict 中的 key 用来存储元素，value 统一为 null
- 当存储的所有数据都是整数，并且元素数量不超过 set-max-intset-entries (默认值为 512) 时，Set 会采用 IntSet 编码，以节省内存
每次插入都会检查是否满足 都是整数 和 数量不超过 set-max-intset-entries 这两个条件，如果不满足，则会将 IntSet 编码转换为 HT 编码：
结构如下：
11. Zset
ZSet 也就是 SortedSet，其中每一个元素都需要指定一个 score 值和 member 值：
- 可以根据 score 值排序
- member 必须唯一
- 可以根据 member 查询分数
因此，zset 底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的哪种编码结构可以满足？
- SkipList：可以排序，并且可以同时存储 score 和 ele 值（member），但是无法根据 key 查询 val
- HT（Dict）：可以键值存储，并且可以根据 key 找 value，但是无法排序
所以 ZSet 选择全都要，在 RedisObject 和数据结构中间加了一层结构体 struct zset，如图：
o->encoding 只写了 SKIPLIST，但是其实是两种
此时使用 SkipList 和 Dict 的唯一缺点：内存占用太高
当元素数量不多时，HT 和 SkipList 的优势不明显，而且更耗内存。因此 zset 还会采用 ZipList 结构来节省内存，不过需要 同时满足两个条件：
- 元素数量小于 zset_max_ziplist_entries， 默认值 128
- 每个元素都小于 zset_max_ziplist_value 字节， 默认值 64
ziplist 本身没有排序功能，而且没有键值对的概念，因此需要有 zset 通过编码实现：
- ZipList 是连续内存，因此 score 和 element 是紧挨在一起的两个 entry， element 在前，score 在后
- score 越小越接近队首，score 越大越接近队尾，按照 score 值升序排列
ZSet 创建和新元素插入过程：
既然拥有 ZSet 和 ZipList 两种类型的编码，那么也会和 Set 一样出现编码转换的问题：
可以看到：ZipList 转化为 HT 和 SkipList 的条件除了上列的两个外，还有一个方法：ziplistSafeToAdd () ，内容是若 ZipList 的总大小超过 1G，也会转化为 HT 和 SkipList（ZSet 和 Hash 都这样），但是正常情况下，128 * 64 < 1G
12. Hash
hash 结构如下：
zset 集合如下：
Hash 结构与 Redis 中的 Zset 非常类似：
- 都是键值存储
- 都需求根据键获取值
- 键必须唯一
区别如下：
- zset 的键是 member，值是 score；hash 的键和值都是任意值
- zset 要根据 score 排序；hash 则无需排序
因此，Hash 底层采用的编码与 Zset 也基本一致，只需要把排序有关的 SkipList 去掉即可：
- Hash 结构默认采用 ZipList 编码，用以节省内存。 ZipList 中相邻的两个 entry 分别保存 field 和 value
- 当数据量较大时，Hash 结构会转为 HT 编码，也就是 Dict，触发条件有两个：
- ZipList 中的元素数量超过了 hash-max-ziplist-entries（默认 512）
- ZipList 中的任意 entry 大小超过了 hash-max-ziplist-value（默认 64 字节）
当满足上面两个条件其中之⼀的时候，Redis 就使⽤ dict 字典来实现 hash
可以看到：ZipList 转化为 HT 的条件除了上列的两个外，还有一个方法：ziplistSafeToAdd ()，内容是若 ZipList 的总大小超过 1G，也会转化为 HT（ZSet 和 Hash 都这样）
Redis 的 hash 之所以这样设计，是因为当 ziplist 变得很⼤的时候，它有如下几个缺点：
- 每次插⼊或修改引发的 realloc 操作会有更⼤的概率造成内存拷贝，从而降低性能
- ⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据
- 当 ziplist 数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为 ziplist 上的查找需要进行遍历
总之，ziplist 本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发⽣改动，就会引发内存 realloc，可能导致内存拷贝
