Redis原理篇—数据结构

笔记整理自 b站_黑马程序员Redis入门到实战教程

底层数据结构

动态字符串SDS

我们都知道 Redis 中保存的 Key 是字符串，value 往往是字符串或者字符串的集合。可见字符串是 Redis 中最常用的一种数据结构。

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

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

Redis 构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称 SDS。

例如，我们执行命令：

那么 Redis 将在底层创建两个 SDS，其中一个是包含“name”的 SDS，另一个是包含“虎哥”的 SDS。

Redis 是C语言实现的，其中 SDS 是一个结构体，源码如下：

例如，一个包含字符串“name”的 sds 结构如下：

SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的 SDS：

假如我们要给 SDS 追加一段字符串“,Amy”，这里首先会申请新内存空间：

如果新字符串小于 1M，则新空间为扩展后字符串长度的两倍+1；
如果新字符串大于 1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

IntSet

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

结构如下：

其中的 encoding 包含三种模式，表示存储的整数大小不同：

contents[] 数组中真正存的是什么，是由 encoding 来决定的，它决定数组中每一个整数的大小、范围。

contents 充当了一个指针，指向数组中第一个元素的地址，所以对于这个数组的遍历以及增删改查都由 intset 自己控制了。

为了方便查找，Redis 会将 intset 中所有的整数按照升序依次保存在 contents 数组中，结构如图：

现在，数组中每个数字都在 int16_t 的范围内，因此采用的编码方式是 INTSET_ENC_INT16，每部分占用的字节大小为：

Header 头部共占 8 个字节：
- encoding：4 字节
- length：4 字节
contents：2 字节 * 3 = 6 字节

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 中的元素唯一、有序
具备类型升级机制，可以节省内存空间
底层采用二分查找方式来查询

Dict

我们知道 Redis 是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过 Dict 来实现的。

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

我们先来分析 哈希表(DictHashTable) 和 哈希节点(DictEntry) 结构：

当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash值(h)，然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1 & 3 =1，因此 k1=v1 要存储到数组角标 1 位置。

再来分析 字典(Dict) 结构：

Dict 的扩容

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

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

哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
哈希表的 LoadFactor > 5；

Dict 的缩容

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

Dict 的 rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的 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 的 rehash 并不是一次性完成的。试想一下，如果 Dict 中包含数百万的 entry，要在一次 rehash 完成，极有可能导致主线程阻塞。因此 Dict 的 rehash是分多次、渐进式的完成，因此称为渐进式 rehash。
- 每次执行新增、查询、修改、删除操作时，都检查一下 dict.rehashidx 是否大于 -1，如果是则将 dict.ht[0].table[rehashidx] 的 entry 链表 rehash 到 dict.ht[1]，并且将 rehashidx++。直至 dict.ht[0] 的所有数据都 rehash 到 dict.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 最终为空。

整个过程可以描述成：

未 rehash 前：
rehash：

加入新元素 dictEntry<k5, v5>，需要扩容
- 先以新的容量创建哈希表，并保存到 ht[1] 中，ht[0] 中的所有旧元素重新计算 hash 值，将元素迁移到新的哈希表中，且 rehashidx 置为 0。
- 此时将 ht[1] 赋值给 ht[0]，并将 ht[1] 置为 null，即完成 rehash。 rehashidx 置回 -1。

源码解析

