简单动态字符串（SDS）

空间预分配

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

如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。如果对SDS进行修改之后，SDS的长度将大于等于1MB,那么程序会分配1MB的未使用空间。

链表

当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

redis的链表实现的特性可以总结如下：

双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是0(1)。

无环：表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点。

带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为0(1)。

带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为0(1)。

多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

哈希

当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。

哈希表结构

table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小，也即是table数组的大小，而used属性则记录了哈希表目前已有节点（键值对）的数量。sizemask属性的值总是等于size-1,这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面（哈希值与sizemask进行与运算）。

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：

哈希结点结构

下图就展示了如何通过next指针，将两个索引值相同的键k1和k0连接在一起。

Redis中的字典由dict.h/dict结构表示：

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。

除了ht[1]之外，另一个和rehash有关的属性就是rehashidx,它记录了rehash目前的进度，如果目前没有在进行rehash,那么它的值为-1。

rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor)维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩哈希表的工作可以通过执行rehash (重新散列）操作来完成，Redis对字典的哈希表执行rehash的步骤如下：

1) 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht [ 0 ] • used属性的值）：

•如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0] .Used*2 的2^N(2的n次方幂）；

•如果执行的是收缩操作，那么ht [ 1 ]的大小为第一个大于等于ht [ 0 ] . used的2^N。

2) 将保存在ht[0]中的所有键值对rehash到ht [1 ]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[l]哈希表的指定位置上。

3) 当ht[0]包含的所有键值对都迁移到了ht[l]之后（ht[0]变为空表），释放ht[0],将ht[l]设置为ht[0],并在ht[l]新创建一个空白哈希表，为下一次rehash 做准备。

渐进式rehash

rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

以下是哈希表渐进式rehash的详细步骤：

1 )为ht [ 1 ]分配空间，让字典同时持有ht [ 0 ]和ht [ 1 ]两个哈希表。

2) 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash 工作正式开始。

3) 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht [ 1 ],当rehash工作完成之后，程序将rehashidx属性的值增一。

4) 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht [ 1 ],这时程序将rehashidx属性的值设为-1，表不rehash操作已完成。

渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

整数集合

整数集合（intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。它可以保存类型为intl6_t, int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

整数集合结构体

contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项（item)，各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

length属性记录了整数集合包含的元素数量，也即是contents数组的长度。

虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值，encoding可以设置为INTSET_ENC_INT16，INTSET_ENC_INT32，INTSET_ENC_INT64。

升级与降级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade )

升级整数集合并添加新元素共分为三步进行：

1)根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

2) 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。

3) 将新元素添加到底层数组里面。

整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存。因为整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将intl6_t、int32_t或者int64_t类型的整数添加到集合中，而不必担心出现类型错误，这种做法非常灵活。

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

压缩列表

压缩列表是一种为节约内存而开发的顺序型数据结构，被用作set,hash和zset的底层实现之一。压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构，可以包含多个节点，每个节点可以保存一个字节数组或者整数值。

压缩列表节点的构成

节点的previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度。因为节点的previous_entry_length属性记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。压缩列表的从表尾向表头遍历操作就是使用这一原理实现的。

节点的content属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。

参考：《redis设计与实现》