数据库 Redis原理-数据结构（总结）

Redis数据结构动态字符串（SDS）介绍SDS结构体定义SDS扩容规则相较于C语言字符串的优点

整数集合（IntSet）介绍结构体定义如下整数集合的升级操作总结

哈希表（Dict）介绍结构体定义Dict的扩容计算新扩容的空间大小rehash的触发条件

压缩列表（ZipList）介绍entry中的encoding编码连锁更新问题总结

快速列表（QuickList）介绍压缩列表（ZipList）中entry的限制QuickList结构体的定义总结

跳表（SkipList）介绍结构体定义如下其他细节

参考

Redis数据结构

动态字符串（SDS）

介绍

Redis中保存的Key是字符串，value往往是字符串或者字符串的集合，字符串是Redis中最常用的一种数据结构。

动态字符串SDS（simple dynamic string）是为了解决C语言字符串存在的问题，以及从节省内存空间的角度出发而设计出来的。

SDS结构体定义

注意：flags代表 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64这5 种类型的len 和 alloc 成员变量的数据类型

比如：

sdshdr16 类型的 len 和 alloc 的数据类型都是 uint16_t，表示字符数组长度和分配空间大小不能超过 2 的 16 次方 sdshdr32 则都是 uint32_t，表示表示字符数组长度和分配空间大小不能超过 2 的 32 次方。

在 struct 声明了 __attribute__ ((packed)) ，它的作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。

例如，一个"hi"的SDS结构如下：

SDS扩容规则

如果所需的 sds 长度小于 1 MB，那么最后的扩容是按照翻倍扩容来执行的，即 2 倍的newlen + ‘\0’如果所需的 sds 长度超过 1 MB，那么最后的扩容长度应该是 newlen + 1MB + ‘\0’

这里加’\0’是为了兼容部分 C 语言标准库的函数

给"hi"的SDS结构追加一段字符串“,Amy”，这里首先会申请新内存空间：

相较于C语言字符串的优点

获取字符串长度时间复杂度O(1)（len成员变量记录了长度，要获取长度直接返回该值即可，不需要变量整个字符串）支持动态扩容（不会发生缓冲区溢出）二进制安全（可以保存任意格式的二进制数据）节省内存空间（设计了5种类型的结构体，灵活保存不同大小的字符串）

整数集合（IntSet）

介绍

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。

具体而言，如果set集合中的元素都是整数且元素个数小于 512 （默认值，set-maxintset-entries配置）个，Redis 会使用整数集合作为 Set 类型的底层数据结构，否则采用哈希表来作为底层数据结构；

为了方便查找，Redis会将intset中所有的整数按照升序依次保存（即，查找set中的元素时可以用二分查找，时间复杂度O(log^n)）

结构体定义如下

其中的encoding包含三种模式，表示存储的整数字节数：

注意：虽然 contents 被声明为 int8_t 类型的数组，但是实际上 contents 数组并不保存任何 int8_t 类型的元素，contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值

整数集合的升级操作

何时进行升级操作？

如果此时set中的数据都比较小，使用2个字节整数就能表示，但如果突然插入一条特别大的数，超过2字节的表示范围了，那么此时就要进行整数集合的升级操作了，也就是将集合的元素编码encoding值升级为更大字节的模式，原来集合中保存的每个元素所占的字节数也要升级为更大的字节，因为所有的元素要统一字节大小，这样才能根据(首地址+元素长度)定位到每个元素。

如何进行升级操作？

假设当前的整数集合中的元素为5、10、20，因为数比较小2个字节16位就能表示，其结构如下：

我们添加一个数字：50000，此时16位(2字节)不能表示，需要升级到32位(4字节)，接下来升级操作的具体流程如下：

首先，进行数组扩容，扩容到刚好装下4个32位(4字节)整数然后，将需要移动的元素从后往前依次移动到对应的位置最后，将新元素插入到数组应该存放的位置

插入后的结构：

此时的5、10、20、50000都占32位(4字节)。

总结

总的来说，整数集合的设计还是基于节省内存资源的角度来考虑的，整数集合的特点如下：

Redis会确保Intset中的元素唯一、有序（插入时通过二分查找到了数据，就直接返回不进行数据的添加，没有查找到对应的数据，则在对应有序的位置插入）具备类型升级机制，可以节省内存空间（对应encoding的三种模式，存储不同的整数类型的大小，遇到超出类型所表示的范围后就进行升级）底层采用二分查找方式来查询（二分查找有序的数组时间复杂度O(log^n)）

哈希表（Dict）

介绍

Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）。

Redis 采用了「链式哈希」来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接起，以便这些数据在表中仍然可以被查询到。

结构体定义

Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

扩容的时候需要进行rehash操作（需要将旧哈希表(dictht)中的数据转移到扩容后更大空间的哈希表中去，也就是从ht[0]迁移到ht[1]中去，这就是为什么需要准备两个哈希表）。

然后采用的是渐进式 rehash，也就是不会一次性将所有的数据都拷贝到新的哈希表中去（因为数据量太大的话迁移操作会花费太多时间，从而阻塞主线程）。