// 无论是扩容、缩容、初始化都是调用的 dictExpand 方法
int dictExpand(dict *d, unsigned long size) {// 底层调用了 _dictExpand 方法return _dictExpand(d, size, NULL);
}||\/
/** 真正的rehash方法*/
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{if (malloc_failed) *malloc_failed = 0;// 如果当前entry数量超过了要申请的size大小，或者正在rehash，直接报错if (dictIsRehashing(d) || d->ht[0].used > size)return DICT_ERR;// 声明新的hash tabledictht n; /* the new hash table */// 实际大小，第一个大于等于size的2^n次方unsigned long realsize = _dictNextPower(size);/* Detect overflows 超出LONG_MAX，说明内存溢出 报错*/if (realsize < size || realsize * sizeof(dictEntry*) < realsize)return DICT_ERR;/* Rehashing to the same table size is not useful. 新的size如果与旧的一致，报错*/if (realsize == d->ht[0].size) return DICT_ERR;/* Allocate the new hash table and initialize all pointers to NULL */// 重置新的hash table大小和掩码n.size = realsize; n.sizemask = realsize-1;if (malloc_failed) {n.table = ztrycalloc(realsize*sizeof(dictEntry*));*malloc_failed = n.table == NULL;if (*malloc_failed)return DICT_ERR;} else // 分配内存：size * entrySizen.table = zcalloc(realsize*sizeof(dictEntry*));// 已使用个数初始化为0，代表这是一个全新的哈希表n.used = 0;/* Is this the first initialization? If so it's not really a rehashing* we just set the first hash table so that it can accept keys. * 如果是第一次，直接把n赋值给ht[0]即可*/if (d->ht[0].table == NULL) {d->ht[0] = n;return DICT_OK;}// 否则，要么是扩容，要么是收缩，需要rehash，此处只需要把rehashidx置为0即可。在每次增、删、改、查时都会触发rehash。/* Prepare a second hash table for incremental rehashing */d->ht[1] = n; // 此时就用到了ht[1]d->rehashidx = 0; // rehashidx置为0，标志rehash已经开始了（-1表示未开始）// 这里并未做迁移操作，直接返回了，这只是分配了内存而已。那什么时候做呢？在每次执行新增、查询、修改、删除操作时进行迁移。return DICT_OK;
}/* Our hash table capability is a power of two 2^n */
static unsigned long _dictNextPower(unsigned long size)
{unsigned long i = DICT_HT_INITIAL_SIZE;if (size >= LONG_MAX) return LONG_MAX + 1LU;while(1) {if (i >= size)return i;i *= 2;}
}

小总结

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] 执行，其它操作在两个哈希表

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 ），用于标记压缩列表的末端。

ZipList-Entry

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

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

注意：

ZipList 中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值 0x1234，采用小端字节序后实际存储值为：0x3412。

Encoding 编码

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

字符串：如果 encoding 是以“00”、“01”或者“10”开头，则证明 content 是字符串。

编码	编码长度	字符串大小
\|00pppppp\|	1 bytes	<= 63 bytes
\|01pppppp\|qqqqqqqq\|	2 bytes	<= 16383 bytes
\|10000000\|qqqqqqqq\|rrrrrrrr\|ssssssss\|tttttttt\|	5 bytes	<= 4294967295 bytes

例如，我们要保存字符串：“ab”和“bc”：

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

整数：如果 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 后结果为实际值

由此看出，ZipList 中各种各样的编码，最终的目的就是尽可能的节省（压缩）内存，所以在 redis 内部，ZipList 的使用场景还是非常多的，后续讲解不同的数据类型就会讲到。但其实它也有一定的使用限制，因为 ZipList 在遍历时，只能从前向后或者从后向前遍历，假如它保存的节点数量非常多，那么这个列表就会非常长，而如果查找的元素恰好在中间的某个位置，我们就需要遍历很多个节点才能找到它（查询方式跟链表类似，但更加节省内存），因此 ZipList 在使用的时候，往往都会对节点的个数有一定的限制。

ZipList 的连锁更新问题

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

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

现在，假设我们有 N 个连续的、长度为 250~253 字节之间的 entry，因此 entry 的 previous_entry_length 属性用 1 个字节即可表示，如图所示：

此时如果在头结点添加一个 254 字节，记录前一个节点的值就需要 5 个字节，整个 entry 节点就占据了 254 字节，然后每一个后面的节点都需要更新 previous_entry_length 属性的值，导致发生了一连串的更新。

ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。

