从根儿上理解 Redis（一）
简单动态字符串
Redis 底层使用 C 语言实现的，但是 Redis 没有直接使用 C 语言传统的字符串表示，而是构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型。
当 Redis 需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis 就会使用 SDS 来表示字符串值。
下面来看一下，为什么 Redis 会使用 SDS 而不是 C 字符串。
SDS 的定义
struct sdshdr{
//记录 buf 数组中已使用字节的数量
//等于 SDS 所保存字符串的长度
int len;
//记录 buf 数组中未使用字节的数量
int free;
//字节数组，用于保存字符串
char buf[];
}
image.png
上图是 SDS 结构实例，free 表示生于多少空间，len 表示占用了多少空间，末尾 ‘\0’ 不统计。buf 用于存储。
SDS 对比 C 字符串优势：
1.常数复杂度获取字符串长度，C 字符串获取长度需要遍历整个字符串。
2.杜绝缓冲区溢出，SDS 完全杜绝了缓冲区溢出，在新分配和拼接的时候，都会判断空间够不够。
3.减少修改字符串时带来的内存重分配次数。应用空间预分配和惰性kongjianshifang机制。
4.二进制安全，可以保存任意格式的二进制数据。
5.兼容部分 C 字符串函数。
链表
Redis 构建了自己的链表实现，当一个列表键包含了数量比较多的元素，又或者列表中包含的与那素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。
除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了链表。
链表节点结构：
typedef struct listNode{
struct listNode *prev;
struct listNode *next;
void *value;
}
多个 listNode 组成的双端链表
image.png
Redis 应用一个 list 结构来持有链表，如下：
typedef struct list{
//表头
listNode *head;
//表尾
listNode * tail;
//节点个数
unsigned long len;
//节点值复制函数
void (dup)(void ptr);
//节点释放函数
void (free)(void ptr);
//节点值对比函数
int (match)(void *ptr,void *key);
} list;
list 结构为链表提供了表头指针 head、表尾指针 tail、以及链表长度技术器 len，dup 函数用于复制节点所保存的值，free 函数用于释放链表节点所保存的值，match 函数用于对比链表节点所保存的值和另一个输入值是否相等。
list 示意图：
image.png
字典
字典，又称为符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。
Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表结点，每个哈希表结点就保存了字典中的一个键值对。
哈希表结构：
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值总是等于 size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
} dictht;
image.png
table 属性是一个数组，数组中每个元素都是一个指向 dictEntry 结构的指针，每个 dictEntry 结构保存着一个键值对。size 记录哈希表的大小，used 标识哈希表已有节点的数量。sizemark 总是等于 size - 1。
哈希表节点：
typedef struct dictEntry{
//键
void *key;
//值
union{
void *val;
unit64_tu64;
int64_ts64;
}v;
//指向下个哈希表节点，形成链表
struct dictEntry *next;
}dictEntry;
next 属性指向另一个哈希表节点指针，这个指针可以将多个哈希值相同的键值对连接在一起，来解决哈希冲突。
image.png
字典结构：
typedef struct dict{
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dict ht[2];
//rehash 索引
//当 rehash 不在进行时，值为 -1
int rehashidx;
}dict;
type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于特定类型键值对的函数。
privdata 属性保存了需要传给那些类型特定函数的可选参数。
image.png
跳跃表
跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
大部分情况下，跳跃表可以和平衡树相匹配。
Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。
跳表示例：
image.png
header：指向跳跃表的表头节点。
tail：指向跳跃表的表尾节点。
level：记录目前跳跃表内，层数最大的那个节点的层数。
length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量。
跳表节点每一层都有前进指针和跨度，跨度标识前进指针指向的节点和当前节点的距离。
每个节点都有一个后退指针，指向前一个节点。
1.0 2.0 3.0 是每个节点的分值，按顺序排列。
o1,o2,o3 是节点所保存的成员对象。
跳跃表节点
typedef struct zskiplistNode{
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span；
}level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
}zskiplistNode;
跳跃表
typedef struct zskiplist{
//表头节点和表尾节点
struct skiplistNode *header, *tail;
表中节点的数量
unsigned long length；
//表中层树最大的节点的层数
int level;
}zskiplist;
整数集合
整数集合是 Redis 用于保存整数值的集合抽象数据结构，可以保存的类型为 int16_t、int32_t 或者 int64_t 的整数，并且保证集合不会出现重复元素。
typedef struct intset{
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
}intset;
contents 是整数集合的底层实现，整数集合的每个元素都是 contents 数字的一个数组项。
length 属性记录了整数集合包含的元素数量。
encoding 决定 contents 数组的类型。
image.png
整数集合的升级
每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有元素的类型长，整数集合就要做升级。
升级分为三步:
1.根据新元素类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
例如下图，原本集合中的元素是 int16_t 类型的 1,2,3。然后将 65535 添加进去，因为 65535 是 int32_t 类型，所以就要做升级。
image.png
2.将底层数组现有元素转换成新元素相同类型，所有元素如下图，从后往前，一次重新放到新分配的空间的 3,2,1 的位置。
image.png
image.png
image.png
整数集合升级好处就是灵活性和尽可能的节约内存。
整数集合不支持降级操作。
压缩列表
压缩列表是列表键和哈希键的底层实现之一，当一个列表键只包含少量列表项，并且每个列表要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表键的底层实现。
压缩列表的构成：
image.png
image.png
压缩列表节点构成
每个压缩列表节点可以保存一个字节数组或者一个整数值。
image.png
previous_entry_length，记录了压缩列表中前一个节点的长度。
encoding，记录了节点的 content 属性所保存的数据类型及长度。
content，保存节点的值。
压缩列表有连锁更新机制，跟上面那个整数集合升级有点像。
previous_entry_length 记录了压缩列表中前一个节点的长度，previous_entry_length 的大小是一个字节，两个字节或者五个字节，根据前一个元素大小有关。但是假如在多小于 254 字节数之前添加一个大于等于 254 字节的数，后续的 previous_entry_length 都要挨个更新长度。
最后
至此 Redis 的底层数据结构就介绍完了，来看下下面这个表，Redis 使用的不同类型队形的编码方式。是不是就很清晰了。
image.png
参考：Redis 设计与实现
