数据结构分类

数据结构按键和值分类，可以分为两类，键值数据结构和值的数据结构。键值数据结构是hash表，用户通过键在hash表中找到值；值的数据结构又可以分为两类，API层面数据结构和底层数据结构。API层面的数据结构包括String、List、Set，Sorted Set，Hash，Bitmap；底层数据结构包括SDS（简单动态字符串）、dict（哈希表）、ziplist（压缩列表）、quicklist（双向链表）、skiplist（跳表），intset（整数数组）。值的底层数据结构是这篇文章介绍的重点。

值的底层数据结构

简单动态字符串

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）， 而是自己构建了一种名为 **简单动态字符串（simple dynamic string，SDS）**的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。（和Golang相同，我相信也是大多数语言的作法）

C字符串	SDS
获取字符串长度的复杂度为 O(N)	获取字符串长度的复杂度为 O(1)
API 是不安全的，可能会造成缓冲区溢出	API 是安全的，不会造成缓冲区溢出
修改字符串长度 N 次必然需要执行 N 次内存重分配	修改字符串长度 N 次最多需要执行 N 次内存重分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用所有 <string.h> 库中的函数	可以使用一部分 <string.h> 库中的函数

与 C 字符串不同， SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性： 当 SDS API 需要对 SDS 进行修改时， API 会先检查 SDS 的空间是否满足修改所需的要求， 如果不满足的话， API 会自动将 SDS 的空间扩展至执行修改所需的大小， 然后才执行实际的修改操作， 所以使用 SDS 既不需要手动修改 SDS 的空间大小， 也不会出现前面所说的缓冲区溢出问题

哈希表

普普通通的使用链表法的散列表，唯一需要注意的是渐进式rehash（这个和golang的symc.Map相同）。我们着重介绍一下渐进式rehash

渐进式rehash

dict的数据结构里包含 两个哈希表。在重哈希期间，数据从一个哈希表向另一个哈希表迁移。Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QqY9mkes-1609427803384)(./assets/1.jpg)]

压缩列表

ziplist 是一个经过特殊编码的 双向链表，它的设计目标就是为了提高存储效率。 ziplist 可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以 O(1)O(1) 的时间复杂度在表的两端提供 push 和 pop 操作。

一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用地址指针（或引用）连接起来。这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存。而 ziplist 却是将表中每一项存放在前后 连续的地址空间 内，一个 ziplist 整体占用一大块内存。它是一个表（list），但其实不是一个链表（linked list）。

另外，ziplist 为了在细节上节省内存，对于值的存储采用了 变长编码方式，大概意思是说，对于大的整数，就多用一些字节来存储，而对于小的整数，就少用一些字节来存储。ziplist 的底层结构如下所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y8hHLxho-1609427803397)(./assets/2.png)]

• zlbytes: 32bit，表示 ziplist 占用的字节总数。
• zltail: 32bit，表示 ziplist 表中最后一项（entry）在 ziplist 中的偏移字节数。
• zllen: 16bit， 表示 ziplist 中数据项（entry）的个数。 zllen 可以表达的最大值为 2^16-1。当 ziplist 长度超过 2^16−1 时， zllen 不表示长度，长度需要进行遍历计算。
• entry: 表示真正存放数据的数据项，长度不定。一个数据项（entry）也有它自己的内部结构。
• zlend: ziplist 最后1个字节，是一个结束标记，值固定等于 255。

quicklist（双向链表）

quicklist 是由 ziplist 为节点组成的双向链表。 ziplist 本身也是一个能维持数据项先后顺序的列表（按插入位置），而且是一个内存紧缩的列表（各个数据项在内存上前后相邻）。比如，一个包含 3 个节点的 quicklist ，如果每个节点的 ziplist 又包含 4 个数据项，那么对外表现上，这个 list 就总共包含 12 个数据项。
quicklist的设计是在空间和时间取了折中：

• 双向链表便于在表的两端进行 push 和 pop 操作，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
• ziplist 由于是一整块连续内存，所以存储效率很高。但是 不利于修改操作，每次数据变动都会引发一次内存的 realloc （扩容）。特别是当 ziplist 长度很长的时候，一次 realloc 可能会导致大批量的数据拷贝，进一步降低性能。

skiplist（跳表）

跳跃表（skiplist） 是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

intset（整数数组）

intset 是一个由整数组成的 有序集合，从而便于在上面进行二分查找，用于快速地判断一个元素是否属于这个集合。它在内存分配上与 ziplist 有些类似，是连续的一整块内存空间，而且对于大整数和小整数（按绝对值）采取了不同的编码，尽量对内存的使用进行了优化。

对于小集合使用 intset 来存储，主要的原因是节省内存。特别是当存储的元素个数较少的时候， dict 所带来的内存开销要大得多（包含两个哈希表、链表指针以及大量的其它元数据）。所以，当存储大量的小集合而且集合元素都是数字的时候，用 intset 能节省下一笔可观的内存空间。

API结构和底层结构对应关系

API数据结构	限制	底层数据结构（量小）	底层数据结构（量大）
string	512 MB	SDS	SDS
list	最大长度 2^32-1	quicklist	quicklist
set	最大长度 2^32-1	intset	dict
zset	最大长度 2^32-1	ziplist	dict+skiplist
hash	最大长度 2^32-1	ziplist	dict
bitmap	512 MB	SDS	SDS