小总结

ZipList特性：

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

出现的概率很低，但还是有可能发生的。那这个问题真的没有办法解决吗？

也并不是，其实在 redis 新版本中，作者引入了一个新的数据结构：listpack 紧凑列表，虽然这个列表引入到 redis 当中了，但是目前仅仅在 stream 底层结构使用了，并没有运用到常见的比如：List、Set 这些结构当中，可能是因为改动产生的影响比较大，因为 ZipList 在 redis 中用的范围太广了，要改的东西非常的多，所以 redis 依然使用的是 ZipList。

关于 listpack的文章可以参考：listpack如何遍历？如何解决ziplist连锁更新问题？(五)

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
其默认值为 -2：

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

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

以下是 QuickList 的和 QuickListNode 的结构源码：

我们接下来用一段流程图来描述当前的这个结构：

compress 值为 1，代表首尾各有 1 个节点不压缩，中间节点压缩，所以首尾两个节点是完整的 ziplist，有 zlbytes、zltail、zllen、zlend 属性，中间是 entry。而中间的两个节点则做了压缩处理，将来读取数据还要做解压缩。

小总结

QuickList 的特点：

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

SkipList

在前面我们学习的 ZipList、QuickList 这两种列表，它们的共同特点就是非常节省内存，不过它们在遍历元素时，要么从头到尾遍历，要么从尾到头遍历，因此它们在查找首尾元素时性能还是不错的；但是你如果想从中间随机查询，那样性能就不怎么好了。不过我们如果需要从中间查询，那么就需要用到这个数据结构：SkipList。

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

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

源码如下：

底层储存的值其实是用 sds 存储的，那么为什么在上方的图都是以数字表示呢？其实这个数字是上面 zskiplistNode 中的 score 属性，用来做排序、查找用的，像索引，而真正的数据是挂载在节点上的。

小总结

SkipList 的特点：

跳跃表是一个双向链表，每个节点都包含 score 和 ele 值。
节点按照 score 值排序，score 值一样则按照 ele 字典排序。
每个节点都可以包含多层指针，层数是 1 到 32 之间的随机数（由 SkipList 的底层函数控制，根据算法推测多少层合适）。
不同层指针到下一个节点的跨度不同，层级越高，跨度越大。
增删改查效率与红黑树基本一致，实现却更简单。

RedisObject

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

什么是 redisObject

从 Redis 的使用者的角度来看，⼀个 Redis 节点包含多个 database（非 cluster 模式下默认是 16 个，cluster 模式下只能是 1 个），而一个 database 维护了从 key space 到 object space 的映射关系。这个映射关系的 key 是 string 类型，⽽ value 可以是多种数据类型，比如：string、list、hash、set、sorted set 等。我们可以看到，key 的类型固定是 string，而 value 可能的类型是多个。

⽽从 Redis 内部实现的⾓度来看，database 内的这个映射关系是用⼀个 dict 来维护的。dict 的 key 固定用⼀种数据结构来表达就够了，这就是动态字符串 sds。而 value 则比较复杂，为了在同⼀个 dict 内能够存储不同类型的 value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是 robj，全名是 redisObject。

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	双端链表
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

String

String 是 Redis 中最常见的数据存储类型：

其基本编码方式是 RAW，基于简单动态字符串（SDS）实现，存储上限为 512mb。

robj 的 ptr 指针指向的是一个 SDS 对象，这个 SDS 对象是一片独立的内存空间，所以创建这个 String 时需要先申请 RedisObject 的内存空间，再申请 SDS 对应的内存空间，所以它需要两次内存的申请操作，将来释放也需要两次内存的释放操作。
如果存储的 SDS 长度小于 44 字节，则会采用 EMBSTR 编码，此时 object head 与 SDS 是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。

