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

偏执的太偏执、 2022-02-19 15:16 213阅读 0赞

# 4、整数集合 #

整数集合（intset）是 Redis 用于保存整数值的集合抽象数据结构， 可以保存 `int16_t` 、 `int32_t` 、 `int64_t` 的整数值， 并且保证集合中不会出现重复元素。

实现较为简单：

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

各个项在数组中从小到大有序地排列， 并且数组中不包含任何重复项。

虽然 `intset` 结构将 `contents` 属性声明为 `int8_t` 类型的数组， 但实际上 `contents` 数组并不保存任何 `int8_t` 类型的值 —— `contents` 数组的真正类型取决于 `encoding` 属性的值：

如果 `encoding` 属性的值为 `INTSET_ENC_INT16` ， 那么 `contents` 就是一个 `int16_t` 类型的数组， 数组里的每个项都是一个 `int16_t` 类型的整数值 （最小值为 `-32,768` ，最大值为 `32,767` ）。

如果 `encoding` 属性的值为 `INTSET_ENC_INT32` ， 那么 `contents` 就是一个 `int32_t` 类型的数组， 数组里的每个项都是一个 `int32_t` 类型的整数值 （最小值为 `-2,147,483,648` ，最大值为 `2,147,483,647` ）。

如果 `encoding` 属性的值为 `INTSET_ENC_INT64` ， 那么 `contents` 就是一个 `int64_t` 类型的数组， 数组里的每个项都是一个 `int64_t` 类型的整数值 （最小值为 `-9,223,372,036,854,775,808` ，最大值为 `9,223,372,036,854,775,807` ）。

### 升级 ###

c语言是静态类型语言，不允许不同类型保存在一个数组。这样第一，灵活性较差，第二，有时会用掉不必要的内存

比如用long long储存1

为了提高整数集合的灵活性和节约内存，我们引入升级策略。

当我们要将一个新元素添加到集合里， 并且新元素类型比集合现有元素的类型都要长时， 集合需要先进行升级。

分为三步进行：

1.  根据新元素的类型， 扩展整数集合底层数组的空间大小， 并为新元素分配空间。
2.  将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上
3.  将新元素添加到底层数组里面。

因为每次添加新元素都可能会引起升级， 每次升级都要对已有元素类型转换， 所以添加新元素的时间复杂度为 O(N) 。

因为引发升级的新元素比原数据都长，所以要么他是最大的，要么他是最小的。我们把它放在开头或结尾即可。

### 降级 ###

略略略，不管你们信不信，整数集合不支持降级操作。。我也不知道为啥

# 5、压缩列表 #

压缩列表是列表键和哈希键的底层实现之一。

当一个列表键只包含少量列表项，并且列表项都是小整数或者短字符串，redis就会用压缩列表做列表键底层实现。

压缩列表是 Redis 为了节约内存而开发的， 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。

一个压缩列表可以包含任意多个节点（entry）， 每个节点可以保存一个字节数组或者一个整数值。

具体实现：

![20190417154409102.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

具体说一下entry：

由三个部分组成：

1、previous\_entry\_length:记录上一个节点的长度，这样我们就可以从最后一路遍历到开头。

2、encoding：记录了content所保存的数据类型和长度。（具体编码不写了，不重要）

3、content：保存节点值，可以是字节数组或整数。（具体怎么压缩的等我搞明白再补）

### 连锁更新 ###

前面说过， 每个节点的 `previous_entry_length` 属性都记录了前一个节点的长度：

*  如果前一节点的长度< `254` KB， 那么 `previous_entry_length` 需要用 `1` 字节长的空间
 *  如果前一节点的长度>=`254` KB， 那么 `previous_entry_length` 需要用 `5` 字节长的空间

现在， 考虑这样一种情况： 在一个压缩列表中， 有多个连续的、长度介于 `250` 字节到 `253` 字节之间的节点 ，这时， 如果我们将一个长度大于等于 `254` 字节的新节点 `new` 设置为压缩列表的表头节点。。。。

然后脑补一下，就会导致连锁扩大每个节点的空间对吧？e(i)因为e(i-1)的扩大而扩大，i+1也是如此，以此类推。。。

删除节点同样会导致连锁更新。

这个事情只是想说明一个问题：插入删除操作的最坏时间复杂度其实是o(n\*n)，因为每更新一个节点都要o(n)。

但是，也不用太过担心，因为这种特殊情况并不多见，这些命令的平均复杂度依旧是o(n)。

[20190417154409102.png]: /images/20220219/3973f145fa2a42efbce91d1bc7846ed1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: /images/20220219/fdaad9e0765845f98012f9d668ac1273.png