网站内链建设_湘潭网站优化_正规接单赚佣金的平台_网络营销的内容有哪些方面

Redis 源码分析-内部数据结构 intset

intset 是用于实现集合 (set) 这种对外的数据结构。它包含的元素无序，且不能重复。当插入的元素都是整形，底层使用 intset 存储，否则使用 dict。

intset 结构和部分函数分析

结构体定义如下：

// intset 结构体
typedef struct intset {uint32_t encoding;      // 数据编码，表示 intset 中的每个数据元素用几个字节（2、4、8）来存储，超出上限就需要转 dict 存储uint32_t length;        // 表示 intset 中的元素个数int8_t contents[];      // 柔性数组 总长度为  encoding * length
} intset;

各字段含义如下：

encoding 数据编码，表示intset中的每个数据元素用几个字节来存储。

可选值：

#define INTSET_ENC_INT16 (sizeof(int16_t))		// 2字节
#define INTSET_ENC_INT32 (sizeof(int32_t))		// 4字节
#define INTSET_ENC_INT64 (sizeof(int64_t))		// 8字节

length intset 中的元素个数
contents 柔性数组，存放真实数据，总大小为 encoding * length

需要注意的是，intset 会随着数据的添加而改变它的数据编码

127.0.0.1:6379> sadd myset 1 2 3
(integer) 3
127.0.0.1:6379> memory usage myset
(integer) 61
127.0.0.1:6379> sadd myset 4 5
(integer) 2
127.0.0.1:6379> memory usage myset
(integer) 65
127.0.0.1:6379> sadd myset 36666
(integer) 1
127.0.0.1:6379> memory usage myset
(integer) 79

我们来分析一下：

添加 3 个小元素后，myset 占用 61 字节，再添加两个小元素，myset 占用 65 字节，说明 1 个小元素占用 2字节，与我们的分析一致。同时也可以得出除了元素所占的空间，结构体本身占用 65 - 5*2 = 55 字节。

接着我们添加了 36666 元素，超出了 2 字节的表示范围，因此变为了4字节编码，共有（1、2、3、4、5、36666）6 个元素，占用 24 字节。

结构体本身 55 字节 + 元素 24 字节 = 79 字节

与输出结果一致。

了解了数据结构后，分析两个主要函数（插入和查找）：

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {// 获取要插入 value 的编码类型uint8_t valenc = _intsetValueEncoding(value);uint32_t pos;if (success) *success = 1;// 如果比当前的编码类型大，需要进行升级if (valenc > intrev32ifbe(is->encoding)) {return intsetUpgradeAndAdd(is, value);} else {// 如果当前 value 已经存在if (intsetSearch(is, value, &pos)) {if (success) *success = 0;return is;}// 内存扩充以容纳新的元素is = intsetResize(is, intrev32ifbe(is->length) + 1);// 将待插入位置后面的元素统一向后移动 1 个位置if (pos < intrev32ifbe(is->length)) intsetMoveTail(is, pos, pos + 1);}// 把 value 插入到指定 pos_intsetSet(is, pos, value);// length + 1is->length = intrev32ifbe(intrev32ifbe(is->length) + 1);return is;
}

获取要插入数据的编码类型，与当前编码类型比较
- 比当前编码类型大，进行升级存储，同时由于是新元素造成的存储升级，所以很轻松知道要插入元素的位置
- 比当前编码类型小，传入 value 进行查找
  - 能找到，直接返回
  - 找不到，返回要插入的位置，首先进行内存扩充以容纳新元素，再把要插入位置的后面元素集体后移1个位置，最后把当前 value 插入到指定位置，整体长度 + 1
这个插入方法时间复杂度为 O(N)

// 在指定的 intset 中查找指定的元素 value，如果找到，则返回 1 并且将参数 pos 指向找到的元素位置
// 如果没找到，则返回 0 并且将参数 pos 指向能插入该元素的位置。
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {// intset 里的数据是按小端（little endian）模式存储的，因此在大端（big endian）机器上运行时，这里的 intrev32ifbe 会做相应的转换int min = 0, max = intrev32ifbe(is->length) - 1, mid = -1;int64_t cur = -1;// 如果 intset 为空,直接返回 0 和要插入的位置 0if (intrev32ifbe(is->length) == 0) {if (pos) *pos = 0;return 0;} else {// 如果要插入的 value > 最大值 或 < 最小值,那么要插入的位置就确定了if (value > _intsetGet(is, max)) {if (pos) *pos = intrev32ifbe(is->length);return 0;} else if (value < _intsetGet(is, 0)) {if (pos) *pos = 0;return 0;}}// 二分查找要插入的位置while (max >= min) {mid = ((unsigned int) min + (unsigned int) max) >> 1;cur = _intsetGet(is, mid);if (value > cur) {min = mid + 1;} else if (value < cur) {max = mid - 1;} else {break;}}// 如果找到的值就是要插入的值，返回1，并把 pos 指向该位置if (value == cur) {if (pos) *pos = mid;return 1;} else {    // 返回 0，并把 pos 指向该插入的位置if (pos) *pos = min;return 0;}
}

查找时首先对特殊情况进行处理（intset为空、比最小值小，比最大值大）
接着进行二分查找
- 如果最后找到的值和要插入的值相同，修改 pos 为当前位置，返回 1
- 如果不同，说明需要插入，pos 指向要插入的位置，返回 0
查找时间复杂度为 O(log N)

ziplist 对比

Intset 和 ziplist 相比，都有时间换空间的意思，但也有一些不同：

intset 中每个元素都是定长的，ziplist 元素长度可以不同
intset 只能存储整数，而 ziplist 任意二进制串都可以存储
intset 中的元素是有序的，查找时可以进行二分查找，而 ziplist 只能遍历

另外，intset 在以下情况发生时会转变为 dict

添加了字符串，intset 无法表示

127.0.0.1:6379> sadd myset 1 2 3
(integer) 3
127.0.0.1:6379> object encoding myset
"intset"
127.0.0.1:6379> sadd myset zwj
(integer) 1
127.0.0.1:6379> object encoding myset
"hashtable

添加了一个数字，但它超出了能表示的范围。intset 能够表达的最大的整数范围为 -2⁶⁴~2⁶⁴-1，因此，如果添加的数字超出了这个范围，这也会导致 intset 转成 dict
添加的集合元素个数超过了set-max-intset-entries配置的值（默认 512）的时候，此时查找效率为 O(log N)，数据量大时会比较慢，也会导致 intset 转成 dict