而为什么 SDS 的长度需要小于 44 字节呢？是因为 SDS 的头尾此时共占 4 字节，加上内容的长度共占 48 字节，而 RedisObject 的头占据 16 字节，加起来刚好 64 字节，而这个数组有什么特殊之处呢？这个就跟 redis 内存分配的方式有关了，redis 底层采用内存分配的算法是 jemalloc，它在分配内存时会以 $2^n$ 去做内存分配，而 64 恰好是一个分片大小，因此不会产生内存分片。这就是为什么以 44 字节为限制的原因。
如果存储的字符串是整数值，并且大小在 LONG_MAX 范围内，则会采用 INT 编码：直接将数据保存在 RedisObject 的 ptr 指针位置（刚好 8 字节），不再需要 SDS 了。

底层实现⽅式：动态字符串 sds 或者 long。

String 的内部存储结构⼀般是 sds（Simple Dynamic String，可以动态扩展内存），但是如果⼀个 String 类型的 value 的值是数字，那么 Redis 内部会把它转成 long 类型来存储，从⽽减少内存的使用。

确切地说，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 型先转成字符串再进行相应的操作。

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：

Set

Set 是 Redis 中的单列集合，满足下列特点：

不保证有序性
保证元素唯一
求交集、并集、差集

可以看出，Set 对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？
- HashTable，也就是 Redis 中的 Dict，不过 Dict 是双列集合（可以存键、值对）。
Set 是 Redis 中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高。
- 为了查询效率和唯一性，set 采用 HT 编码（Dict）。Dict 中的 key 用来存储元素，value 统一为 null。
- 当存储的所有数据都是整数，并且元素数量不超过 set-max-intset-entries 时，Set 会采用 IntSet 编码，以节省内存。

但要注意一点，IntSet 编码并不是永久性的，如果违背了上面两个条件其中之一，就不能用 IntSet 存储了，所以每一次插入新元素时，Set 集合都会去检查这两个条件，只要违背了任意一个，就会从 IntSet 编码转换为 HT 编码，代码如下：

set-max-intset-entries 的默认值是 512：

结构如下：

IntSet
HT

ZSet

ZSet 也就是 SortedSet，其中每一个元素都需要指定一个 score 值和 member 值：

可以根据 score 值排序后
member 必须唯一
可以根据 member 查询分数

因此，zset 底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的哪种编码结构可以满足？

SkipList：可以排序，并且可以同时存储 score 和 ele 值（member）
HT（Dict）：可以键值存储，并且可以根据 key 找 value

结构如下：

HT 可以快速的找到对应的 value（score），SkipList 负责排序，范围查询。

当元素数量不多时，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 在添加元素时，也会判断编码方式是否应该转变，判断 ziplist 的两个条件是否违背，如果违背则需要转成 HT + SkipList。

Hash

Hash 结构与 Redis 中的 ZSet 非常类似：

都是键值存储
都需求根据键获取值
键必须唯一

区别如下：

zset 的键是 member，值是 score；hash 的键和值都是任意值
zset 要根据 score 排序；hash 则无需排序

底层实现方式：压缩列表ziplist 或者 字典dict

当 Hash 中数据项比较少的情况下，Hash 底层才⽤压缩列表 ziplist 进行存储数据，随着数据的增加，底层的 ziplist 就可能会转成 dict，具体配置如下：

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

当满足上面两个条件其中之⼀的时候，Redis 就使⽤ dict 字典来实现 hash。

Redis 的 hash 之所以这样设计，是因为当 ziplist 变得很大的时候，它有如下几个缺点：

每次插⼊或修改引发的 realloc 操作会有更⼤的概率造成内存拷贝，从而降低性能。
⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更大的⼀块数据。
当 ziplist 数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为 ziplist 上的查找需要进行遍历。

总之，ziplist 本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发生改动，就会引发内存 realloc，可能导致内存拷贝。

hash 结构如下：

zset 集合如下：

因此，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 字节）