Redis底层数据结构之IntSet

redis底层数据结构已完结👏👏👏：

• ☑️redis底层数据结构之SDS
• ☑️redis底层数据结构之ziplist
• ☑️redis底层数据结构之quicklist
• ☑️redis底层数据结构之Dict
• ☑️redis底层数据结构之IntSet
• ☑️redis底层数据结构之ZSkipList

一、概述

IntSet是一个存储整数值的集合，内部使用有序、无重复的数组保存数据。优点:节省内存空间。高效的查找、插入和删除操作。使用场景: 在集合键只包含整数值且数量较少时使用。

二、IntSet结构

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))
1
2
3
4
5
6
7
8
9

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结构当中

说明：

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

intset与ziplist相比：

• ziplist可以存储任意二进制串，而intset只能存储整数。
• ziplist是无序的，而intset是从小到大有序的。因此，在ziplist上查找只能遍历，而在intset上可以进行二分查找，性能更高。
• ziplist可以对每个数据项进行不同的变长编码（每个数据项前面都有数据长度字段len），而intset只能整体使用一个统一的编码（encoding）。

三、自动升级

当在一个int16类型的整数集合中插入一个int32类型的值，整个集合的所有元素都会转换成32类型。 整个过程有三步：

• 根据新元素的类型（比如int32），扩展整数集合底层数组的空间大小，并为新元素分配空间。
• 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。
• 最后改变encoding的值，length+1。