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

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

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

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

先上图：

元素支持三种规格：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

原文链接： https://pengrl.com/p/20024/

原文出处： yoko blog ( https://pengrl.com )

原文作者： yoko ( https://github.com/q191201771 )

版权声明：本文欢迎任何形式转载，转载时完整保留本声明信息（包含原文链接、原文出处、原文作者、版权声明）即可。本文后续所有修改都会第一时间在原始地址更新。