redis数据结构之intset的实例详解
在redis中,intset主要用于保存整数值,由于其底层是使用数组来保存数据的,因而当对集合进行数据添加时需要对集合进行扩容和迁移操作,因而也只有在数据量不大时redis才使用该数据结构来保存整数集合。其具体的底层数据结构如下:
typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; } intset;
整数集合主要有三个属性:encoding用于保存当前集合的编码,有16位,32位和64位三种;length保存了当前整数集合中保存的数据数量;contents属性则保存了具体的数据,其每个数据占用的位数由encoding属性指定。
这里主要需要进行说明的是redis的intset中数据是采用从小到大的顺序存储的,因而对于数据的查询可以采用二分法进行查询,具体的搜索代码如下:
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { int min = 0, max = intrev32ifbe(is->length)-1, mid = -1; int64_t cur = -1; /* The value can never be found when the set is empty */ // 处理 is 为空时的情况 if (intrev32ifbe(is->length) == 0) { if (pos) *pos = 0; return 0; } else { /* Check for the case where we know we cannot find the value, * but do know the insert position. */ // 因为底层数组是有序的,如果 value 比数组中最后一个值都要大 // 那么 value 肯定不存在于集合中, // 并且应该将 value 添加到底层数组的最末端 if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) { if (pos) *pos = intrev32ifbe(is->length); return 0; // 因为底层数组是有序的,如果 value 比数组中最前一个值都要小 // 那么 value 肯定不存在于集合中, // 并且应该将它添加到底层数组的最前端 } else if (value < _intsetGet(is,0)) { if (pos) *pos = 0; return 0; } } // 在有序数组中进行二分查找 // T = O(log N) while(max >= min) { mid = (min+max)/2; cur = _intsetGet(is,mid); if (value > cur) { min = mid+1; } else if (value < cur) { max = mid-1; } else { break; } } // 检查是否已经找到了 value if (value == cur) { if (pos) *pos = mid; return 1; } else { if (pos) *pos = min; return 0; } }
此外,整数集合中具体还有两个需要说明的操作是升级和降级。升级指的是当向低编码的整数集合中添加位数较高的数值时,就会扩容并将整数集合中的所有元素都转换为高位数的编码格式,然后把新添加的元素插入到指定位置;降级指的是当将整数集合中唯一一个高位的元素删除时会将其余元素转换为低位数的编码格式,但是为了提升速率,redis中并不会为剩余元素重新分配内存并进行编码转换,而只是会将该高位元素给删除,并重新分配内存给剩余的元素,然后迁移数据。如图是inset保存数据的示例:
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
暂无评论...
更新日志
2024年05月20日
2024年05月20日
- dnf角色名字
- 舅舅党爆料《星空》或将登陆P55平台!今年圣诞节上线
- 《方舟》开发商确定裁员6人!新作承诺不会受到影响
- 中式恐怖续作《纸嫁衣7》首曝PV公布!现已开启预约
- 周建军-老三骑驴.2017【FLAC】
- 谭维维.2007-耳界【天娱传媒】【WAV+CUE】
- 逃跑计划.2021-回到海洋【东亚星光】【FLAC分轨】
- 《对马岛》击败《战神》《蜘蛛侠》:同时在线最高单机
- 人民日报评《歌手》全开麦直播:抛去滤镜难能可贵
- 《DNF手游》可以下载了:现已开放角色创建
- 群星《醉爱对唱》[WAV+CUE][523M]
- 孟庭苇《留住这一刻》4CD[WAV+CUE][2.5G]
- 张杰《第1张》首版 [WAV+CUE][412M]
- 《永劫无间》反击《王者荣耀》:武道无穷,但请尊重“武道”
- 《星之破晓》回应《永劫无间》:蹭蹭精,莫挨,不欢迎!