redis源码阅读之底层数据结构intset整型集合
source link: http://www.pengrl.com/p/20024/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 )
版权声明：本文欢迎任何形式转载，转载时完整保留本声明信息（包含原文链接、原文出处、原文作者、版权声明）即可。本文后续所有修改都会第一时间在原始地址更新。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK