Redis原理再学习05:数据结构-整数集合intset

2022/3/11 19:14:55

本文主要是介绍Redis原理再学习05:数据结构-整数集合intset,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

intset介绍

intset 整数集合,当一个集合只有整数元素,且元素数量不多时,Redis 就会用整数集合作为集合键的底层实现。

redis> SADD numbers 1 3 5 7 9

(integer 5)

redis> OBJECT ENCODING numbers

(intset)

为什么要用 intset?

集合键的另外一种实现是值为空的散列表(hash table),当元素比较少时,用hash table 存就比较浪费内存,而用

intset 就比较节约内存。

整数集合实现

intset 结构定义:

// https://github.com/redis/redis/blob/3.0/src/intset.h#L35
typedef struct intset {
    uint32_t encoding; // 编码格式, 这个格式有3种,见下面
    uint32_t length; // 集合元素的数量
    int8_t contents[]; // 保存元素的数组
} intset;

// https://github.com/redis/redis/blob/3.0/src/intset.c#L40
/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t)) // 16位2个字节
#define INTSET_ENC_INT32 (sizeof(int32_t)) // 32位4个字节
#define INTSET_ENC_INT64 (sizeof(int64_t)) // 64位8个字节

intset 整数集合结构示意图:

image-20220308222015299

虽然,intset 整数集合里字段 contents 声明是 int8_t 数据类型,但是 contents 存储的数据类型是根据 encoding 属性值来确定的。

  • encoding 值为 INTSET_ENC_INT16 时,contents 就是一个 int16_t 类型的数组,数组里每一项都是 int16_t 类型的整数值。最小值为 -32768,最大值为 32767。
  • 同理,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。

encoding 的值为什么有 3 种呢?

为了节省内存。redis 可以根据存储的元素数值大小,选择合适的类型来存储。

比如添加新元素时,元素整数值超过了当前编码格式能表示的范围,就升级数据类型。

整数集合操作的一些 API

整数集合操作一些 API:

// https://github.com/redis/redis/blob/3.0/src/intset.h#L41
intset *intsetNew(void);  // 创建空集合
intset *intsetAdd(intset *is, int64_t value, uint8_t *success); // 将 value 添加到 is 集合中
intset *intsetRemove(intset *is, int64_t value, int *success); // 将 value 从 is 集合中移除
uint8_t intsetFind(intset *is, int64_t value); // 在结合 is 中搜索 value 元素,成功返回1,失败返回0
int64_t intsetRandom(intset *is); // 随机返回一个元素
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value); // 获取下标为pos的元素值并保持在value中
uint32_t intsetLen(intset *is); // 计算集合中元素个数
size_t intsetBlobLen(intset *is); // 计算集合中元素所占字节总数

获取元素编码格式函数:

_intsetValueEncoding:

// https://github.com/redis/redis/blob/3.0/src/intset.c#L45
/* Return the required encoding for the provided value. */
static uint8_t _intsetValueEncoding(int64_t v) {
    if (v < INT32_MIN || v > INT32_MAX)
        return INTSET_ENC_INT64;
    else if (v < INT16_MIN || v > INT16_MAX)
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;
}

参考

  • 《redis设计与实现》 作者:黄健宏

  • redis.io

  • github redis3.0/intset.h

  • github redis3.0/intset.c



这篇关于Redis原理再学习05:数据结构-整数集合intset的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程