当前位置：首页 > news >正文

Redis 中 IntSet 底层数据结构

news 来源：原创 2025/6/9 16:02:20

IntSet 底层数据结构

序言:

像字符串 SDS 只是保存了一个变量的值，但是像 Redis 中也是需要保存一些集合元素的，这里就介绍一下其中一种集合 IntSet，由于是 Set 所以也有 Set 的一些特性，不过也多加了一些特性：
● 唯一
● 长度可变
● 有序
● 可自动升级

数据结构

这里先来看一下 InSet 的底层结构：
在这里插入图片描述
contents数组：用来保存元素的，用的就是 C 语言里面的数组，不过可以观察到这个数组的类型是 int8_t 就说明这个数组能够存的数字很小（-128~127）。难道这个 IntSet 的数据结构就只能存这些数字吗，其实并不是的，它到底存哪些数字主要由 InSet 的 encoding 字段来控制的，它本身算是充当一个数组的起始地址。
length：表示元素的个数。
encoding：编码方式，支持三种编码方式，这三种方式用来表示存储在数组中的数据能够表示多大，且每一个数字读取的方式和占用数组的大小也不一样。
在这里插入图片描述
这里以 16 位来举例：
比如存放一个 16 位能够表示的数字，那么单独放在 8 位的数组中是放不下的，所以在 contents 数组中会以两位来表示一个数字，那么读取的时候也是两位一起读然后转换成一个数字，所以说其实 contents 这个字段充当的是一个数组的起始地址，但是往里面存怎么样的数字和怎么读取都是由 IntSet 来控制的，可以利用多位来表示一个数组。

所以在 IntSet 中读取元素的方式也是有一个计算公式的。

startPtr + (sizeof(encoding) * index)

这个公式的具体含义就是，从数组起始地址开始加上读取元素索引 * 编码大小，就表示要读到的元素的位置。
由于每种编码的方式不同导致在一个数组中可能一个数占用的大小也不相同，所以需要索引 * 编码的大小。
并且如果读到元素之后也需要同样读取编码大小相同个数的位数才能组成想要的值。

由于要确保这个计算公式的准确性，所以 Inset 中要求存在数组中的编码要统一。

接下来举个例子：
存放5、10、20三个元素。

在这里插入图片描述
这里这三个数都在 16 位编码内能够存储，所以采用 16 编码，由于是16位编码，所以这三个元素每个元素都占用数组中的两位，也就是两个字节。

计算一下当前 IntSet 的大小。
● encoding：4 字节
● length：4 字节
● contents：2*3=6 字节
总共是 14 字节。

保存在 IntSet 中的数据也会保持一个有序的状态，为了就是能够使用二分查找法更快的找到元素。

IntSet 自动升级

不过之前说过要求存在 contents 中的数据要求编码必须统一为了方便计算要查找的数据的位置。但是如果有一个数要存到当前数组中，但是它的数对应的编码大于当前编码会怎么办。

这里就涉及到了 IntSet 的升级，会自动把数组中的所有数对应的编码升级。

举例：
例如现在还是存 5，10，20这三个数，对应的编码也是 16 位的。
在这里插入图片描述
此时如果向数组中添加一个 50000 超过 16 编码，需要使用 32 位编码，这时候 IntSet 会自动升级，会按照新的编码和元素个数进行数组的扩容。

这时每个元素都需要占用 4 个字节，确保编码的一致性，所以数组需要占用的内存就是（3+1） * 4 == 16 字节

在这里插入图片描述
计算完数组的大小之后，就需要将原先的数组中的数据扩大到相对应的编码大小之后，倒序的拷贝到扩容后的数组中。

这里为什么需要倒叙呢？
因为如果正序的话，假设这里是5先转移，那么 5 原先占用 2 个字节，然后扩容到四个字节然后在进行拷贝，在扩容到 4 个字节的时候就会把后面 10 这个数字给覆盖掉了，就导致数据的丢失，但是如果是倒叙，从 20 开始的话，20后面没有数字可以放行的扩容然后转移。所以需要倒倒序。

当转移完成之后：
在这里插入图片描述
这时候就可以把新要插入的数据放入到数组的尾部。

最后要修改头信息中的 encoding 和 length。

IntSet 底层数据结构

序言:

数据结构

IntSet 自动升级

相关文章：