redis 数据结构介绍三 - 第三部分 整数集合

用户头像
Nick
关注
发布于: 2020 年 04 月 29 日

redis中对于 set 其实有两种处理,对于元素均为整型,并且元素数目较少时,使用 intset 作为底层数据结构,否则使用 dict 作为底层数据结构,先看一下代码先

typedef struct intset {
// 编码方式
uint32t encoding;
// 集合包含的元素数量
uint32t length;
// 保存元素的数组
int8t contents[];
} intset;
/ Note that these encodings are ordered, so:
INTSETENCINT16 < INTSETENCINT32 < INTSETENCINT64. */
#define INTSETENCINT16 (sizeof(int16t))
#define INTSETENCINT32 (sizeof(int32t))
#define INTSETENCINT64 (sizeof(int64t))

一眼看,为啥整型还需要编码,然后 int8t 怎么能存下大整形呢,带着这些疑问,我们一步步分析下去,这里的编码其实指的是这个整型集合里存的究竟是多大的整型,16 位,还是 32 位,还是 64 位,结构体下面的宏定义就是表示了 encoding 的可能取值,INTSETENCINT16 表示每个元素用2个字节存储,INTSETENCINT32 表示每个元素用4个字节存储,INTSETENCINT64 表示每个元素用8个字节存储。因此,intset中存储的整数最多只能占用64bit。length 就是正常的表示集合中元素的数量。最奇怪的应该就是这个 contents 了,是个 int8t 的数组,那放毛线数据啊,最小的都有 16 位,这里我在看代码和《redis 设计与实现》的时候也有点懵逼,后来查了下发现这是个比较取巧的用法,这里我用自己的理解表述一下,先看看 8,16,32,64 的关系,一眼看就知道都是 2 的 N 次,并且呈两倍关系,而且 8 位刚好一个字节,所以呢其实这里的contents 不是个常规意义上的 int8_t 类型的数组,而是个柔性数组。看下 wiki 的定义

>Flexible array members[1](https://en.wikipedia.org/wiki/Flexiblearraymember#citenote-1) were introduced in the [C99](https://en.wikipedia.org/wiki/C99) standard of the [C programming language](https://en.wikipedia.org/wiki/C(programminglanguage)) (in particular, in section §6.7.2.1, item 16, page 103).[2](https://en.wikipedia.org/wiki/Flexiblearraymember#citenote-2) It is a member of a struct, which is an array without a given dimension. It must be the last member of such a struct and it must be accompanied by at least one other member, as in the following example:

struct vectord {
size_t len;
double arr[]; // the flexible array member must be last
};

在初始化这个 intset 的时候,这个contents数组是不占用空间的,后面的反正用到了申请,那么这里就有一个问题,给出了三种可能的 encoding 值,他们能随便换吗,显然不行,首先在 intset 中数据的存放是有序的,这个有部分原因是方便二分查找,然后存放数据其实随着数据的大小不同会有一个升级的过程,看下图



![](https://i.loli.net/2020/01/10/qIc6HgP7wfCLipN.png)

新创建的intset只有一个header,总共8个字节。其中encoding = 2, length = 0, 类型都是uint32t,各占 4 字节,添加15, 5两个元素之后,因为它们是比较小的整数,都能使用2个字节表示,所以encoding不变,值还是2,也就是默认的 INTSETENCINT16,当添加32768的时候,它不再能用2个字节来表示了(2个字节能表达的数据范围是-215~215-1,而32768等于215,超出范围了),因此encoding必须升级到INTSETENC_INT32(值为4),即用4个字节表示一个元素。在添加每个元素的过程中,intset始终保持从小到大有序。与ziplist类似,intset也是按小端(little endian)模式存储的(参见维基百科词条[Endianness](https://en.wikipedia.org/wiki/Endianness))。比如,在上图中intset添加完所有数据之后,表示encoding字段的4个字节应该解释成0x00000004,而第4个数据应该解释成0x00008000 = 32768



发布于: 2020 年 04 月 29 日 阅读数: 31
用户头像

Nick

关注

还未添加个人签名 2017.12.22 加入

还未添加个人简介

评论

发布
暂无评论
redis数据结构介绍三-第三部分 整数集合