redis包含5种常用数据结构

String 、List、Hash、Set 、Zset

基础铺垫

以set为例

redis其实可以理解为 K-V数据库，因此对每个键值对都会有一个 dictEntry，里面存储了指向 Key 和 Value 的指针；next 指向下一个 dictEntry，与本 Key-Value 无关

key

可以看出 key不是直接存的字符串，而是一个SDS结构

value

value既不是存的String，也不是存的SDS结构，而且用的RedisObject结构

RedisObject

实际上，不论 redis存储的值是 5 种类型的哪一种，都是通过 RedisObject 来存的；

RedisObject 中的 type 字段指明了要存的值的类型，即：String/List/Set/Zset/Hash中的一个；
RedisObject 中的encoding表示底层使用的编码格式，为了提供存储效率和执行效率，每种数据类型的底层结构不止一种
RedisObject 中的ptr 字段则指向对象所在的地址。可以看出，字符串对象虽然经过了 RedisObject 的包装，但仍然需要通过 SDS 存储。

所以，每种类型都是通过设置RedisObject中的这三个属性来实现存值的。

SDS结构与其他语言字符串结构比较

1.获取字符串长度复杂度

由于SDS结构中含有len属性，所以获取字符串长度的复杂度为o(1);而对于其他语言来说，获取字符串的长度需要遍历字符串计数来实现，时间复杂度o(n);

2.字符串的内存重分配次数

其他语言由于不记录字符串长度，所以要修改字符串必须重新分配内存。SDS实现了空间预分配和惰性释放两种策略：

空间预分配：当SDS的API 对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，不仅会为SDS分配修改所需的空间，还会为SDS额外分配空间，这样可以减少连续执行字符串增长操作所需内存分配次数。
惰性释放：当 SDS 的 API 需要对 SDS 保存的字符串进行缩短时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用，

3.二进制安全

二进制安全（binary-safe）：指能处理任意的二进制数据，包括非 ASCII 和 null 字节。C 字符串以空字符 '\0'，作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串'\0'，导致程序读入的空字符会被误认为是字符串的结尾，因此C字符串无法正确存取二进制数据；SDS 的 API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS 不是以空字符串'\0'来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束，因此 Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据。

4.C字符串函数兼容

SDS 的buf数组会以'\0'结尾，这样可以重用 C 语言库<string.h> 中的一部分函数，避免了不必要的代码重复。

5.API安全性与缓冲区溢出

缓冲区溢出（buffer overflow）：会存在这样的一种异常，当程序将数据写入缓冲区时，会超过缓冲区的边界，并覆盖相邻的内存位置。在 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出

由于 SDS 记录了自身长度，同时在修改时，API 会按照如下步骤进行：

（1）先检查SDS的空间是否满足修改所需的要求；

（2）如果不满足要求的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小；

（3）然后才执行实际的修改操作；

所以SDS不会造成缓冲区溢出情况

一、String

字符串存储过程分为两步：1、选择合适的SDS类型；2、选择合适的encoding编码格式;

1、选择合适的SDS类型

根据值value的长度选择对应的SDS类型

源码分析

根据位移计算可知 1<<8 = 2^8=256，单位是字节。也就是说，每种类型的SDS可存储的字节数如下：

SDS_TYPE_5　-- 32 Byte
SDS_TYPE_8　-- 256 Byte
SDS_TYPE_16 -- 64KＢ
SDS_TYPE_32 -- ...
SDS_TYPE_64 -- ...

2、选择合适的encoding编码格式

Redis的全部底层数据结构有：

redis_encoding_int (long类型的整数)

redis_encoding_embstr (embstr编码的简单动态字符串)

redis_encoding_raw (简单动态字符串)

redis_encoding_ht (字典）

redis_encoding_linkedlist （双端链表）

redis_encoding_ziplist（压缩列表）

redis_encoding_intset（整数集合）

redis_encoding_skiplist（跳跃表和字典）

字符串的底层encoding编码结构是 int，raw 或者 embstr。

embstr 和 raw比较

好处：embstr 的使用只分配一次内存空间(因此 RedisObject 和 sds 是连续的)，而 raw 需要分配两次内存空间(分别为 RedisObject 和 sds 分配空间)。因此与 raw 相比，embstr 的好处在于创建时少分配一次空间，删除时少释放一次空间，以及对象的所有数据连在一起，寻找方便。

坏处: 而embstr 的坏处也很明显，如果字符串的长度增加需要重新分配内存时，整个 RedisObject 和 sds 都需要重新分配空间，因此 Redis 中的 embstr 实现为只读。

如果一个字符串内容可转为 long，那么该字符串会被转化为 long 类型，对象 ptr 指向该 long，并且对象类型也用 int 类型表示。普通的字符串有两种 embstr 和 raw。如果字符串对象的长度小于 44字节，就用 embstr，否则用 raw。