redis源码阅读之底层数据结构intset整型集合

intset是一个整型集合,集合有序,无重复元素,提供了插入、删除、查询、遍历等接口。

内部采用数组存储整型元素。最大支持存储int64整型。

特点是使用数组,空间局部性好。并且在内存占用上做了优化,接下来我们就来说实现部分。

先上图:

redis intset

元素支持三种规格:int16,int32,int64。

使用哪种规格,取决于最大的那个元素的数值范围。初始时是int16。

插入元素时,如果插入的元素的数值范围超过了当前intset规格,则所有元素都要升级规格。也即在一个时刻,一个intset只能有一种规格。一个intset的规格升级后就永远不会降级了(即使之后某些元素删除之后,剩余所有元素的数值范围都下降为更低规格)

intset并不会预申请元素空间大小,每次插入元素,都会调用remalloc扩容。同样,每次删除元素,都会调用remalloc缩容。

元素的存储使用了柔性数组的特性,具体见《聊聊c语言的flexible array member》

intset不提供批量插入接口。插入多个元素只能循环插入。

由于数组要保持有序,所以插入时,需将插入位置之后的所有元素都向后移动。同理,删除元素时,需将删除位置之后的所有元素都向前移动。

由于有序,查找时采用二分查找。这里针对二分做了优化,查找的元素先与最大值比较,如果比最大值还大,则肯定不存在。最小值也是一样。

intset不提供修改接口,因为它是集合,相当于只有key,没有value,也就没有修改这一说,只能增、删。

intset在哪些时候会被用到,我们后面的文章再讲。

redis注释版本源码:https://github.com/q191201771/yoko-read-redis

本文完,作者yoko,尊重劳动人民成果,转载请注明原文出处: https://pengrl.com/p/20024/

0%