0%

redis底层之整数集合INTSET

跳跃列表是一种数据结构,它允许快速查询一个有序连续元素的数据链表,其平均查找和插入时间复杂度都是O(logn),优于普通队列的O(n)。

一、定义

      intset,即整数集合,一个由整数组成的有序集合,从而便于在上面进行二分查找进而快速地判断一个元素是否属于这个集合。它在内存分配上与ziplist有些类似,是连续的一整块内存空间,而且对于大整数和小整数(按绝对值)采取了不同的编码(INTSET_ENC_INT16/32/64),尽量对内存的使用进行了优化,其内部结构如下(redis-6.0.7):

1
2
3
4
5
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
  • encoding:编码方式,contents数组的真正类型取决于encoding属性的值;
    • INTSET_ENC_INT16,则contents数组里的每个数据项都是一个int16_t类型的整数值,可表示范围2^16次方,即-32768~32767
    • INTSET_ENC_INT32,则contents数组里的每个数据项都是一个int32_t类型的整数值,可表示范围2^32次方,即-2147483648~2147483647
    • INTSET_ENC_INT64,则contents数组里的每个数据项都是一个int64_t类型的整数值,可表示范围2^64次方,即-9223372036854775808~9223372036854775807
  • length:整数集合包含的元素数量,也即是contents数组的长度;
    • encoding和length两个字段构成了intset的头部header
  • contents:整数集合的底层实现,集合的每个元素都是contents数组的一个数组项(item),各个项在数组中按值的大小从小到大有序地排列(便于二分查找),并且数组中不包含任何重复项。

当新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级(upgrade),然后才能将新元素添加到整数集合里面;一旦进行了升级,编码就会一直保持升级后的状态。

二、添加

三、参考