SDS Simple Dynamic String
SDS结构定义
struct sds{
// SDS所保存字符串长度，即buf数组中已使用字节数量
int len；
// buf数组中未使用字节的数量
int free；
// 保存字符串的字节数组
char[] buf;
}
相比C语言优势：
- 得到数组长度时间复杂度由O(n)变为O(1)，直接由len得到
- 自动扩容，确保buf数组不会溢出
- 减少修改字符串到来的内存重分配的次数
内存重分配策略
- 内存预分配（扩容）
对SDS进行修改后，SDS小于1M，分配len同样大小给free；大于等于1M的话，分配1M给free
- 惰性空间释放
会将多出的空间给free，避免后续的内存扩容；同时有需求的话，也提供了相应API做到真正的释放，避免内存浪费
链表
链表是列表键的底层实现之一，主要应用场景是列表键包含较多元素或者列表中包含的元素都是较长的字符串
链表节点定义
typedef struct listNode{
// 前置节点
struct listNode *prev；
// 后置节点
struct listNode *next；
// 节点的值
void *value；} listNode；
链表定义
typedef struct list
// 表头节点
listNode *head；
// 表尾节点
listNode *tail；
// 链表所包含节点数量
unsigned long len；
// 节点函数API(省略)
} list；
总结如下：
redis链表节点有prev和next，是个双端链表
redis表头节点的prev指向null，表尾节点的next指向null,无环节点
通过head和tail访问头尾节点的时间复杂度为O（1）
通过len可以直接得到链表长度
字典
字典是哈希键的底层实现之一，当一个哈希键包含的键值对较多或者键值对中元素是较长的字符串时，会使用字典
reis的字典使用哈希表作为底层实现，类似于hashmap的哈希表
字典的哈希表的结构定义
typedef struct dictht{
// 哈希表数组
dicEntry *table；
// 哈希表大小
unsigned long size；
// 哈希表大小的掩码，计算索引值（yuhashmap一样）
unsigned long sizemask；
// 哈希表已有节点的数量
unsigned long used；
} dictht；
redis字典结构定义
typedef struct dict{
// 类型特定函数
dicType *type；
// 私有数据
void privdata；
// 哈希表，一般情况下字典只使用ht[0],ht[1]会在rehash时使用
dictht ht[2];
// rehash 索引，当rehash不在进行时，值为-1
int trehashidx；
} dict；
rehash
进行rehash的步骤如下所示：
(1) 为ht[1]分配空间
如果是扩展操作，ht[1]大小是第一个大于等于ht[0]used2的2的n次方
如果是收缩操作，ht[1]大小是第一个大于等于ht[0]*used的2的n次方
(2) 将保存在ht[0]处的所有键值对rehash到ht[1]处
(3) 将ht[0]所有键值对迁移成功后，释放ht[0],将ht[1]设置为ht[0],ht[1]新创建一个空表，为下一次rehash做准备
渐进式rehash每次rehash一部分，然后将rehashidx值+1，最后完成后变为-1
跳跃表
跳跃表是一种有序数据结构，通过在每个节点维持多个指向其他节点的指针，从而达到快速访问节点的目的
跳跃表作为有序集合键的底层实现之一。如果一个有序集合元素数量较多，或者有序集合成员是较长的
跳跃表节点
typedef struct zskiplistNode{
// 层
struct zskiplistLevel{
// 前进指针
struct zskiplistNode *forward；
// 跨度
unsigned int span；
} level[];
// 后退指针
struct zskplistNode *backward;
// 分值
double score；
// 成员对象
obj *obj；
} zskiplistNode；
level数组即层数组，包括多个元素，每个元素包括一个指向其他节点的指针，即层数越多，访问其他节点速度越快
level[i].span，跨度，即两节点之间的距离，指向null的跨度为0.跨度用来计算排位
跳跃表结构
tyoedef struct zskiplist{
struct skiplistNode *header，*tail
// 表中节点数量
unsigned long length；
// 表中层数最大的节点的层数
int level；
} zskiplist；
整数集合
整数集合是集合键的底层结构之一，应用场景：集合只包含整数元素并且元素数量不多
intset结构
typedef struct intset{
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组，类型并不是int8_t，而是取决于encoding
int8_t contents[];
} intset;
inset中的元素保存在contents数组中，在数组中按值的大小排列。
升级
整数集合编码方式有int_16,int_32,int_64这三种，若是一直往content中放int_16的过程中，放入了一个int_32，全部数都要升级为int_32,若是再放入一个int_64,那么会全部升级为int_64,这样确保了类型的正确，往里边随便丢入数字不会出错。
注意只可以升级不支持降级
压缩列表
压缩列表是哈希键和列表键底层。场景：列表键只包含少量列表项，并且每项是小整数或者较短字符串
压缩列表是一系列特殊编码的内存块形成的顺序型存贮结构，包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值
列表的构成
| 属性 | 类型 | 用途 |
|---|---|---|
| zlbytes | uint_32t | 记录压缩列表占用的内存数 |
| zltail | uint_32t | 记录表尾指针距离压缩列表起始地址多少字节 |
| zllen | uint_16t | 记录压缩列表包含的节点数量（当数量小于65536就是这个值。否则的话需要便利） |
| entryX | 列表节点 | 压缩列表包含的节点，节点长度随内容而变 |
压缩列表节点的构成
previous_entry_length 记录前一个节点长度
该属性长度可以是1字节或者5字节（根据前一个节点长度是否<254)
根据这一属性可以由当前节点的起始地址计算前一个节点的起始地址，压缩列表的从表尾到表头节点就是根据这一原理实现的。一直向前回溯
这一属性引发的连锁更新
一连串的250-253字节大小的节点，所以这些节点的previous_entry_length大小都是1，若是在表头加一个255字节的，那么后边第一个的previous_entry_length就由1变成5，这第一个变化的节点大于254，后边以此继续下去造成连锁更新。
最坏的情况下，连锁反应需要N次空间重分配操作，每次重分配最坏复杂度为O(n).所以连锁最坏复杂度为O(n2).
####对象
redis键总是字符串，值有字符串/列表/哈希/集合/有序集合,对象type属性记录对象类型，类型包括以下4个
字符串对象可以被其余4个嵌套，比如列表中的字符串元素
列表对象
列表对象编码可以是ziplist或者linkedlist
ziplist底层实现是压缩列表，linkedlist底层是双端链表
哈希对象
哈希对象编码可以是ziplist或者hashtable
hashtable使用字典作为底层实现
集合对象
集合对象编码可以是intset或者hashtable
intset底层是整数集合
有序集合对象
有序集合对象编码可以是ziplist和skiplist
skiplist底层使用跳跃表实现
redis对象的多态
就列表对象来说，只管执行LLEN，如果底层是压缩列表，使用ziplistLen。如果底层是双端列表，使用listLength。
redis内存回收
redisObject中与有一个属性是refcount，创建一个新对象，初始化为1，被引用就+1，不再被程序引用就-1，成了0就释放。
对象的共享，redis会在初始化服务器时，创建10000个共享对象，包括0-9999，当用的0-9999，会引用这些共享变量。
对象的lru属性是上一次访问对象的时间，当前时间减去lru就是对象的空转时间。