共计 4719 个字符，预计需要花费 12 分钟才能阅读完成。
Redis 数据结构底层总结
数据结构与对象
| 对象 | 解释 |
|---|---|
| 简单动态字符串 | 字符串的底层实现 |
| 链表 | 列表的底层实现 |
| 字典 | 运用在多个方面，包括 Hash 的实现等 |
| 跳跃表 | 有序集合的底层实现 |
| 整数集合 | 集合的底层实现之一 |
| 压缩字典 | 列表键和哈希键的底层实现之一 |
String
/* Redis 简单动态字符串的数据结构 */
struct sdshdr {
// 字符长度，记录 buf 数组中已使用的字节数量
unsigned int len;
// 当前可用空间，记录 buf 数组中未使用的字节数量
unsigned int free;
// 具体存放字符的 buf
char buf[];
};SDS 和 C 字符串的区别
-
常数复杂度获取字符串长度
因为 SDS 纪录了自身字符串中已经使用的长度和未使用的长度，所以可以在 O(1)的时间复杂度内获取到字符串长度，然而 C 字符串不得不通过遍历整个字符串才能获取到长度，其花费的则是 O(N)。
-
杜绝缓冲区溢出
和 C 字符串不同的是，SDS 会利用纪录下来的长度去检查自身是否还有足够的空间去容纳新的需求，如果不满足的话，会先进行扩容，然后才执行新的操作。
-
减少修改字符串时带来的内存重分配次数
C 字符串中每次进行增加和缩短的操作时，都会涉及到内存的重新分配，SDS 利用未使用空间来实现 空间预分配和惰性空间释放 这两种优化策略。
-
空间预分配
用于优化 SDS 的字符串 增长 操作：当要涉及到对 SDS 进行空间扩展的时候，程序不仅仅会为 SDS 分配修改所需要的空间，还会为 SDS 分配额外的未使用空间，好处在于在下次扩容的时候，如果未使用空间还足够使用的话，就使用未使用空间进行扩容。
-
惰性空间
用于优化 SDS 的字符串 缩短 操作：当要缩短 SDS 保存的字符串时，程序并不会立即使用内存重分配来回收缩短后多出来的字节，而是将其回收起来纪录到 free 空间中，以便将来继续使用。
-
-
二进制安全
C 字符串中判断结束的条件是遇见空字符，不同的是，SDS 则选择了通过自身的 len 属性的值来判断字符串是否结束，这样做的目的在于使得 SDS 不仅仅能够存储字符串，还能存储二进制。
-
兼容部分 C 字符串函数
通过遵循 C 字符串以空字符结尾的惯例，SDS 可以在有需要的时候重用 C 语言中的 string 函数库，比如对比函数，追加函数等等，从而实现代码的重用。
链表
链表结点
typedef struct listNode{
// 前置结点
struct listNode *prev;
// 后置结点
struct listNode * next;
// 结点值
void * value;
}链表
typedef struct list{
// 表头节点
listNode * head;
// 表尾节点
listNode * tail;
// 链表长度
unsigned long len;
// 节点值复制函数
void *(*dup) (void *ptr);
// 节点值释放函数
void (*free) (void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
}- dup 函数用于
复制链表结点所保存的值； - free 函数用于
释放链表结点所保存的值； - match 函数用于
对比链表结点所保存的值和另一个输入值是否相等；
- 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是 O（1）。
- 无环：表头节点的 prev 指针和表尾节点的 next 都指向 NULL，对链表的访问时以 NULL 来做判断是否截止。
- 带表头指针和表尾指针：因为链表带有 head 指针和 tail 指针，程序获取链表头结点和尾节点的时间复杂度为 O(1)。
- 带链表长度计数器：链表中存有记录链表长度的属性 len。
- 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用来保存各种不同类型的值。
字典
哈希表结点
typeof struct dictEntry{
// 键
void *key;
// 值
union{
void *val;
uint64_tu64;
int64_ts64;
}
struct dictEntry *next;
}哈希表
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
}字典
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privedata;
// 哈希表
dictht ht[2];
// rehash 索引
int rehashidx;
}哈希算法
解决键冲突
rehash
- 扩展空间：为字典的 ht[1]哈希表分配空间，其空间将会被扩展到第一个大于等于 ht[0].used*2^n 的整数值；
- 数据迁移：将保存在 ht[0]上的所有键值对迁移到 ht[1]中；
- 交换：迁移完后，释放掉 ht[0]，将现在的 ht[1]设置为 ht[0]，并且为 ht[1]新创建一个空白哈希表，实现了相互交换的过程；
渐进式 rehash
跳跃表
跳跃表结点
typedef struct zskiplistNode{
// 层
struct zskiplistLevel{
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
}- 层：level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。
- 前进指针：用于指向表尾方向的前进指针
- 跨度：用于记录两个节点之间的距离
- 后退指针：用于从表尾向表头方向访问节点
- 分值和成员：跳跃表中的所有节点都按分值从小到大排序。成员对象指向一个字符串，这个字符串对象保存着一个 SDS 值
跳跃表
typedef struct zskiplist {
// 表头节点和表尾节点
structz skiplistNode *header,*tail;
// 表中节点数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
}zskiplist;整数集合
typedef struct intset{
// 编码方式
uint32_t enconding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
}- 扩展空间：根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
- 转换编码：将底层数组现有的所有元素都转换成新的编码格式，重新分配空间
- 添加：将新元素加入到底层数组中
压缩列表
本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-09/146889.htm
