文章目录
redis常用数据结构以及底层编码
redis对象
在redis中，使用对象来表示数据库中的键值。redis中的对象可以用一个redisobject对象来表示。
在redis中有五种常用的数据类型：
| REDIS_String | 字符串对象 |
|---|---|
| Redis_LIST | 列表对象 |
| Redis_HASH | 哈希对象 |
| Redis_SET | 集合对象 |
| Redis_ZSET | 有序集合对象 |
这里需要强调的一点是，上面每种数据结构对象，其内部编码在不同的场景下可以有不同的实现，这里在后面分析具体的底层编码后会有具体的说明。
下图简要说明了redisobject的组成：
字符串对象
字符串对象使用的编码：
| 编码 | 对象 |
|---|---|
| REDIS_ENCODING_INT | 当字符串的值保存整数时使用 |
| REDIS_ENCODING_EMBSTR | 使用embstr编码的简单动态字符 |
| REDIS_ENCODING_RAW | 使用简单动态字符串实现的字符串对象 |
简单动态字符串（SDS）是什么？
redis没有使用c语言的字符串，而是自己实现了一个名为简单动态字符串的抽象类型，在redis数据库里面，字符串的键值对在底层都是由SDS实现的，这里需要说明的一点，sds还被用作缓冲区，AOF中的AOF缓冲区，客户端输入，输出缓冲区都是由SDS实现的。
SDS的结构：{
int len //记录字符串的长度，所以在获取字符串长度命令时，其时间复杂度为o（1）
设置和更新SDS长度的工作是由SDS的API在执行时自动完成的。
char buf[] //字节数组，用于保存字符串
int free // 记录buf数组中未使用字节的数量
}
SDS：有效的避免了缓冲区（buf）溢出：
当执行SDS API时，比如执行append命令时，API会先检查SDS的空间是否满足修改所需的要求，如果空间大小不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小。然后才执行实际的修改操作。
修改字符串的值可能带来的问题：
- 如果对字符串进行增长，如上述所说，需要进行内存分配来扩展底层buf数组空间的大小，如果没有这一步内存分配，就会造成缓冲区溢出。
- 如果对字符串修改后，缩短了字符串，那么就需要重新分配内存释放掉字符串缩短的那部分内存空间，如果没有做，就会产生内存泄漏。
内存分配需要执行系统调用，所以通常是比较耗时的操作，在SDS中，通过未使用空间free，实现了空间预分配和惰性空间释放两种优化策略。
空间预分配
对SDS修改后，SDS的长度（len）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS的len属性的值，将和free属性的值相同。即相当于把未使用的值扩展为现在buf数组已使用的值，如果下次对字符串进行增长，增长长度小于free的值，就不会进行内存分配，只有在下次buf数组不够用时，才会再次按照上述规则进行再次进行内存分配。
惰性空间释放
当需要缩短SDS保存的字符串时，不会立即使用内存重分配来回收缩短的字节，而是使用free属性将这些字节的数量记录下来，并等待将来使用。这种策略，避免了缩短字符串所需的内存重分配操作，并为可能出现的增长操作提供了优化。
介绍完了SDS，下面我们继续回到字符串对象的介绍，并比较raw编码与embstr编码的区别：
如果字符串对象保存的字符串的值长度>39字节，那么字符串对象将使用一个SDS来保存字符串的值，并将对象的编码设置为raw。
如果字符串对象保存的字符串的值长度<=39字节，那么字符串对象将使用一个SDS来保存字符串的值，并将对象的编码设置为embstr。
embstr与raw两者之间的差异：
embstr：是用于保存短字符串的一种优化编码方式，embstr编码与raw编码一样，都是用redisobject与sds结构来表示字符串对象，但是raw编码会调用两次内存分配函数分别创建redisobject结构和sds结构（所以sds能够表示较长的字符串），而embstr编码则通过调用一次内存分配函数来分配一块连续的内存空间，空间中依次包含redisobject与sds结构。
embstr优点：
将创建字符串对象所需内存分配次数降低了1次，只需要执行一次内存释放函数就可以释放。
说明:
我们可以在redis中使用long,double类型的浮点数，但是浮点数在redis是以字符串值来保存的，如果保存一个浮点数，会先将浮点数转化成字符串值，然后保存转换所得到的的字符串值。
Redis中没有为embstr编码的字符串对象编写任何相应的修改程序（只有int编码的字符串对象和raw编码的字符串对象有修改程序）即embstr编码的字符串对象只是可读的，当对embstr编码的字符串对象执行修改命令时，会先将对象的编码从embstr转换成raw，然后再执行修改命令。
使用场景：
- 计数器：因为redis的单线程机制，所以不会存在并发技术冲突。
- 缓存
- 分布式锁
列表对象：
列表对象编码：
| 编码 | 对象 |
|---|---|
| REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的列表对象 |
| REDIS_ENCODING_LinkeList | 使用双端链表实现的列表对象 |
编码:
下面介绍列表底层编码：
链表：
特性：
链表为双端链表，获取某个节点的前端节点与后端节点的复杂度都是o（1）
链表没有环，表头节点的prev指针还有表尾节点的next指针都是null，获取表头节点和表尾节点的复杂度为o（1）
链表自己维护了链表长度属性len，所以获取长度的时间复杂度为o（1）。
使用场景：
发布与订阅功能，慢查询，监视器
redis服务器本身还使用了链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。
压缩列表
压缩列表是列表键和哈希键的底层实现之一：
当列表只包含少量的列表项，且列表项是小整数值，或者长度比较短的字符串，redis就会使用压缩列表来做列表的底层实现。
当哈希键只包含少量键值对，并且键值对的键和值要么就是小整数值，或者长度比较短的字符串
redis就会使用压缩列表来做哈希键的底层实现。
压缩列表可能出现的问题（连锁更新）：
如果在压缩列表中存在连续的几个节点的长度在251-253间，那么它们的pre_length属性都为1个字节，如果其中任意一个节点长度发生变化增加，那么后面的节点的pre_length都需要扩容到5字节，造成一系列节点的连续扩容，会对系统性能造成很大的影响。
哈希对象
| 编码 | 对象 |
|---|---|
| REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的对象 |
| REDIS_ENCODING_HT | 使用字典实现的哈希对象 |
ziplist
哈希对象编码如果是ziplist，每当有新的键值对加入到哈希对象时，会先将键的压缩列表节点推入到压缩列表表尾，然后将保存了值的压缩列表节点推入到压缩列表表尾。所以保存了同一个键值对的两个节点总是紧挨在一起，键在前，值在后。
hashtable
hastable编码的哈希对象，使用字典作为底层实现，哈希对象中的每个键值对，都使用一个字典键值对来保存。字典的每个键都是一个字符串对象，对象中保存了键值对的键，字典中的每个值都是一个字符串对象，对象中保存了键值对的值。
字典对象结构图：
转换
当哈希对象中保存的所有键值对的键和值的字符串长度都小于64字节，当哈希对象保存的键值对的数量小于512个，都会使用ziplist作为hash对象底层编码。
集合对象
| 编码 | 对象 |
|---|---|
| REDIS_ENCODING_INTSET | 使用整数集合实现的集合对象 |
| REDIS_ENCODING_ZIPLIST | 使用字典实现的有序集合对象 |
编码之间的相互转换
当满足集合对象保存的所有元素都是整数值，并且集合对象保存的元素数量不超过512个
时会使用整数集合实现的集合对象，注意当使用字典作为集合的底层实现时，字典中的dictEntry键为元素，值为null。
有序集合对象
| 编码 | 对象 |
|---|---|
| REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的有序集合对象 |
| REDIS_ENCODING_SKIPLIST | 使用跳跃表和字典实现的有序集合对象 |
这里重点介绍一下skiplist编码的有序集合，它使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。
zset结构中的跳跃表按照分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的object属性，保存了元素的成员，跳跃表节点的score属性保存了元素的分值。通过这个跳跃表，就可以进行范围性操作。但是如果我们想要根据元素查询分值，只有跳跃表的话，时间复杂度就会变成o(logn)，所以引入字典为有序集合创建一个从成员到分值的映射，字典的dictEntry中的键保存元素，而值保存元素的分值。基于此，就可以用o（1）复杂度查找给定成员的分值。
总的来说，redis选择了用时使用字典和跳跃表两种数据结构来实现有序集合，让有序集合的查找和范围型操作都尽可能快的执行。
编码之间的相互转换：
当有序集合保存的元素数量小于128，并且保存的所有元素成员的长度都小于64字节，会采用ziplist编码实现有序集合，任一条件不满足都会采用skiplist编码。