2021-07-04 10:27  阅读(197)
文章分类:死磕 Redis 文章标签:死磕 Java死磕 Redis
© 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

intset 是 Redis 实现 Set 的底层实现之一,当集合元素不大于设定值并且元素都是整数时,就会用 intset 作为 Set 的底层数据结构。

它有如下几个特点:

  • 元素类型只能为数字
  • 元素有三种类型:int16_t、int32_t、int64_t
  • 元素有序且不可重复
  • 和 SDS 一样,intset 也是内存连续的,就像数组一样

下面是数据结构的定义:

typedef struct intset {
    // 编码类型 int16_t、int32_t、int64_t
    uint32_t encoding; 
    
    // 长度 最大长度:2^32
    uint32_t length;
    
    // 数组,元素
    int8_t contents[];
} intset;
  • encoding:为 intset 的编码方式,一共有三种类型,分别对应不同的范围:
编码方式 范围
int16_t -32768~32767
int32_t -2147483648~2147483647
int64_t -2^63 ~ 2^63-1

intset的编码由最大的那个数决定,如果有一个数是 int64_t,那么整个 intset 的编码都是 int64_t。在向 intset 中添加元素时,会存在一个元素升级的过程。

  • length:intset 中整数的个数。
  • contents[]:整数数组。intset 中的每个元素都是 contents 数组的一个数组项,各个项在数据中都是按照值从小到大有序的排列且不存在重复项。虽然 contents[] 声明为 int8_t,但 contents 数组并不保存任何 int8_t 类型的值,contents 数组真正的类型由 encoding 决定。

intset 内存是连续的,所有数据的增删改查操作都是在内存地址偏移的基础上进行的,并且整数的保存也是有序的,下图是一个包含有 5 个元素的 intset:

每当我们要将一个新元素添加到 intset 里面时,如果新元素的类型比集合里面所有元素的类型都要长时,那么 intset 需要新进行升级,然后才能将新元素添加到 intset 中。例如有一个 intset 里面的元素都是 int16_t 类型,这时新添加一个元素的类型为 int32_t,那么这个时候需要先将 intset 里面所有的元素全部升级为 int32_t 然后再添加元素。

升级 intset 并添加新元素共分为三个步骤进行:

  1. 根据新元素的类型,扩展 intset 底层数组的空间大小,并为新元素分配空间
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置在正确的位上,而且在放置元素的过程中,需要继续维持底层数据的有序性
  3. 将新元素添加到底层数组里面

以上面的图为例。开始是 int16_t,各元素位置如下:

现在我们增加一个元素 65535,这是一个 int32_t 的元素,所以需要扩展空间大小。一个 int32_t 占用 32 位空间,6 个元素一共占用 192 位空间,所以需要扩展的空间大小为 112,如下图:

已经重新扩展了空间,然后需要将员原来元素放在正确的位上,得到下图:

最后添加新元素:

然后程序将 encoding 属性的值从 INTSET_ENC_INT16 改成 INTSET_ENC_INT32,length 从 5 该为 6 ,如下:

intset 的升级会带来两个好处:

  1. 提升 intset 的灵活性
  2. 尽可能地节约内存

intset 不支持降级操作,一旦进行升级,编码就会一直保持升级后的状态。

关于 intset 的源码就不多做阐述了,有兴趣的小伙伴可以自己查看。

参考

  • 《Redis 设计与实现》
点赞(0)
版权归原创作者所有,任何形式转载请联系作者; Java 技术驿站 >> 【死磕 Redis】----- Redis 数据结构: intset
上一篇
【死磕 Redis】----- Redis 数据结构: skiplist
下一篇
【死磕 Redis】----- Redis 数据结构:对象(RedisObject)