新西兰地理位置,男士卫衣搭配,弗洛伊德禁地
Redis主要数据结构：简单动态字符串(SDS)、双端链表、字典、跳跃表、整数集合、压缩列表和快速列表；
一、简单动态字符串(SDS)：
Redis没有直接使用C语言中的传统的字节数组保存字符串，而是自行构建了简单动态字符串(SDS)，C字符串只是作为简单动态字符串(SDS)的字面量，用于在无需对字符串值进行修改的地方。
结构：
我要评论struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 表示字符串真正的长度，不包含空终止字符*/
uint8_t alloc; /* 表示字符串的最大容量，不包含Header和最后的空终止字符 */
unsigned char flags; /*表示header的类型*/
char buf[];
};
sds结构一共有五种Header定义，其目的是为了满足不同长度的字符串可以使用不同大小的Header，从而节省内存。
通过使用SDS代替C字符串的优点：
当SDS需要修改时，首先会检查SDS的空间是否满足修改所需的要求，如果不满足会自动进行空间扩容。sds规定：如果扩展后的字符串总长度小于1M则新字符串长度为扩展后的两倍；如果大于1M，则新的总长度为扩展后的总长度加上1M；这样做的目的是减少Redis内存分配的次数，同时尽量节省空间。
//如果程序执行的是增长字符串的操作，比如拼接操作(append)，那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小一一如果忘了这一步就会产生缓冲区溢出。
//如果程序执行的是缩短字符串的操作，比如截断操作(trim)，那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间一一如果忘了这一步就会产生内存泄漏。
//SDS通过未使用空间， SDS实现了空间预分配(同上扩容)和惰性空间释放(同回收sds空余空间的函数)两种优化策略。
C 字符串里面不能包含空字符，否则最先被程序读人的空字符将被误认为是字符串结尾，这些使得C 字符串只能保存文本数据。虽然数据库一般用于保存文本数据，但使用数据库来保存像图片、音频、视频、压缩文件二进制数据的场景也不少见，因此，为了确保Redis 可以适用于各种不同的使用场景， SDS 的API 都是二进制安全的(binary-safe)，所有SDS API 都会以处理二进制的方式来处理SDS 存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。
主要操作：
sds释放函数sdsfree、sds动态调整函数sdsMakeRoomFor、回收sds空余空间的函数sdsRemoveFreeSpace(实际上，就是重新分配一块内存，将原有数据拷贝到新内存上，并释放原有空间，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free 属性将这些字节的数量记录起来，并等待将来使用)、sds连接操作函数sdscatlen。
二、双端链表
因为Redis 使用的C 语言并没有内置这种数据结构，所以Redis 构建了自己的链表实现。
链表在Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表。除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了链表， Redis 服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区( output buffer)。
结构：
Redis为双端链表的每一个节点定义了如下的结构体：
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
与一般的双端链表无异，定义了链表节点的结构体之后，下面就定义链表的结构体，用来方便管理链表节点，其结构体定义如下：
typedef struct list {
listNode *head;//头
listNode *tail;//尾
void *(*dup)(void *ptr);//复制函数
void (*free)(void *ptr);//释放函数
int (*match)(void *ptr, void *key);//节点值对比函数
unsigned long len;//链表长度
} list;
Redis为sdlist定义了一个迭代器结构，其能正序和逆序的访问list结构：
typedef struct listIter {
listNode *next;
int direction;
} listIter;
Redis 的链表实现的特性可以总结如下：
三、字典
字典是一种用于保存键值对(key-value pair)的抽象数据结构。在字典中，一个键(key)可以和一个值(value)进行关联（或者说将键映射为值），这些关联的键和值就称为键值对。因此Redis 构建了自己的字典实现。
Redis 的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时， Redis 就会使用字典作为哈希键的底层实现。
结构：
typedef struct dict {
dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2]; // 哈希表
long rehashidx; //rehash 索引,当 rehash 不在进行时，值为 -1
unsigned long iterators; // 目前正在运行的安全迭代器的数量
} dict;
type 属性和privdata 属性是针对不同类型的键值对，为创建多态字典而设置的：
type 属性是一个指向dietType 结构的指针，每个dietType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
而privdata 属性则保存了需要传给那些类型特定函数的可选参数。
typedef struct dictType {
uint64_t (*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;
ht 属性是一个包含两个项的数组，数组中的每个项都是一个dictht 哈希表，一般情况下，字典只使用ht[0]哈希表， ht[l]哈希表只会在对ht[0]哈希表进行rehash 时使用。除了ht[1]之外，另一个和rehash 有关的属性就是rehashidx ，它记录了rehash 目前的进度，如果目前没有在进行rehash ，那么它的值为-1。图4-3 展示了一个普通状态下（没有进行rehash)的字典。
typedef struct dictht {
dictEntry **table;// 哈希表数组
unsigned long size; // 哈希表大小
unsigned long sizemask; // 哈希表大小掩蜀，用于计算索引值, 总是等于size-1
unsigned long used; // 该哈希表已有节点的数量
} dictht;
table 属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry 结构的指针，每个dictEntry 结构保存着一个键值对。
typedef struct dictEntry {
void *key; // 键
union {// 值
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 指向下个哈希表节点，形成链表
} dictEntry;
key 属性保存着键值对中的键，而v 属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t 整数，又或者是一个int64_t 整数。
next 属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突(collision)的问题。
（与HashMap一样的hash方法）
主要操作：
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。Redis 计算哈希值和索引值的方法如下：
当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突(collision)。redis的哈希表使用链地址法(separate chaining)来解决键冲突，每个哈希表节点都有一个next 指针，多个哈希表节点可以用next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。
随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子(load factor)维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：
其中哈希表的负载因子可以通过公式：
＃负载因子＝哈希表巳保存节点数量/哈希表大小load factor= ht[0].used / ht[0].size
扩展或收缩哈希表需要将ht[0]里面的所有键值对rehash到ht[l]里面，但是，这个rehash 动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。这样做的原因在于为了避免rehash对服务器性能造成影响。以下是哈希表渐进式rehash 的详细步骤：
渐进式rehash 的好处在于它采取分而治之的方式，将rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash 而带来的庞大计算量。
字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行。新添加到字典的键值对一律会被保存到ht[l]里面，而ht[0]则不再进行任何添加操作。
四、跳跃表
跳跃表(skiplist)是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表支持平均O(logN)、最坏O(N)（的复杂度的节点查找，还可以通过顺序性操作来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。
Redis 使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员(member)是比较长的字符串时， Redis 就会使用跳跃表作为有序集合键的底层实现。
Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。
结构：
跳跃表数据结构 跳跃表的结构体定义在server.h文件中。其中包括跳跃表节点zskiplistNode和跳跃表zskiplist两个结构体。
typedef struct zskiplistNode {
sds ele; // 成员对象
double score; // 分值
struct zskiplistNode *backward; // 后向指针
struct zskiplistLevel {// 层
struct zskiplistNode *forward; // 前向指针
unsigned int span; // 跨度
} level[];
} zskiplistNode;
层(level)：节点中用Ll 、L2 、L3 等字样标记节点的各个层， Ll 代表第一层， L2代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。跳跃表节点的level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。
每次创建一个新跳跃表节点的时候，程序都根据事次定律(power law，越大的数出现的概率越小）随机生成一个介于1 和32 之间的值作为level 数组的大小，这个大小就是层的“高度”。
跨度：层的跨度(level [i] . span 属性）用于记录两个节点之间的距离：
两个节点之间的跨度越大，它们相距得就越远。指向NULL 的所有前进指针的跨度都为0 ，因为它们没有连向任何节点。
遍历操作只使用前进指针就可以完成了，跨度实际上是用来计算排位(rank)的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
多个跳跃表节点就可以组成一个跳跃表：
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 跳跃表的表头节点和表尾节点
unsigned long length; // 表中节点的数量
int level; // 表中层数最大的节点层数
} zskiplist;
通过使用length 属性来记录节点的数量，程序可以在0(1)复杂度内返回跳跃表的长度。level 属性则用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的层数量。
跳跃表基本操作 Redis中关于跳跃表的相关操作函数定义在t_zset.c文件中：
跳跃表操作：
创建一个跳跃表
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
// 申请内存
zsl = zmalloc(sizeof(*zsl));
// 初始化跳跃表属性
zsl->level = 1;
zsl->length = 0;
// 创建一个层数为32，分值为0，成员对象为NULL的表头结点
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
// 设定每层的forward指针指向NULL
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
// 设定backward指向NULL
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}
创建一个跳跃表节点：
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
// 申请内存
zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
// 设定分值
zn->score = score;
// 设定成员对象
zn->ele = ele;
return zn;
}
插入节点：
往跳跃表中插入一个节点，必然会改变跳表的长度，可能会改变其长度。而且对于插入位置处的前后节点的backward和forward指针均要改变。 插入节点的关键在找到在何处插入该节点，跳跃表是按照score分值进行排序的，其查找步骤大致是：从当前最高的level开始，向前查找，如果当前节点的score小于插入节点的score，继续向前；反之，则降低一层继续查找，直到第一层为止。此时，插入点就位于找到的节点之后。
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
// updata[]数组记录每一层位于插入节点的前一个节点
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
// rank[]记录每一层位于插入节点的前一个节点的排名
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
x = zsl->header;
// 从最高层开始查找
for (i = zsl->level-1; i >= 0; i--) {
// 存储rank值是为了交叉快速地到达插入位置
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
// 前向指针不为空，前置指针的分值小于score或当前向指针的分值等于空但成员对象不等于0的情况下，继续向前查找
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
// 存储当前层上位于插入节点的前一个节点
update[i] = x;
}
// 此处假设插入节点的成员对象不存在于当前跳跃表内，即不存在重复的节点
// 随机生成一个level值
level = zslRandomLevel();
if (level > zsl->level) {
// 如果level大于当前存储的最大level值
// 设定rank数组中大于原level层以上的值为0
// 同时设定update数组大于原level层以上的数据
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
// 更新level值
zsl->level = level;
}
// 创建插入节点
x = zslCreateNode(level,score,ele);
for (i = 0; i < level; i++) {
// 针对跳跃表的每一层，改变其forward指针的指向
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
// 更新插入节点的span值
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
// 更新高层的span值
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
// 设定插入节点的backward指针
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
跳跃表删除：
Redis提供了三种跳跃表节点删除操作。分别如下：
根据给定分值和成员来删除节点，由zslDelete函数实现；
根据给定分值来删除节点，由zslDeleteByScore函数实现；
根据给定排名来删除节点，由zslDeleteByRank函数实现
上述三种操作的删除节点部分都由zslDeleteNode函数完成。zslDeleteNode函数用于删除某个节点，需要给定当前节点和每一层下当前节点的前一个节点。
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = 0; i < zsl->level; i++) {
if (update[i]->level[i].forward == x) {
// 如果x存在于该层，则需要修改前一个节点的前向指针
update[i]->level[i].span += x->level[i].span - 1;
update[i]->level[i].forward = x->level[i].forward;
} else {
// 反之，则只需要将span-1
update[i]->level[i].span -= 1;
}
}
// 修改backward指针，需要考虑x是否为尾节点
if (x->level[0].forward) {
x->level[0].forward->backward = x->backward;
} else {
zsl->tail = x->backward;
}
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--;
}
获取给定分值和成员的节点的排名：
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x;
unsigned long rank = 0;
int i;
x = zsl->header;
// 从最高层开始查询
for (i = zsl->level-1; i >= 0; i--) {
// 前向指针不为空，前置指针的分值小于score或当前向指针的分值等于空但成员对象不等于o的情况下，继续向前查找
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) <= 0))) {
rank += x->level[i].span;
x = x->level[i].forward;
}
// 此时x可能是header，所以此处需要判断一下
if (x->ele && sdscmp(x->ele,ele) == 0) {
return rank;
}
}
return 0;
}
区间操作：
Redis提供了一些区间操作，用于获取某段区间上的节点或者删除某段区间上的所有节点等操作，这些操作大大提高了Redis的易用性：
五、整数集合
整数集合(intset)是Redis 用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t 、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。
结构：
每个intset.h/intset 结构表示一个整数集合：
typedef struct intset {
uint32_t encoding; // 编码方式
uint32_t length; // 集合包含的元素数量
int8_t contents[];// 保存元素的数组
} intset;
操作：
每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级(upgrade)，然后才能将新元素添加到整数集合里面。整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约空间
升级整数集合并添加新元素共分为三步进行：
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
// 获取当前编码格式
uint8_t curenc = intrev32ifbe(is->encoding);
// 获取需要升级到的编码格式
uint8_t newenc = _intsetValueEncoding(value);
// 获取原整数集中的整数个数
int length = intrev32ifbe(is->length);
// 由于待添加的元素一定是大于或者小于整数集中所有元素，故此处需要判断添加到新数据集的头部或者尾部
// 如果value为正，则添加到新数据集的尾部；反之则添加到首部
int prepend = value < 0 ? 1 : 0;
// 设定新的编码格式
is->encoding = intrev32ifbe(newenc);
// 对原数据集进行扩容
is = intsetResize(is,intrev32ifbe(is->length)+1);
// 采用从后往前的重编码顺序，这样就避免覆盖数据了。
while(length--)
// 将原数据集中的数据依次赋值到新数据集中
// _intsetGetEncoded(is,length,curenc)获取数据集is的第length位上的数据，curenc为原数据集的编码格式
// _intsetSet将数据集is的第length+prepend位上设定为上一函数返回的值
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
// 将待添加的数据添加到首部或者尾部
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
// 修改新数据集的长度
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
六、压缩列表
当一个列表键只包含少量的列表项，并且每个列表项要么就是小整数型或者是长度较短的字符串。常用来作为列表建和哈希键的底层实现。为了节约内存而开发。
zlbytes：4字节，记录整个压缩列表占用内存的字节数
zltail：4字节，记录压缩列表尾部节点距离起始地址的偏移量
zllen：2字节，记录压缩列表包含的节点数量
entry：不定，列表中的每个节点
zlend：1字节，特殊值0xFF，标记压缩列表的结束。
七、快速列表（quicklist）
quicklist结构意思为一个由ziplist组成的双向链表，链表中的每一个节点都以压缩列表ziplist的结构保存着数据，而ziplist有多个entry节点，保存着数据。相当与一个quicklist节点保存的是一片数据，而不再是一个数据。
结构：
quicklist表头结构：
typedef struct quicklist {
//指向头部(最左边)quicklist节点的指针
quicklistNode *head;
//指向尾部(最右边)quicklist节点的指针
quicklistNode *tail;
//ziplist中的entry节点计数器
unsigned long count;
//quicklist的quicklistNode节点计数器
unsigned int len;
//保存ziplist的大小，配置文件设定，占16bits
int fill : 16;
//保存压缩程度值，配置文件设定，占16bits，0表示不压缩
unsigned int compress : 16;
} quicklist;
quicklist节点结构：
typedef struct quicklistNode {
struct quicklistNode *prev; //前驱节点指针
struct quicklistNode *next; //后继节点指针
//不设置压缩数据参数recompress时指向一个ziplist结构
//设置压缩数据参数recompress指向quicklistLZF结构
unsigned char *zl;
unsigned int sz; //压缩列表ziplist的总长度
unsigned int count : 16; //ziplist中包的节点数，占16 bits长度
//表示是否采用了LZF压缩算法压缩quicklist节点，1表示压缩过，2表示没压缩，占2 bits长度
unsigned int encoding : 2;
//表示一个quicklistNode节点是否采用ziplist结构保存数据，2表示压缩了，1表示没压缩，默认是2，占2bits长度
unsigned int container : 2;
//标记quicklist节点的ziplist之前是否被解压缩过，占1bit长度
//如果recompress为1，则等待被再次压缩
unsigned int recompress : 1;
unsigned int attempted_compress : 1; /* 节点太小无法压缩//测试时使用 */
unsigned int extra : 10; //额外扩展位，占10bits长度
} quicklistNode;
压缩过的ziplist结构—quicklistLZF：
typedef struct quicklistLZF {
//表示被LZF算法压缩后的ziplist的大小
unsigned int sz; /* LZF size in bytes*/
//保存压缩后的ziplist的数组，柔性数组
char compressed[];
} quicklistLZF;
管理ziplist信息的结构quicklistEntry：
typedef struct quicklistEntry {
const quicklist *quicklist; //指向所属的quicklist的指针
quicklistNode *node; //指向所属的quicklistNode节点的指针
unsigned char *zi; //指向当前ziplist结构的指针
unsigned char *value; //指向当前ziplist结构的字符串vlaue成员
long long longval; //指向当前ziplist结构的整数value成员
unsigned int sz; //保存当前ziplist结构的字节数大小
int offset; //保存相对ziplist的偏移量
} quicklistEntry;
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
理解Redis持久化，RDB持久化和AOF持久化的不同处理方式
Redis 两类持久化方式，快照和全量追加日志的不同处理方式
网友评论