数据类型与底层数据结构的关系

String

在Redis内部，string类型的底层储存结构是SDS。

SDS: 简单动态字符串 simple dynamic string

SDS的数据结构如下所示

typedef struct sdshdr {
    // buf中已经占用的字符长度
    unsigned int len;
    // buf中剩余可用的字符长度
    unsigned int free;
    // 数据空间
    char buf[];
}

既然C语言有字符串，为什么还需要重新设计一个SDS呢？原因有如下几点：

常数复杂度获取字符串长度

因为 C 字符串并不记录自身的长度信息， 所以为了获取一个 C 字符串的长度， 程序必须遍历整个字符串， 对遇到的每个字符进行计数， 直到遇到代表字符串结尾的空字符为止， 这个操作的复杂度为 O(N) 。

和 C 字符串不同， 因为 SDS 在 len 属性中记录了 SDS 本身的长度， 所以获取一个 SDS 长度的复杂度仅为 O(1) 。

二进制安全

C 字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

举个例子， 如果有一种使用空字符来分割多个单词的特殊数据格式， 如下图 所示， 那么这种格式就不能使用 C 字符串来保存， 因为 C 字符串所用的函数只会识别出其中的 “Redis” ， 而忽略之后的 “Cluster” 。

使用 SDS 来保存之前提到的特殊数据格式就没有任何问题， 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束

API是安全，杜绝缓冲区溢出(自动扩容)

因为 C 字符串不记录自身的长度， 所以 strcat(两个字符串相加) 假定用户在执行这个函数时， 已经为 dest 分配了足够多的内存， 可以容纳 src 字符串中的所有内容， 而一旦这个假定不成立时， 就会产生缓冲区溢出。

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

空间预分配

空间预分配用于优化 SDS 的字符串增长操作： 当 SDS 的 API 对一个 SDS 进行修改， 并且需要对 SDS 进行空间扩展的时候， 程序不仅会为 SDS 分配修改所必须要的空间， 还会为 SDS 分配额外的未使用空间。

其中， 额外分配的未使用空间数量由以下公式决定：

1）如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ， 那么程序分配和 len 属性同样大小的未使用空间， 这时 SDS len 属性的值将和 free 属性的值相同。 举个例子， 如果进行修改之后， SDS 的 len 将变成 13 字节， 那么程序也会分配 13字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。

2）如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB 的未使用空间。 举个例子， 如果进行修改之后， SDS 的 len 将变成 30 MB ， 那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。

通过空间预分配策略， Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。

惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作： 当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用 free 属性将这些字节的数量记录起来， 并等待将来使用。

兼容部分 C 字符串函数

虽然 SDS 的 API 都是二进制安全的， 但它们一样遵循 C 字符串以空字符结尾的惯例： 这些 API 总会将 SDS 保存的数据的末尾设置为空字符， 并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符， 这是为了让那些保存文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数。

Hash

参考：https://www.cnblogs.com/hunternet/p/12651530.html

hash是日常开发过程中使用Redis的一个数据结构，其底层实现方式有两种，如下所示。一种是zipList，这种是当hash结构的V值较小的时候使用的编码方式,另一种是字典dict

压缩列表zipList

同时满足以下条件使用压缩列表：

1.哈希对象保存的所有键值的字符串长度小于64字节；

2.哈希对象保存的键值对数量小于512个；

哈希表dict

哈希表dict类似于Java中的HashMap，字典dict采用连链地址法解决冲突碰撞问题。

参考：https://www.cnblogs.com/reecelin/p/13362104.html

List

参考：https://www.cnblogs.com/hunternet/p/12624691.html

List的底层使用压缩列表ziplist和双向链表list实现（3.0之后list键已经不直接用ziplist和linkedlist作为底层实现了，取而代之的是quicklist）

Set

参考：https://www.cnblogs.com/hunternet/p/12695738.html

Set的底层数据结构有两种：intset 和 hashtable。

intset

当一个集合满足以下两个条件时，Redis 会选择使用 intset 编码:

1.集合对象保存的所有元素都是整数值；

2.集合对象保存的元素数量小于等于 512 个（这个阈值可以通过配置文件 set-max-intset-entries 来控制）；

hashtable

哈希表

ZSet

参考：https://www.cnblogs.com/hunternet/p/12717643.html

有序集合对象的底层数据结构有两种：skiplist 和 ziplist

ziplist

当有序集合对象同时满足以下两个条件时，会使用 ziplist 编码进行存储:

1.有序集合对象中保存的元素个数小于 128 个（可以通过配置 zset-max-ziplist-entries 修改）；

2.有序集合对象中保存的所有元素的总长度小于 64 字节（可以通过配置 zset-max-ziplist-value 修改）；

skiplist

跳表：有索引的链表结构，查询效率可以媲美红黑树。