一、SDS
Redis自己构建了一种名为简单动态字符串（simple dynamic string, SDS）的抽象类型，将SDS用作Redis的默认字符串表示。而没有直接使用C语言传统的字符串表示。
每个sds.h/shshdr结构表示一个SDS值：
struct sdshdr{
// 记录buf数组中已使用字节的数量
// 等于SDS所保存字符串的长度
int len;
// 记录buf数组中未使用字节的数量
int free;
// 字节数组
char buf[];
};
要点：
- Redis 只会使用C字符串作为字面量，在大多数情况下，Redis使用SDS作为字符串表示。
- 比起C字符串，SDS具有以下优点：
- 常数复杂度获取字符串长度。
- 杜绝缓冲区溢出。
- 减少修改字符串长度时所需的内存重分配次数。
- 二进制安全：不以空字符作为字符串结尾。
- 兼容部分C字符串函数。
二、链表
链表节点：adlist.h/listNode
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
链表：adlist.h/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;
要点：
- 链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。
- 每一个链表节点有一个listNode结构表示，每一个节点都有一个指向前置节点和后直接点的指针，所以Redis的链表实现时双端链表。
- 每一个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息。
- 因为链表表头节点和前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表。
- 通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值。
三、字典
哈希表：dict.h/dictht
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
哈希表节点：
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t 64;
} v;
// 指向下个哈希表节点，形成链表, 以此解决冲突
struct dictEntry *next;
} dictEntry;
字典：dict.h/dict
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引
// 当rehash不在进行时，值为-1
int trehashidx; // rehashing not in progress if rehashidx == -1
}
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);
}dictType;
要点：
- 字典被广泛用于实现redis的各项功能，其中包括数据库和哈希键。
- Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用。
- 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算哈希键的哈希值（优点：即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快）。
- 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值会连成一个单项链表（速度考虑，采用头插法）。
- 在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成，而是渐进式的完成的（每次更新更新新哈希表，删除旧哈希表节点，插入只插入新哈希表，保证ht[0]包含的键值对数量只减不增，最终为空表）。
四、跳跃表
跳跃表节点：redis.h/zskiplistNode
trypedef struct zskiplistNode {
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forword;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
zskiplist 结构定义：
typedef strut zskiplist {
// 表头节点和表尾节点
structz skiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
要点：
- 跳跃表是有序集合的底层实现之一。
- Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNde则用于表示跳跃表节点。
- 每个跳跃表节点的层高都是1至32之间的随机数。
- 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
- 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
六、整数集合
整数集合：intset.h/intset
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
要点：
- 整数集合是集合键的底层实现之一。
- 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
- 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
- 整数集合只支持升级操作，不支持降级操作。
七、压缩列表
| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
|---|
要点：
- 压缩列表是一种为节约内存而开发的顺序型数据结构。
- 压缩列表被用作列表键和哈希键的底层实现之一。
- 压缩列表可以包含多个节点，每一个节点可以保存一个字节数组或者整数值。
- 添加新节点到压缩列表，或者从压缩列表删除节点，可能会引发连锁更新操作，但这种操作出现的机率并不高。
