字节青训营后端打卡笔记，主题结构参照文章，以及网络上其它很多的资料所记录下来的笔记。

Redis数据结构一览

SDS(Simple Dynamic String)

C语言字符串的缺陷

获取字符串长度函数strlen()时间复杂度为O(N)
字符串以\0结尾，意味着字符串里的内容不能包括\0字符
字符串不会记录自身缓冲区大小，因此对字符串的操作函数不安全，容易造成缓冲区溢出，有可能导致程序运行终止

SDS结构设计

len，记录了字符串的长度，因此获取字符串长度的时间复杂度为O(1)
alloc，分配给字符数组的空间长度。在修改字符串时，可以通过alloc-len来计算出剩余的空间大小，可以用来判断空间是否满足修改需求。如果不满足，就会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。见下图：

需要注意的是，s_realloc函数在动态扩容时，如果检测到原来内存空间后面一段连续空间长度未能满足要求，仍旧会申请新的内存空间并把原来的数据复制过去。根据chatGPT，这取决于程序对内存空间的分配，是很不确定的，而且大概率是都要新申请空间并复制数据到新的内存空间。
flags，用来表示不同类型的SDS。一共5种，sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，就是2的次方。
buf[]，字符数据，用来保存实际数据。

链表

链表结点结构设计

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;

其中，dup、free、match函数是可以自定义实现的功能函数，暂且不管。只需要关注链表的结构就行。

链表的优势与缺陷

优点

从某个结点获取其前缀与后缀结点的时间复杂度是o(1)的
获取链表的头结点与尾结点的时间复杂度也是O(1)的
获取链表长度的时间复杂度也是O(1)的，因为维护了长度len
每个链表结点使用void*保存指针结点的值，因此可以保存各种不同类型的值

缺点

内存不连续，因此无法快速定位某一个结点
保存值需要一个链表结点结构头的分配，内存开销较大

压缩列表

结构设计

由连续内存块组成的顺序型数据结构，其结构如下：

zlbytes，记录整个压缩列表占用对内存字节数
zltail，记录压缩列表列表尾的偏移量
zllen，记录压缩列表包含的结点数量
zlend，标记压缩列表的结束点，固定值0xFF(十进制255)

结点包含三部分：

prevlen，记录了[前一个结点的长度]
encoding，记录了当前结点实际数据的类型以及长度
data，记录数据

prevlen

prevlen表示前一个结点的长度，以便能够从后向前遍历列表。它的编码规则如下：

如果前一个结点长度小于254，那么就占用一个字节表示前一个结点的长度
如果前一个结点长度大于等于254，那么第一个字节为254，再额外使用4个字节（等价于一个int）表示前一个结点的长度。

encoding

encoing编码代表了当前结点的实际数据的类型以及长度，其编码规则简写如下：

当前结点的数据是整数，使用1字节空间编码
当前结点数据是字符串，根据字符串的长度大小，使用1字节/2字节/5字节的空间进行编码

具体编码规则可以网上搜索。只要记住它代表了当前结点的实际数据的类型以及长度就行了。

连锁更新

压缩列表充分利用了内存进行存储，并通过prevlen和encoding来记录前一个结点的长度以及当前结点实际数据类型以及长度。

基于以上特点，当压缩列表修改某一数据时，如果发生了数据类型的变化，或者数据长度发生了较大变化，很可能需要往后占用额外的内存空间。于是不仅该结点需要更新，其之后的所有结点都需要更新，这就叫“连锁更新”。

例如：

这同时也是压缩列表的缺陷之一。这也意味着压缩列表不适合用于存储较多的数据。

哈希表

Redis中的哈希表就是很常规的哈希表。

当产生哈希冲突时，将同一哈希值的数据用一个链表连起来以避免哈希冲突。其他没有什么结构上的特殊之处了。

rehash

值得一提的是，Redis中使用了双哈希表的模式来支持rehash操作，其结构如下：

在正常服务请求阶段，插入的数据都会写入到[哈希表1]，此时的[哈希表2]并不会被分配空间。

当触发rehash时，有以下三个步骤：

给[哈希表2]分配空间，一般会比[哈希表1]大2倍
将[哈希表1]的数据迁移到[哈希表2]中
迁移完成后，[哈希表1]的空间会被释放，并把[哈希表2]设置为[哈希表1]，然后再[哈希表2]处新创建一个空白的哈希表，为下次rehash做准备

这其中产生的问题，在第二步过程中，如果[哈希表1]的数据量非常大，那么在迁移到[哈希表2]的时候，会涉及到大量的数据拷贝，此时可能会对Redis造成阻塞，于是就有了渐进式rehash

渐进式rehash

在rehash期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis除了执行对应的操作之外，还会将该索引位置上的所有key-value迁移到[哈希表2]上，直到rehash结束，继续之后的步骤。

这里其实不太严谨，根据chatGPT，准确地说，旧表会被标记为“过期”且不会再接受插入的操作。这也就意味着删除、查找以及更新会同时在两张表中进行，如果是查找，按照优先度会先在表2中查找，没找着再在表1中查找。

rehash触发条件

通过负载因子来判断是否需要rehash。

触发rehash的条件主要有两个，我现在还不理解，还需要学习Redis更加深入，这里先挖个坑：

当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。

整数集合

整数集合是Set对象的底层实现之一。整数集合本质上是一块连续内存空间，它的结构定义如下：

typedef struct intset {//编码方式uint32_t encoding;//集合包含的元素数量uint32_t length;//保存元素的数组int8_t contents[];
} intset;

整数集合的升级

当一个元素加入到整数集合中，如果新元素（例如int32_t）比整数集合现有的所有元素（int16_t）都要长时，整数集合需要先进行升级，按新元素的类型扩展contents数组的空间大小，然后才能将新元素加入到整数集合里。其流程见下图：

升级的好处

提升灵活性。通过自动升级底层数组来适应元素，可以将任意类型的整数添加进集合中，而不必担心出现内存错误
节约内存。只会在有需要的时候升级，因此能够尽量节约存储空间。例如，当元素全是int16_t时，不会升级数据使用int64_t存储，只有当存在int64_t的数据时，才会对数组进行升级。

跳表

跳表(SkipList)是一个有序的链表，操作效率可以达到O(logN)。

跳表的特点

多层链表结构
每一层都是有序链表，并且按照元素升序(默认)排列。
元素出现在哪一层是随机决定的，采用的是随机从0层开始，有p的概率加一层的方法（比如添加在第二层的概率是 p^2*(1-p) ），在原论文中给出的p是0.25，意味着期望层数是\frac{1}{1-p}=1.33。chatGPT表示一般p设置为0.5，期望层数为2。
只要元素出现在了第k层，那么k层以下的链表也会出现这个元素。
底层包含所有元素。
头尾结点不存储元素，且头尾结点的层数就是跳表的最大层数，如果元素随机到的层数超过最大层数，则扩展最大层数再添加该元素。
跳表中的结点包含两个指针，一个指针指向同层链表的后一个结点，另一个指向下层链表的同元素结点。

网络上传播较广的跳表结点结构如下：

typedef struct zskiplistNode {//Zset 对象的元素值sds ele;//元素权重值double score;//后向指针struct zskiplistNode *backward;//节点的level数组，保存每层上的前向指针和跨度struct zskiplistLevel {struct zskiplistNode *forward;unsigned long span;} level[];
} zskiplistNode;

这个结构和跳表最后一个特点有点不一样，它没有指向下层链表的同元素结点，作为替代，用一个数组实现了同元素的不同层，同时用span代替level，表示该元素在该层上往后最远能跨多少个元素。