Redis - set底层数据结构实现

前言

Set为无序的，自动去重的集合数据类型，Set数据结构底层实现为一个value为null的字典(dict)，当数据可以用整型表示时，Set集合将被编码为intset数据结构。 两个条件任意一个不满足时，将用hashtable存储数据。 1. 元素个数大于set-max-intset-entries；2. 元素无法用整型表示

# Sets have a special encoding in just one case: when a set is composed
# of just strings that happen to be integers in radix 10 in the range
# of 64 bit signed integers.
# The following configuration setting sets the limit in the size of the
# set in order to use this special memory saving encoding.
set-max-intset-entries 512

实验

127.0.0.1:6379> sadd a-set a b c d d e f
(integer) 6
127.0.0.1:6379> smembers a-set
1) "a"
2) "d"
3) "b"
4) "f"
5) "c"
6) "e"
127.0.0.1:6379> object encoding a-set
"hashtable"

当加入非数字到set中，底层编码是hashtable。

127.0.0.1:6379> sadd b-set 1 2 3 3 3 4 5 6 7
(integer) 7
127.0.0.1:6379> smembers b-set
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
127.0.0.1:6379> object encoding b-set
"intset"

当加入到set中的元素全是整型时，底层编码是intset，数据结构是有序的。

127.0.0.1:6379> sadd b-set c
(integer) 1
127.0.0.1:6379> smembers b-set
1) "1"
2) "7"
3) "4"
4) "3"
5) "c"
6) "5"
7) "6"
8) "2"
127.0.0.1:6379> object encoding b-set
"hashtable"

再次往b-set加入一个非整型元素，此时b-set底层编码改为hashtable，数据无序。

intset

整数集合是一个有序的，存储整型数据的结构。 整型集合在Redis中可以保存int16_t，int32_t，int64_t类型的整型数据，并且可以保证集合中不会出现重复数据。

typedef struct intset{
    uint32_t encoding;   // 编码类型，3个可选，根据元素中最大值判断是否需要修改编码方式
    uint32_t length;       //  元素个数
    int8_t contents[];    //  元素存储
}

可以把整数集合看成是一个有序的数组，查找某个值时，可以使用二分法查找，复杂度为logn。
encoding - length - data1 - data2 - ... - datan