凌云的博客

行胜于言

Redis 5 数据结构(五)intset

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


概述

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

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

intset 的实现

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

intset 结构的定义如下:

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
  • encoding 表示 contents 的编码方式,有如下编码方式 c #define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t)) * length 表示集合中的元素个数。 下图是一个拥有一个 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 API c intset *intsetNew(void);

创建一个 intset。

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

添加数据到 intset 中。 * success 为 1 表示添加成功 * success 为 0 表示 intset 中已有此数字

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

删除 intset 中数值为 value 的数字 * success 为 1 表示删除成功 * success 为 0 表示 intset 中没有此数字

uint8_t intsetFind(intset *is, int64_t value);

判断 intset 中是否有此数字 * 返回 1 表示存在此数字 * 返回 0 表示不存在此数字

int64_t intsetRandom(intset *is);

随机返回 intset 中的一个数字

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

获取 intset 中特定索引的数字 * 返回 1 表示获取成功,数字保存在 value 中 * 返回 0 表示索引无效

uint32_t intsetLen(const intset *is);

返回 intset 元素的个数。

size_t intsetBlobLen(intset *is);

返回 intset 占用的总字节数。

总结

  • intset 中的数字总是有序的,因此在进行数字查找时可以使用二分法
  • intset 有多种编码方式,添加数字的时候会使用能满足条件的最小编码
  • intset 的插入和删除都需要对整个 intset 的内存进行 realloc,因此 intset 不适合保存大量的数字
  • intset 会在需要的时候进行编码升级,但不会进行编码降低(这可以避免频繁的编码转换)