Redis数据结构-整数集合

概述

整数集合(intset)是集合键的底层实现之一,当一个集合质保函整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现

redis> SADD numbers 1 3 5 7 9
(integer) 5

redis> OBJECT ENCODING numbers
"intset:

在这个例子中,我们创建了一个只包含5个元素的集合键,并且集合中的所有元素都是整数值,那么这个集合键的底层实现就会是整数集合

整数集合的实现

整数集合是Redis用于保存整数值的集合抽象数据结构,它可以保存类型为int16_t, int32_t或者int64_t的整数值,并且保重集合中不会出现重复元素

typeof struct intset {
    // 编码方式
    unit32_t encoding;

    // 集合包含的元素数量
    unit32_t length;

    // 保存元素的数组
    int8_t contents[];
} intset;

contents数组是整数集合的底层实现,整数集合的每个元素都是contents数组的一个数组项,各个数组项在树脂中按值的大小从小大大有序地排列,并且数组中不包含任何重复项

length属性记录了整数集合包含的元素数量,也即是contents数组的长度.

虽然intset结构将contains属性声明为int8_t类型的数组,但实际上contents数组并不保存任何int8_t类型的值,contents数组的真正类型取决与encoding属性的值

升级

每当我们需要将一个新元素添加到整数集合里面,并且新元素的类型比钟书记和现有的所有元素的类型都要长时,证书集合需要先进行升级,然后才能将新元素添加到整数集合里面

升级整数集合并添加新元素共分为三步进行:

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

升级的好处

证书集合的升级策略有两个好处,一个是提升整数集合的灵活性,另一个是尽可能地节约内存

提升灵活性

因为C语言是静态类型语言,为了避免类型错误,我们通常不会将两种不同类型的值放在同一个数据结构里面.

例如,我们一般只使用int16_t类型的数组来保存int16_t类型的值,只使用int32_t类型的数组来保存int32_t类型的值

但是,因为整数集合可以通过自动升级底层数组来适应新元素,所以我可以随意地将int16_t,int32_t或者int64_t类型的整数添加到集合中,而不必担心出现类型错误

节约内存

当然,要让一个数组可以同时保存int_16t,int32_t,int64_t三种类型的值最简单的做法就是直接使用int64_t类型的数组作为整数集合的底层实现,不过这样一来,机师添加到整数集合里面的都是int16_t或者int32_t类型的值,数组都需要使用int64_t类型的空间去保存它们,从而出现浪费内存的情况

而整数集合现在的做法既可以让集合能同时保存三种不同类型的值,又可以确保升级操作只会在有需要的时候进行,这可以尽量节省内存

降级

没有降级

重点回顾

• 整数集合是集合键的底层实现之一
• 整数集合的底层实现为数组,这个数组以有序,无重复的方式保存集合元素,在有需要时,程序会根据新添加元素的类型,改变这个数组的类型
• 升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存
• 整数集合只支持升级操作,不支持降级操作