redis数据结构之整数集合

参考文献:黄健宏《Redis设计与实现》

用处

整数集合是集合键的底层实现之一

当一个集合中只包含整数值元素且元素的数量不多时,redis就会使用整数集合作为集合键的底层实现

实现

整数集合可以保存类型为int16_t,int32_t,或者int64_t的整数值,并且会保证集合中不会出现重复元素

redis用intset结构来表示一个整数集合

typedef struct intset {
  // 编码方式
  uint32_t encoding;

  // 集合包含的元素数量
  uint32_t length;

  // 保存元素的数组
  int8_t contents[];
}

其中主要是contents数组,用来存储整数集合的每一个元素item,各个项在数组中按值的大小从小到大有序的排列,并且数组中不包含任何重复项

这里需要注意的是:虽然intset结构将contents属性声明为了int8_t类型,但实际上contengs数组并不保存任何的int8_t类型的值,contents数组的真正类型取决于encoding属性的值

即这里如果计算一个整数集合中元素占用大小的话需要根据encoding属性的值得出contents数组的item元素的类型为什么,再乘以length属性的值即可

何为整数集合的升级

既然提到升级,那么什么样的场景需要进行整数集合的升级?具体的升级又是升级什么?

前面说到了整数集合具体的contents类型是由encoding属性决定的,那么我们假设一种情况:

当一个整数集合中只有int16_t类型的item时,那么这个整数集合的encoding值为int16_t 即可,不需要采用int64_t类型来浪费内存,

如果这个时候我们向该整数集合中添加了一个int64_t 类型的整数,比如:-2675256175807981027 这个时候现有的整数集合元素类型为int16_t就放不下该元素,这个时候就需要进行整数集合的升级,升级的是整数集合中存储元素的类型

概括一下就是:

每当我们将一个新元素添加进整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长的时候,整数集合就需要进行升级,升级以后才能将新元素添加到整数集合中

升级步骤

  • 根据新元素的类型,扩展整数集合底层数组的空间大小,为新元素分配空间

  • 转换底层数组中现有元素的类型为新元素的类型,并将类型转换后的元素放到正确的位置上,且需要维持底层数组的有序性质

  • 将新元素添加到底层数组中

  • 更新整数集合的length属性

步骤解析

假如现有整数集合中有三个int16_t 类型的元素 1, 2, 3

新元素为int32_t 类型的65535

在第一步中,扩展数组的空间大小是需要根据新元素的类型计算出扩展后的数组空间大小

那么计算出扩展后的底层数组的占用空间大小为:4 * 32 = 128位

另一个需要注意的是数组在内存中是一块连续的内存空间

数组中的下标对应的内存的体现就是位,比如128位的数组,分四个元素,那么对应0下标的元素占用的位就是0-31 ,相应的1下标对应的位是32-63 ,2下标对应的位为64-95 ,而下标3即第四个元素对应的位为96-127位


为什么升级

  • 提升整数集合的灵活性

因为整数集合提供了自动升级功能,所以我们在使用时并不需要担心出现类型错误,可以随意的将不同类型的整数添加到整数集合中

  • 节约内存

redis设计整数集合时,是可以将整数集合中元素的类型设计成int64_t的,这样带来结果是虽然可以向其中任意添加int16_t,int32_t,int64_t 类型的元素不用担心类型错误,但是弊端就是浪费内存,redis作为内存数据库,对内存尤为重视

是否支持自动降级?

整数集合不支持自动降级,一旦对数组进行了升级,encoding编码属性就会一直保存升级以后的状态

总结

  • 整数集合是集合键的底层实现之一

  • 整数集合支持自动升级策略

  • 自动升级带来的好处是可以为使用整数集合的我们提供极大的灵活性,不必担心类型错误以及极大的节约了内存使用率

  • 整数集合不支持自动降级,一旦升级完成,就无法降级

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,047评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,807评论 3 386
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,501评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,839评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,951评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,117评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,188评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,929评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,372评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,679评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,837评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,536评论 4 335
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,168评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,886评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,129评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,665评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,739评论 2 351

推荐阅读更多精彩内容