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。
为什么是44呢？
实际redis中存储数据的最小SDS结构是SDS_TYPE_8，结构：
可以看出，一个最小的ＳＤＳ，至少占用３字节,再加上RedisObject的16个字节，也就是说一个最小的字符串是19个字节。
再了解下redis的内存分配器：jemalloc、tcmalloc。
这些内存分配器可以分配的大小2/4/8/16/32/64字节，可以看出最多分配64字节，即64K连续的内存。
64字节，减去RedisObject的16字节和SDS的3字节头信息，剩下45字节，再去除\0结尾，这样得出embstr可存储最大长度为64-16-3-1=44字节的字符串。?
底层数据编码格式转换
- 当 int 数据不再是整数，或大小超过了 long 的范围时，自动转化为 raw。
- 对于 embstr，由于其实现是只读的，因此在对 embstr 对象进行修改时，都会先转化为 raw 再进行修改。因此，只要是修改 embstr 对象，修改后的对象一定是 raw 的，无论是否达到了 44个字节。
ps:字符串追加空间扩展流程
?String的使用场景
number底层也是使用的String来实现的，所以可以用来实现自增、创建全局唯一的Id?、计数功能，另外还有分布式锁、位运算setbit