Redis 内部数据结构详解(7)：intset

数据分析与开发 · 公众号 · 数据库 · 2017-05-12 11:55

正文

（点击上方公众号，可快速关注）

作者：张铁蕾

zhangtielei.com/posts/blog-redis-intset.html

如有好文章投稿，请点击 → 这里了解详情

本系列基于 Redis 3.2 分支

本文是《Redis内部数据结构详解》系列的第七篇。在本文中，我们围绕一个Redis的内部数据结构——intset展开讨论。

Redis里面使用intset是为了实现集合(set)这种对外的数据结构。set结构类似于数学上的集合的概念，它包含的元素无序，且不能重复。Redis里的set结构还实现了基础的集合并、交、差的操作。与Redis对外暴露的其它数据结构类似，set的底层实现，随着元素类型是否是整型以及添加的元素的数目多少，而有所变化。概括来讲，当set中添加的元素都是整型且元素数目较少时，set使用intset作为底层数据结构，否则，set使用dict作为底层数据结构。

在本文中我们将大体分成三个部分进行介绍：

集中介绍intset数据结构。
讨论set是如何在intset和dict基础上构建起来的。
集中讨论set的并、交、差的算法实现以及时间复杂度。注意，其中差集的计算在Redis中实现了两种算法。

我们在讨论中还会涉及到一个Redis配置（在redis.conf中的ADVANCED CONFIG部分）：

set-max-intset-entries 512

intset数据结构简介

intset顾名思义，是由整数组成的集合。实际上，intset是一个由整数组成的有序集合，从而便于在上面进行二分查找，用于快速地判断一个元素是否属于这个集合。它在内存分配上与ziplist有些类似，是连续的一整块内存空间，而且对于大整数和小整数（按绝对值）采取了不同的编码，尽量对内存的使用进行了优化。

intset的数据结构定义如下（出自intset.h和intset.c）：

typedef struct intset {

uint32_t encoding;

uint32_t length;

int8_t contents[];

} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))

#define INTSET_ENC_INT32 (sizeof(int32_t))

#define INTSET_ENC_INT64 (sizeof(int64_t))

各个字段含义如下：

encoding: 数据编码，表示intset中的每个数据元素用几个字节来存储。它有三种可能的取值：INTSET_ENC_INT16表示每个元素用2个字节存储，INTSET_ENC_INT32表示每个元素用4个字节存储，INTSET_ENC_INT64表示每个元素用8个字节存储。因此，intset中存储的整数最多只能占用64bit。
length: 表示intset中的元素个数。encoding和length两个字段构成了intset的头部（header）。
contents: 是一个柔性数组（flexible array member），表示intset的header后面紧跟着数据元素。这个数组的总长度（即总字节数）等于encoding * length。柔性数组在Redis的很多数据结构的定义中都出现过（例如sds,quicklist, skiplist），用于表达一个偏移量。contents需要单独为其分配空间，这部分内存不包含在intset结构当中。