Redis 5 数据结构（五）intset

分类：Redis| 发布时间：2019-05-06 22:25:00

本文是 Redis 5 数据结构系列的第五篇，主要讲解 intset 的结构和实现细节。

Redis 主要使用 intset 保存纯数字的集合。

intset 的源码在 src/intset.h 和 src/intset.c。

intset 结构的定义如下：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

下图是一个拥有一个 6 个元素的 intset，其 encoding 为 INTSET_ENC_INT16

可以看到 intset 里面的数字是有序的，实际上在使用 intset 的 API 增加数字的时候，接口的实现总是在合适的位置插入数据，从而保证 intset 的数字总是有序的。

在插入数据的时候（先不考虑编码升级的情况），会先判断 intset 中是否已有此数字，如果已经存在此数字则不会进行任何操作。否则会先用 zrealloc 扩展申请的内存块，然后使用 memove 移动内存，最后将数据写入合适的位置以确保插入后的 intset 依然有序。

以上述的 intset 为例，假设我们要插入数字 20,插入后的 intset 如下：

删除 intset 的数据时，会先查找 intset 是否有此数字，若有则先使用 memmove 移动数据，将要删除的数字覆盖掉，然后使用 zrealloc 缩减内存块。

在插入数据的时候，若发现要插入的数据超出了当前编码所能保存的数值范围则需要进行编码升级，还是以第一个图为例，假设现在要插入 32768，由于 32768 超出了 int16_t 的范围，因此需要对 intset 进行编码升级，升级后的 intset 如下：

可以看出为了容纳 32768 这个数字，intset 进行了编码升级，现在其 encoding 由 INTSET_ENC_INT16 升级为了 INTSET_ENC_INT32。 intset 中的每个数字所占用的空间由两字节变成了四字节。

以升级后的 intset 为例，假设我们现在删除了 32768，剩下的数字都可以使用 int16_t 来表示了，那么 intset 是否会进行编码降级呢？答案是不会。

intset *intsetNew(void);

创建一个 intset。

intset *intsetAdd(intset *is, int64_t value, uint8_t *success);

添加数据到 intset 中。

intset *intsetRemove(intset *is, int64_t value, int *success);

删除 intset 中数值为 value 的数字

uint8_t intsetFind(intset *is, int64_t value);

判断 intset 中是否有此数字

int64_t intsetRandom(intset *is);

随机返回 intset 中的一个数字

uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);

获取 intset 中特定索引的数字

uint32_t intsetLen(const intset *is);

返回 intset 元素的个数。

size_t intsetBlobLen(intset *is);

返回 intset 占用的总字节数。

凌云的博客