Redis-整数集合

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多(不超过REDIS_SET_MAX_INTSET_ENTRIES个,其他情况下用的hashtable)时,Redis使用整数集合作为集合键的底层实现
整数集合的结构
- encoding | length | contents[]
- encoding: contents中数据值占用的位数
- length: 整数集合的长度
- contents: 从小到大顺序保存的集合元素
涉及到的问题:
- 升级
  触发情形: 新添加的元素比整数集合现有元素的类型都要长时,会触发升级
  升级的三步: 分配空间 => 原数据迁移 => 添加新数据
  好处: 提升整数集合的灵活性, 尽可能地节约内存
- 降级
  不支持降级
- 主要API的时间复杂度
  intsetAdd: O(n)
  intsetRemove: O(n)
  intsetFind: O(logn)
  添加和删除涉及到元素之后所有元素的移动,时间复杂度为O(n).查找时,因为是有序的,可以使用二分查找时间复杂度为O(logn)
总结
- Redis中处理小数据量的时候,会优先选择使用连续的内存空间,这样做便于降低内存分配和回收次数和指针的运算(intset, ziplist, embstr). 这也是为什么Redis的对象一般都有两种数据结构用于存储.

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。