本篇文章主要针对redis常见的对象以及其对应的存储结构进行整理，前面已经写了字符串和字典的存储结构。下面将先对其它存在的存储结构进行简介，然后对每一种对象使用到的存储结构进行整理并说明在什么情况下会发生变化。
存储结构简介
链表
链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。 作为一种常用数据结构，链表内置在很多高级的编程语言里面，因为Redis使用的C语言并没有内置这种数据结构，所以Redis构建了自己的链表实现。
链表在Redis中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现
redis使用的是双端链表，如图3-1所示
Redis的链表实现的特性可以总结如下：
- 双端：链表节点带有prev和next指针，获取某个节点的前置节点和 后置节点的复杂度都是O（1）。
- 无环：表头节点的prev指针和表尾节点的next指针都指向NULL， 对链表的访问以NULL为终点。
- 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。
- 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O（1）。
- 多态：链表节点可以用于保存各种不同类型的值
跳跃表
跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持 多个指向其他节点的指针，从而达到快速访问节点的目的。 跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可 以通过顺序性操作来批量处理节点。 在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。
Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员 （member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。
整数集合
整数集合（intset）是集合键的底层实现之一，当一个集合只包含整 数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
整数集合（intset）是Redis用于保存整数值的集合抽象数据结构， 它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。
刚开始添加整数的时候，redis会选择合适的整数类型来创建数组，后续每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级 （upgrade），然后才能将新元素添加到整数集合里面。 升级整数集合并添加新元素共分为三步进行：
- 根据新元素的类型，扩展整数集合底层数组的空间大小，并为 新元素分配空间。
- 将底层数组现有的所有元素都转换成与新元素相同的类型，并 将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需 要继续维持底层数组的有序性质不变。
- 将新元素添加到底层数组里面
升级的优点：
- 提升整数集合的灵活性 因为C语言是静态类型语言，为了避免类型错误，通常不会将两种不同类型的值放在同一个数据结构里面。整数集合可以通过自动升级底层数组来适应新元素，从而保证数组中只有一种类型
- 尽可能地节约内存：整数集合现在的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存。
整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直 保持升级后的状态。
压缩列表
压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的 连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包 含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。
下图是压缩列表的存储结构，以及每个片段对应的含义。
其中除了entryx不确定外，其它都是定长的。entry的结构如下
每个压缩列表节点都由previous_entry_length、encoding、content三个部分组成
- previous_entry_length：记录前一个节点的长度，属性的长度可以是1字节或者5 字节：
- 如果前一节点的长度小于254字节，那么previous_entry_length属性 的长度为1字节：前一节点的长度就保存在这一个字节里面。
- 如果前一节点的长度大于等于254字节，那么previous_entry_length 属性的长度为5字节：其中属性的第一字节会被设置为0xFE（十进制值 254），而之后的四个字节则用于保存前一节点的长度。
- encoding：记录了节点的content属性所保存数据的类型以及长度，字节的高比特为记录类型，低bit为记录数据长度
- content：负责保存节点的值，节点值可以是一个字节数组 或者整数
存在的问题：会出现连锁更新
简单的说，如果已存在的，如果新插入一个节点，其长度大于254，因为后续节点的字节长度是1字节，所以需要将其字节长度扩展子5字节，这样就会导致其节点长度发生变化，如果恰好这个节点扩展后，也大于254，就会导致后面的页发生变化，接着后面的如果也是，则也会更新，从而引发连锁更新。
要注意的是，尽管连锁更新的复杂度较高，但它真正造成性能问题 的几率是很低的：
- 首先，压缩列表里要恰好有多个连续的、长度介于250字节至253 字节之间的节点，连锁更新才有可能被引发，在实际中，这种情况并不多见；
- 其次，即使出现连锁更新，但只要被更新的节点数量不多，就不 会对性能造成任何影响：比如说，对三五个节点进行连锁更新是绝对不会影响性能的；
添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引 发连锁更新操作，但这种操作出现的几率并不高。
对象
陆续介绍了Redis用到的所有主要数据结构，比如简单动态字符串（SDS）、双端链表、字典、压缩列表、整数集合等等。
Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。
通过这五种不同类型的对象，Redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
除此之外，Redis的对象系统还实现了基于引用计数技术的内存回 收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会 被自动释放；另外，Redis还通过引用计数技术实现了对象共享机制， 这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。
最后，Redis的对象带有访问时间记录信息，该信息可以用于计算 数据库键的空转时长，在服务器启用了maxmemory功能的情况下，空转 时长较大的那些键可能会优先被服务器删除。
先简单介绍下一些概念
- 类型： 就是上面所获的字符串、列表等类型，可以通过
TYPE命令来看 - 编码：表示对象使用的底层结构，比如SDS，链表，压缩列表等，可以通过
OBJECT ENCODING命令。
字符串
字符串对象的编码可以是int、raw或者embstr。
int: 用来保存可以用long表示的数字
embstr编码是专门用于保存短字符串的一种优化编码方式，这种编码和raw编码一样，都使用redisObject结构和sds结构来表示字符串对象，但raw编码会调用两次内存分配函数来分别创建redisObject结构和sds结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sdshdr两个结构。
embstr编码的好处是：将创建字符串对象所需的内存分配次数从raw编码的两 次降低为一次。 释放embstr编码的字符串对象只需要调用一次内存释放函数，而释 放raw编码的字符串对象需要调用两次内存释放函数。 因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起raw编码的字符串对象能够更好地利用缓存带来的优势。
编码之间的转换
对于int编码的字符串对象来说，如果我们向对象执行了一些命令，使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串对 象的编码将从int变为raw。
因为Redis没有为embstr编码的字符串对象编写任何相应的修改程序（只有int编码的字符串对象和raw编码的字符串对象有这些程序），所以embstr编码的字符串对象实际上是只读的。当我们对embstr 编码的字符串对象执行任何修改命令时，程序会先将对象的编码从 embstr转换成raw，然后再执行修改命令。因为这个原因，embstr编码的字符串对象在执行修改命令之后，总会变成一个raw编码的字符串对象。
列表对象
列表对象的编码可以是压缩列表或者链表。
当列表对象可以同时满足以下两个条件时，列表对象使用ziplist编码：
- 列表对象保存的所有字符串元素的长度都小于64字节；
- 列表对象保存的元素数量小于512个；不能满足这两个条件的列表 对象需要使用linkedlist编码
以上两个条件的上限值是可以修改的，具体请看配置文件中关于 list-max-ziplist-value选项和list-max-ziplist-entries选项的说明。
哈希对象
哈希对象的编码可以是压缩列表或者字典对象
ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键 值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到 压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表 尾，因此：
- 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在 前，保存值的节点在后；
- 先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而 后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码：
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字 节；
- 哈希对象保存的键值对数量小于512个；不能满足这两个条件的哈 希对象需要使用hashtable编码。
这两个条件的上限值是可以修改的，具体请看配置文件中关于hash- max-ziplist-value选项和hash-max-ziplist-entries选项的说明。
集合对象
集合对象的编码可以是intset或者hashtable。
当集合对象可以同时满足以下两个条件时，对象使用intset编码：
- 集合对象保存的所有元素都是整数值；
- 集合对象保存的元素数量不超过512个。
不能满足这两个条件的集合对象需要使用hashtable编码。
第二个条件的上限值是可以修改的，具体请看配置文件中关于set- max-intset-entries选项的说明。
有序集合对象
有序集合的编码可以是ziplist或者skiplist。
ziplist编码的压缩列表对象使用压缩列表作为底层实现，每个集合 元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素 的成员（member），而第二个元素则保存元素的分值（score）。
压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素 被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向。
skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。
zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score属性则保存了元素的分值。通过这个跳跃表，程序可以对有序集合进行范围型操作，比如ZRANK、ZRANGE 等命令就是基于跳跃表API来实现的。
除此之外，zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O（1）复杂度查找给定成员的分值，ZSCORE命令就是根据这一 特性实现的，而很多其他有序集合命令都在实现的内部用到了这一特性。
有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。值得一提的是，虽然zset结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元 素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。
为什么有序集合需要同时使用跳跃表和字典来实现？
在理论上，有序集合可以单独使用字典或者跳跃表的其中一种 数据结构来实现，但无论单独使用字典还是跳跃表，在性能上对比起同时使用字典和跳跃表都会有所降低。举个例子，如果我们只使 用字典来实现有序集合，那么虽然以O（1）复杂度查找成员的分 值这一特性会被保留，但是，因为字典以无序的方式来保存集合元 素，所以每次在执行范围型操作——比如ZRANK、ZRANGE等命 令时，程序都需要对字典保存的所有元素进行排序，完成这种排序 需要至少O（NlogN）时间复杂度，以及额外的O（N）内存空间 （因为要创建一个数组来保存排序后的元素）。 另一方面，如果我们只使用跳跃表来实现有序集合，那么跳跃 表执行范围型操作的所有优点都会被保留，但因为没有了字典，所 以根据成员查找分值这一操作的复杂度将从O（1）上升为 O（logN）。因为以上原因，为了让有序集合的查找和范围型操作 都尽可能快地执行，Redis选择了同时使用字典和跳跃表两种数据 结构来实现有序集合。
当有序集合对象可以同时满足以下两个条件时，对象使用ziplist编码：
- 有序集合保存的元素数量小于128个；
- 有序集合保存的所有元素成员的长度都小于64字节；
不能满足以上两个条件的有序集合对象将使用skiplist编码。
以上两个条件的上限值是可以修改的，具体请看配置文件中关于 zset-max-ziplist-entries选项和zset-max-ziplist-value选项的说明。
内存回收
因为C语言并不具备自动内存回收功能，所以Redis在自己的对象系 统中构建了一个引用计数（reference counting）技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。
对象共享
当服务器考虑将一个共享对象设置为键的值对象时，程序需要 先检查给定的共享对象和键想创建的目标对象是否完全相同，只有 在共享对象和目标对象完全相同的情况下，程序才会将共享对象用 作键的值对象，而一个共享对象保存的值越复杂，验证共享对象和 目标对象是否相同所需的复杂度就会越高，消耗的CPU时间也会越 多：
- 如果共享对象是保存整数值的字符串对象，那么验证操作的 复杂度为O（1）；
- 如果共享对象是保存字符串值的字符串对象，那么验证操作 的复杂度为O（N）；
- 如果共享对象是包含了多个值（或者对象的）对象，比如列 表对象或者哈希对象，那么验证操作的复杂度将会是O（N2）。
因此，尽管共享更复杂的对象可以节约更多的内存，但受到 CPU时间的限制，Redis只对包含整数值的字符串对象进行共享。
目前来说，Redis会在初始化服务器时，创建一万个字符串对象， 这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到 9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。
创建共享字符串对象的数量可以通过修改 redis.h/REDIS_SHARED_INTEGERS常量来修改。
对象的空转时长
对象有一个属性记录了其最新一次访问的时间。
OBJECT IDLETIME命令可以打印出给定键的空转时长，这一空转 时长就是通过将当前时间减去键的值对象的最新一次访问时间计算得出的。
OBJECT IDLETIME命令的实现是特殊的，这个命令在访问键的值 对象时，不会修改值对象的最后一次访问事件属性。
除了可以被OBJECT IDLETIME命令打印出来之外，键的空转时长 还有另外一项作用：如果服务器打开了maxmemory选项，并且服务器用 于回收内存的算法为volatile-lru或者allkeys-lru，那么当服务器占用的内 存数超过了maxmemory选项所设置的上限值时，空转时长较高的那部分 键会优先被服务器释放，从而回收内存。 配置文件的maxmemory选项和maxmemory-policy选项的说明介绍了 关于这方面的更多信息。