简述

整数集合是Redis中值的数据结构中比较简单的一种，其实相当于一个整数数组。当使用set时，如果值的集合中只包含整数和小于一定阈值的时候，Redis就会使用整数集合作为存储值的数据结构。intset查询时间复杂度为O(logN)（因为intset是有序的整数），插入时间复杂度为O(N)，数据结构非常紧凑，占用内存少并且是连续内存，对CPU高速缓存支持非常友好。

整数集合

首先，我们先看看Redis中整数集合的结构体，具体代码在intset.h中。

intset

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

可以看到，intset的结构体很简单，只有三个变量属性，而且都不含指针，contents也是个数据，所以intset的数据结构是非常紧凑的。

• encoding
  编码方式，INT16（2字节），INT32（4字节）和INT64（8字节）。
• length
  数组长度，其实就是记录了元素的数量。
• contents[]
  int8_t类型的数据，整数数据存放在此数组里面。整数集合的每个元素都是contents的成员，并且不会重复。
  虽然声明为int8_t类型，但是实际上contents保存的数据的类型是根据encoding不同而不同。
  最开始，新创建的intset使用占用内存最小的int16_t类型，当后面每添加一个新数据，会根据数据的大小决定是否对数据编码进行升级。

intset数据结构图

以下展示了整数集合结构图

如图所示，contents为int16_t类型的整数集合，数据中存储的3个整数都int_16_t类型，都是是从小到大排序，是有序的。当插入一个int32_t类型的整数时，intset会进行一次整数集合的升级，所有数据类型都会升级为int32_t类型。接下来我们来看看整数集合的升级。

整数集合的升级

当我们新增加一条数据到整数集合里面的时候，如果数据大小不超过encoding所指定大小，则会将数据直接添加到整数集合；如果数据大小超过encoding所指定大小，则会先把整数数组升级，再把新数据插入到整数集合。如下图所示：

流程

1. 新创建一个intset，encoding和length占用8个字节，这时候encoding为int16_t类型，length为0。
2. 当添加了1，2，3三个元素后，因为它们大小都是范围在int16_t类型内，都能用两个字节表示，所以这时候encoding不变，长度变为3。
3. 当添加了100000后，因为100000不能用int16_t类型表示了，这时候encoding需要升级为int32_t类型，这时候需要4个字节代表一个元素。
4. 整数集合类型升级为int32_t类型后，再把100000插入到整数集合中。因为整数集合升级了，代表新插入的元素肯定是最小或者最大，可以看情况放在有序整数集合中的第一位或者最后一位，保持有序性。

注意，整数集合不支持降级操作，一旦数组集合升级了，编码就会一直保持升级后的编码。也就是说，如果我这时候删除了100000这个元素，整数集合类型还是int32_t类型，不会降为int16_t类型。

总结

intset是Redis存值的一种数据结构，用在set结构中。intset其实就是整数数组，这个数组是有序的，无重复的保存着集合元素，集合中的元素是相同的数据类型。
当添加了新的元素打过encoding所指定大小时，整数集合的类型会进行升级。但是一旦数组集合升级后，编码就会一直保持升级后的编码，不会降级。
intset查询时间复杂度为O(logN)，新增元素的时间复杂度为O(N)。