具体而言，根据rehashindx字段（这个字段代表哈希表的下标，-1表示未进行rehash操作，其他值的时候代表将哈希表中对应下标的元素移动到新哈希表中去），在每次进行查询、修改、删除的时候将旧哈希表中的数据一点一点移动到扩容后的哈希表中去，而新增操作的时候是直接插入到新的哈希表（查找数据的时候是往两个哈希表都去查一查的，所以数据在两个表中只保留一份），直至将所有数据迁移到新的哈希表中，最后再将rehashindx字段置为-1，并将ht[0]指向新的哈希表，ht[1]指向null到下次rehash在用。

计算新扩容的空间大小

哈希表的长度为2^n

如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

rehash的触发条件

触发 rehash 操作的条件，主要有两个：

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

负载因子=哈希表已保存节点数量/哈希表的大小

当负载因子小于0.1时，Dict会进行rehash收缩哈希表，节省空间。

压缩列表（ZipList）

介绍

压缩列表（ZipList）是一种特殊的“双端链表” ，它是由连续内存块组成的顺序型数据结构，有点类似于数组。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。其结构图如下：除了数据节点外，还存放了另外四个记录字段：

zlbytes，记录整个压缩列表占用对内存字节数；（4字节）zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；（4字节）zllen，记录压缩列表包含的节点数量；（2字节）zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）（1字节）

数据字段entry的结构又包含三个部分：

previous_entry_length，前一节点的长度，占1个或5个字节。

如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据 encoding，编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节 contents，负责保存节点的数据，可以是字符串或整数

注意：ZipList中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。

entry中的encoding编码

Entry中的encoding编码分为字符串和整数两种：

以“00”、“01”或者“10”开头，则证明content是字符串以“11”开始，则证明content是整数，且encoding固定只占用1个字节

连锁更新问题

压缩列表中的每个entry中的previous_entry_length字段都保存了前一个entry的长度，占1或者5个字节（长度 >= 254就变为5字节），想象一个极端情况下，此时压缩列表中保存的大量entry元素都是250字节，然后此时在列表的最前面插入了一个长度大于254字节的元素，那么此时的第二个元素的previous_entry_length从1字节变为了5字节，增加了4字节，总大小来到了254，那么它后面的字节也要更新previous_entry_length，以此类推…，后面的所有元素都要更新。

总结

压缩列表的可以看做一种连续内存空间的"双向链表"列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低如果列表数据过多，导致链表过长，可能影响查询性能，并且需要分配大空间的连续内存增或删较大数据时有可能发生连续更新问题

快速列表（QuickList）

介绍

ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低，因此只适合少量数据的时候使用。但如果采用双端链表的话，需要保存大量的指针，内存消耗又比较大。

快速列表（QuickList）就是结合了压缩列表和双端列表的优点，将多个压缩链表组合起来一个双端链表，并限制每个压缩链表的大小，解决了ZipList的缺陷。其结构如下：

压缩列表（ZipList）中entry的限制

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。

如果值为正，则代表ZipList的允许的entry个数的最大值；如果值为负，则代表ZipList的最大内存大小，分5种情况：

-1：每个ZipList的内存占用不能超过4kb-2：每个ZipList的内存占用不能超过8kb（默认值）-3：每个ZipList的内存占用不能超过16kb-4：每个ZipList的内存占用不能超过32kb-5：每个ZipList的内存占用不能超过64kb

QuickList结构体的定义

其中，compress字段表示List中间节点元素的压缩状况（因为访问比较频繁的节点就是首部和尾部的节点，所以对中间元素进行压缩更省内存空间）

0：表示不压缩其他正整数：首位节点元素不压缩的个数，比如1代表首位各一个节点不压缩

用一段流程图来描述当前的这个结构:

总结

QuickList的特点：

是一个节点为ZipList的双端链表节点采用ZipList，解决了传统链表的内存占用问题控制了ZipList大小，解决连续内存空间申请效率问题中间节点可以压缩，进一步节省了内存

跳表（SkipList）

介绍

Redis 只有 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。zset 结构体里有两个数据结构：一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表节点可能包含多个指针，指针跨度不同

结构如下：

结构体定义如下

Zset 对象要同时保存「元素」和「元素的权重」，对应到跳表节点结构里就是 sds 类型的 ele 变量和 double 类型的 score 变量。每个跳表节点都有一个后向指针（struct zskiplistNode *backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。

跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。

其他细节

参考：小林coding

参考

https://www.bilibili.com/video/BV1cr4y1671t?p=145&vd_source=f65c06237bac951cf7c31d055dee817b

https://xiaolincoding.com/redis/data_struct/data_struct.html#%E9%94%AE%E5%80%BC%E5%AF%B9%E6%95%B0%E6%8D%AE%E5%BA%93%E6%98%AF%E6%80%8E%E4%B9%88%E5%AE%9E%E7%8E%B0%E7%9A%84

推荐链接

评论可见，请评论后查看内容，谢谢！！！