redis 数据结构之整数集合与压缩列表实现原理

一时失言乱红尘 2021-12-16 04:47 247阅读 0赞

**整数集合**

当集合中只有整数，且数目不多时，redis会使用整数集合intset作为集合的实现。

整数集合可保存16位 32位以及64位整数，且去重。

typedef struct intset \{  
    //编码方式  
    uint32\_t encoding;  
    //元素数目  
    uint32\_t length;  
    //保存元素的数组  
    int8\_t contents\[\];  
\} intset;

contents中各个元素从小到大有序排列，并且不包含重复项

contents 数组中真正的类型取决于  encoding属性的值

当整数集合中添加一个新元素且  新元素类型在encoding编码下已经存放不下  需要进行升级：

1 重新分配空间

2 迁移

3 添加新元素

需要对每个元素进行类型转换   时间复杂度O（N）

好处：

1 提升灵活性   不用考虑整数集合类型  直接添加即可，服务端进行类型转换，避免类型不符合错误

2 尽可能节约内存空间，只有在有需要的时候才进行升级。

降级：

整数集合只支持升级操作，不支持降级。

**压缩列表**

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数，要么就是长度比较短的字符串，redis就会使用压缩列表来做列表键的底层实现

当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。

压缩列表是Redis为了节约内存而开发的是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值

ziplist 数据结构

![960295-20180105111959721-165447256.png][]

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值，其中字节数组可以是以下三种长度的其中一种

长度小于等于63字节的字节数组

长度小于等于16383字节的字节数组

长度小于等于4294967295字节的字节数组

数值则可以是以下六种长度的其中一种

1:  4位长介于0至12之间的无符号整数

2：1字节长的有符号整数

3: 3字节长的有符号整数

4：int16类型整数

5：int32类型整数

6 : int64类型整数

压缩列表的数据结构

![20190705093840522.png][]

previous\_entry\_length 属性以字节为单位,记录了压缩列表中前一个节点的长度,previous\_entry\_length属性的长度可以是1字节或者5字节

如果前一节点的长度小于254字节那么previous\_entry\_length属性的长度为1字节 如果前一节点的长度大于等于254字节previous\_entry\_length属性的长度为5字节

根据当前节点的地址和previous\_entry\_length的值来计算出前一个节点的地址

压缩列表的从表尾向表头遍历操作就是使用这一原理实现的，只要我们拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的previous\_entry\_length属性

程序就可以一直向前一个节点回溯，最终到达压缩列表的表头节点。

节点encoding属性记录了节点的content属性所保存数据的类型以及长度

一字节、两字节或者五字节长，值的最高位为00 、01、或者10的是字节数组编码这种编码表示节点的content属性保存着字节数组，数组的长度有编码除去最高两位之后的其他位记录

一字节长 值的最高位以11开头的是整数编码，这种编码表示节点的content属性保存着整数值，整数值的类型和长度有编码除去最高两位之后的其他位记录

节点的content属性负责保存节点的值，节点值可以是一个字节数组或者整数值的类型和长度由encoding决定

**连锁更新**

连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O(n) 连锁更新最坏的时间复杂度O(n\*n)

[960295-20180105111959721-165447256.png]: /images/20211214/e2ccad2e8024400ca263390aec109c2e.png
[20190705093840522.png]: /images/20211214/407cc0d6dd8c4589b5af8211ecc4db4f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，247人围观）

还没有评论，来说两句吧...

相关阅读

相关 Redis数据结构(六) —压缩列表

压缩列表压缩列表是列表键和哈希键的底层实现之一, 当一个列表键只包含少量列表项, 并且每个列表项要么就是小整数值, 要么就是长度比较短的字符串, 那么Redis就会...

女爷i/ 2024年04月18日 08:05/ 0 赞/ 26 阅读

相关 Redis数据结构之整数集合

一：整数集合的实现整数集合intset是集合键的底层实现方式之一，当一个集合只包含整数而且数量不是很多的时候，Redis就会整合集合作为集合键的底层实现方式。

水深无声/ 2022年11月06日 12:54/ 0 赞/ 155 阅读

相关 Redis数据结构之压缩列表

一：Redis数据结构之压缩列表压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点(e

系统管理员/ 2022年10月23日 06:59/ 0 赞/ 157 阅读

相关 redis数据结构实现--压缩列表(ziplist)

压缩列表（ziplist）是链表键和哈希键的底层实现之一。当链表键或哈希键只有少量列表项，且列表项中是小整数值或短字符串，则会采用压缩列表作为底层实现。 ----------

忘是亡心i/ 2022年04月15日 05:54/ 0 赞/ 228 阅读

相关 redis——数据结构（整数集合，压缩列表）

4、整数集合整数集合（intset）是 Redis 用于保存整数值的集合抽象数据结构，可以保存 `int16_t` 、 `int32_t` 、 `int64_t` 的

偏执的太偏执、/ 2022年02月19日 15:16/ 0 赞/ 213 阅读

相关 Redis数据结构(五) —整数集合

整数集合整数集合(intset)是集合键的底层实现之一, 当一个集合只包含整数值元素, 并且这个集合元素数量不多时, Redis就会使用整数集合作为集合键的底层实现.

我就是我/ 2022年01月30日 11:37/ 0 赞/ 193 阅读

相关 redis 数据结构之整数集合与压缩列表实现原理

整数集合当集合中只有整数，且数目不多时，redis会使用整数集合intset作为集合的实现。整数集合可保存16位 32位以及64位整数，且去重。 typedef st

一时失言乱红尘/ 2021年12月16日 04:47/ 0 赞/ 248 阅读

相关图解Redis数据结构篇之压缩列表

前言[\][Link 1] 同整数集合一样压缩列表也不是基础数据结构，而是 Redis 自己设计的一种数据存储结构。它有点儿类似数组，通过一片连续的内存空间，来存

Love The Way You Lie/ 2021年11月11日 16:04/ 0 赞/ 386 阅读

相关 Redis核心原理与实践--列表实现原理之ziplist

列表类型可以存储一组按插入顺序排序的字符串，它非常灵活，支持在两端插入、弹出数据，可以充当栈和队列的角色。 > LPUSH fruit apple (inte

曾经终败给现在/ 2021年09月25日 15:26/ 0 赞/ 319 阅读

相关 Redis数据结构——整数集合-intset

整数集合整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。 1、整数集合实现：

痛定思痛。/ 2021年09月23日 16:42/ 0 赞/ 395 阅读