1. 简单动态字符串（SDS）
Redis 的字符串数据类型是个包装了字节数组的结构体。它的结构是这样的：
struct sdshdr {
int len;
int free;
char buf[];
}
其中，
- buf 是字节数组
- len 记录了 buf 中保存字符串的长度
- free 记录 buf 字节数组中空闲位置的数量
实际 len(buf) == len + free + 1，这是因为 SDS 中存的字符串结尾总会有一个空字符 \0，但对于使用者是透明的。使用这一特性是为了方便重用一些 C 语言的库函数。
SDS 优点
Redis 中使用 SDS（Simple Dynamic String），有以下优点：
- 计算长度的复杂度为 O(1)
- 先自检再修改，杜绝缓冲区溢出
- 修改时减少内存重分配次数（预分配和惰性释放）
- 二进制安全
- 兼容部分 C 语言库函数
“先自检再修改”，对于 C 语言的话，在拼接字符串时都需要先手动检查内存空间够不够再可以拼接，不然可能会造成缓冲区溢出，即覆盖其他已用内存。
“减少内存重分配次数”，在字符串修改时，增长字符串要注意缓冲区溢出，剪短字符串要注意回收内存避免内存泄露。SDS 自动处理了这两个问题。空间预分配就是在分配一些额外备用的空间，即 free 字段所示。具体策略是，在分配时，若 len<1M 那free 是等量的；当 len>=1M 时，free 总是 1M。
惰性释放，就说在有需要时，释放 free 记录的空间。
2. 链表
提供节点重排，顺序访问的能力。
链节点的结构定义：
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value; // 节点的值
} listNode;
链表的结构定义：
typedef struct list {
listNode *head;
listNode *tail;
unsigned long len; // 节点总数量，读取长度 O(1)
void *(*dup) (void *ptr); // 复制函数，多态，根据数据类型而变化
void *(*free) (void *ptr); // 释放函数
int *(*match) (void *ptr); // 匹配函数
} list;
链表特点
由链表及链节点的定义，可见特性：
- 双向
- 无环（表头的 prev、表尾的 next 都是 null）
- 带表头表尾
- 长度计算 O(1)
- 多态
链表应用场景
作为底层实现的应用场景：
- 列表的键（当键的数量比较多或包含的元素字符串比较长时）
- 发布于订阅
- 慢查询
- 监视器
- 服务器本身使用链表保存多个客户端的状态信息
- 使用链表来构建客户端输出缓冲区（output buffer）
3. 字典
是数据库的底层实现，是哈希中键的底层实现。
字典由哈希表实现，哈希表中每个节点就存储了字典中的键值对。
哈希表结构定义：
typedef struct dictht {
dictEntry **table; // 表指针指向表数组
unsigned long size; // 表大小，注意：是表中对应几个空间（每个空间是个单链）
unsigned long sizemask; // 掩码，用于计算索引值（==size-1）
unsigned long used; // 表中所有节点个数
} dictht;
哈希表节点结构定义：
typedef struct dictEntry {
void *key; // 键
union { // 联合体，可存一个可变类型的值
void *val; //
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next; // 下一个节点，形成链表
} dictEntry;
字典结构定义：
typedef struct dict {
dictType *type; // 多态，控制字典中不同类型数据操作的一组函数
void *privdata; // 多态，私有数据，保存不同类型特定函数的可选参数
dictht ht[2]; // 2个 hashTable，ht[1]是在 rehash 中使用
int rehashidx; // 没在 rehash 进度中时为 -1；渐进式递增控制 rehash 进度
}
上述 dictType 是一组函数集合，为适配不同类型多态变化，其结构定义：
typedef struct dictType {
unsigned int (*hashFunction) (const void *key); // 计算哈希值的函数
void *(*keyDup) (void *privdata, const void *key); // 复制键的函数
void *(*valDup) (void *privdata, const void *obj); // 比较值的函数
int (*keyCompare) (void *privdata, const void *key1, const void *key2); // 比较键的函数
void (*keyDestructor) (void *privdata, void *key); // 销毁键的函数
void (*valDestructor) (void *privdata, void *obj); // 销毁值的函数
}
哈希算法：MurmurHash2
Redis 使用 MurmurHash2 算法实现哈希计算，优点：即使输入的键是有规律的，算法也能给出一个好的随机分布性，并且计算速度快。
拉链法解决键冲突
Redis 使用链地址法解决键冲突，也叫拉链法，即不同键的相同hash值下使用链表存储。
为考虑速度，总是将新节点插入在链表表头位置，即插入速度O(1)。
rehash 前后
是否需要 rehash 要看负载因子 load_factor = ht[0].used / ht[0].size。过大时扩展，过小时收缩。
rehash 时机的条件：
- 若服务器没进行
BGSAVE或BGREWRITEAOF并且load_factor>=1时，扩展； - 若服务其正在进行
BGSAVE或BGREWRITEAOF并且load_factor>=5时，扩展； - 若
load_factor<0.1，收缩。
Redis 判断是否在执行上述两个操作有不同的策略是为了节省内存，因为多数操作系统采用写时复制技术来优化子进程使用效率，在子进程存在期间，加大 rehash 时负载因子的阈值，尽量避免不必要的内存操作。
rehash 前为 ht[1] 分配内存空间，公式：
- 扩展时，满足
ht[1].size = 2^n，2^n >= ht[0].used * 2，n 取最小满足值 - 收缩时，满足
ht[1].size = 2^n，2^n >= ht[0].used，n 取最小满足值
rehash 的过程就是将键按新的掩码重新计算 hash 将表 ht[0] 迁移到表 ht[1]，其过程为渐进式地，详细看下一节。
rehash 后会释放 ht[0]（指向 null），并将 ht[0] 和 ht[1] 互换，此时 ht[0] 为有数据的哈希表，ht[1]为备用表。
rehash 过程：渐进式
- 字典中维持一个计数器
rehashidx，设置为 0 时表示正式开始 rehash； - rehash 不是一旦开始就持续进行，而是在字典进行 CURD 时顺带每次执行一步。执行时，将
rehashidx索引上的键值对 rehash 到 ht[1] 上，完成后rehashidx++； - 随着 CRUD 的进行，最终 ht[0] 所有节点都被迁移到 ht[1]，此时将
rehashidx设置为-1，表示结束。
渐进式的特点避免了集中式操作带来的大计算量（真机智）；
并且通过上述过程来看，不难知道在 rehash 期间 ht[0] 和 ht[1] 都是在使用的；
并且在执行期间，新添加的键会一律保存到 ht[1] 中，从而保证了 ht[0] 只减不增（又是个机智的地方）。
4. 跳表skiplist
跳表的本质是内部维护了多个指向后续节点的指针，从而达到快速访问节点的目的。
跳表的效率可以和红黑树相媲美，平均复杂度O(logN)，最差O(N)。
跳表使用场景
Redis中有序集合（ZSet）在元素数量较多或元素成员字符串较长时使用跳表作为底层实现，还有在集群节点中用作内部数据结构。
跳表实现
跳表节点结构定义：
typedef struct zskiplistNode {
struct zskiplistNode *backward; // 只向前一个节点（跨度为1）
double score; // 分值
robj *obj; // 成员对象，一个SDS
struct zskiplistLevel {
struct zskiplistNode *forward; // 指向后续节点的指针
unsigned int span; // 跨度，表示距后续指向节点跨越了多少个元素
} level[]; // 层数组
} zskiplistNode;
跳表的节点组合起来挂在跳表上，跳表维持了整个表的一些信息，实现：
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 表头节点和表尾节点
unsigned long length; // 节点数量（表头节点不算在内），O(1)
int level; // 除表头节点外的所有节点中的最大层数
}
由定义可见：
- “跳跃”的性质只能从前往后，从后往前是遍历；
- 返回跳跃表长度复杂度为 O(1)；
一个 ZSet 中，键名是唯一、不重复的，即上方定义的 obj；分数是可以重复的，即 score；ZSet 中首先按 score 由小到大排序，然后按 obj 的字典序排序。
注意：表头节点特殊，数据结构中只使用了它的层的数据，其他字段没用，层数总为最大层数（MaxLevel）32。同时，表头节点占用了0号下标，也方便从1开始计数。
每创建一个节点，节点的 level 长度会根据幂次定律随机生成一个介于1~32之间的值作为大小。这个大小也被称为“高度”。
跨度是用来计算排名的，在查到某个元素后，计算历史的跨度和就是此元素的排名。
跳表数据的增删改查
参考：知乎上的一篇文章 Skiplist，这里只简单提一下关键点。
查询操作会从 level 的高层开始查，如果发现下一个跳转点的值大于目标值，则降层继续查。
增加和删除需要改变前后节点的指针指向以及跨度。其实也很简单，可参考Skip List--跳表，只需改搜索路径中每一个节点的对应 level 及插入或删除节点的 level 就可以了。
另外，增删操作还可能会改变链表的 level 字段。
修改操作略。
5. 整数集合 intset
当集合中只包含整数值并且数量不多时，就时用整数集合作为底层实现。（可用 OBJECT ENCODING xxx 来查看底层实现）
结构定义
typedef struct intset {
uint32_t encoding; // 元素类型
uint32_t length; // 元素数量
int8_t contents[]; // 元素数组，由小到大排列，不重复
} intset;
整数集合中元素的真正类型取决于 encoding 字段，而非定义 contents 时的类型 int8_t，encoding 字段是个枚举类型，值有
INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64，取元素时是按此类型强取对应地址数据的。
contents 中的元素根据升级规则进行类型的自动升级，没有降级。
升级规则
整数集合会按输入数据的大小自动判断类型进行存储，当需要增大类型时，就会出现升级操作——将所有元素的类型都升级为较大的类型。三步：
- 扩容。根据新元素的类型扩展底层数组的容量。
- 元素类型转换。按排序规则（新值参与排序）中从后向前一个个移动到对应的位置（排序不变）。
- 最后更改属性 encoding 和 length。
这样的移动规则完全在数组所占内存空间的内部执行，也是很 tricky 的。
但由于每次升级都会进行类型转换，所以复杂度是固定的O(N)。
由于类型增大，所以新增的数值要么大于原集合中所有元素，要么小于原集合中所有元素（负数），所以升级完后新元素的位置要么在最后，要么在最前。
升级的好处
- 提升灵活性。C语言是静态类型，为避免类型错误
- 节约内存。集合可同时保存三种不同的类型，需要时升级
6. 压缩列表 ziplist
当列表键或哈希键只包含少量且为小整型或者短字符串时，压缩列表是其底层实现。
压缩列表是一种用使用了紧凑的一段内存（连续内存块）组成的一种顺序型数据结构。其节点可以保存一个字节数组或一个整数值。
- zlbytes 记录了整个压缩列表的总字节数
- zltail 标记了最后一个元素（即entryN）对于 zlbytes 的偏移量（字节）
- zllen 记录了节点的数量
- entryX 列表节点，长度不定，是个结构体，参考下方节点的构成
- zlend 标记列表结束，固定的 0xFF
压缩列表节点的构成：
- previous_entry_length 记录了上一个节点占用的字节大小，可以方便从表尾向表头进行遍历。本身位1字节还是5字节可以根据自己的第一个字节判断，当首字节标记为 0xFE 时表示本值为5字节大小，同时也表示前一个节点长度>=254字节
- encoding 保存了数据类型和长度；其值的最高两位映射了类型，其他位表示数据长度（整型中其他位还映射了不同类型，具体自行查阅）
- content 节点的值，其类型和长度都由 encoding 决定
列表也由插入动作，注意不是只有在两端增删。
连锁更新问题
由上我们可以发现。压缩列表这样设计，就是为了把内存使用地很紧凑，其可以通过自身存储的规则实现由前向后遍历和由后向前遍历。
但同时为了保持这种规则，也会带来一些不便。比如插入一个节点后，其后的节点都需要移动。更有特殊的，可能其后的 previous_entry_length 需要由1字节变为5字节（1字节存小于253的数，5字节存了>=254的数），若恰巧因为下一个节点变长了4个字节，下下一个节点的记录（假如原值位253，要变成257，就需要5字节存储）也需要增长4个字节……这样就发生了连锁反应。即所有的数据不仅仅是移动这么简单了，具体每个节点中还需要插入空间进行更新数据。这样操作复杂度最坏是O(N²)。
不仅插入会造成连锁更新，删除操作也会发生连锁更新。
但这种“连锁更新”的问题在实际中并不多见（条件苛刻：如在插入场景下需要正好连续的部分每个节点长度都是 250~253）。其次，被更新的节点数量不多（压缩列表的使用场景是节点数量不多时才用）。所以连锁更新的问题不会影响性能的。
