Redis数据类型之Set

  1. 云栖社区>
  2. 博客>
  3. 正文

Redis数据类型之Set

技术小牛人 2017-11-22 21:26:00 浏览595
展开阅读全文

前言:set类似于数学上面的集合概念,包含的元素无序,不能重复,能进行交、并、差操作。

      一、内部原理

             set数据结构,也是随着元素数目的多少而变化。当set中添加的元素都是整数且元素数据较少时,set使用intset为底层的数据结构,否则,set使用dict作为底层的数据结构。

             intset是什么?

             从字面意思可以看出是由整数组成的集合。是一个整数组成的有序集合,便于进行二分查找,快速判断一个元素是否属于这个集合。内存分配上也是一整块连续的内存空间,而且根据数值的大小采取了不同的编码,对内存使用进行了优化。
             intset数据结构如下:

 typedef struct intset {
    uint32_t encoding;/*数据编码,表示intset中每个数据元素用几个字节来存储。有三种:数据编码,表示intset中每个数据元素用几个字节来存储。
                       1.INTSET_ENC_INT16表示每个元素用2个字节存储,
                       2.INTSET_ENC_INT32表示每个元素用4个字节存储,
                       3.INTSET_ENC_INT64表示每个元素用8个字节存储。
                       因此,intset中存储的整数最多只能占用64bit*/
    uint32_t length; /*元素个数。encoding和length组成了intset头部。*/    
    int8_t contents[]; /*是一个柔性数组,表示intset的header后面紧跟着数据元素。这个数组的总长度(即总字节数)等于encoding * length*/     } intset;

            注:intset可能会随着数据的添加而改变它的数据编码,创建时intset使用占内存最小的INTSET_ENC_INT16作为编码,每增加一个元素,则根据大小决定是否对数据编码进行改变。

            例子:

            

             如上图:
             1、新建一个intset只有一个header,总共8个字节,encoding=2,length=0。
             2.、添加6,15之后,因为数值较小,所以encoding不变,length=2。
             3、添加32768的时候,超过了两个字节(2个字节能表达的数据范围是-32768~32767),此时encoding升级到INTSET_ENC_INT32为4,即用4个字节表示一个元素。 
             4、添加元素都是按照从小到大的顺序。
             5、intset是按little endian模式存储的。在上图intset添加完所有数据之后,32768=>0x00008000
             什么时间转为dict?
             1、大于512,默认设置:set-max-intset-entries 512
             2、超出最大范围-264~264-1
             3、元素里面包含非数字
             set底层用dict时,key是要添加的元素,value为NULL。
             区别:
             小集合(整数)用intset存储节省内存。dict带来的开销很大(包含元数据信息,两个hash表、链表指针等等)
             从时间复杂度上看,intset是o(log n),而dict可以认为是o(1)(因为zipmap),但是intset元素个数较少,影响不大

      二、相关操作
             SADD key member [member ...] 
             将一个或多个元素加入到集合key中,已存在被忽略。若不存在,则创建。
             SCARD key
             返回集合key的数目。
             SDIFF key [key ...]
             返回集合之间的差集
             SDIFFSTORE destination key [key ...]
             返回集合之间的差集,并将结果存储到目标集合。
             SINTER key [key ...]
             返回集合集合之间的交集
             SINTERSTORE destination key [key ...] 
             返回集合之间的交集,并将结果存储到目标集合。
             SISMEMBER key member
             判断元素是否属于集合key的成员。
             SMOVE source destination member
             将元素从源集合移动到目标集合。
             SPOP key
             随机移除key集合的某一元素,并返回该元素。
             SRANDMEMBER key [count]
             随机返回一个key集合的元素,若提供count参数,则返回一个包含count个元素的数组。
             SREM key member [member ...]
             移除集合中的一个或多个元素。不存在则忽略。
             SUNION key [key ...]
             返回若干个集合的并集。
             SUNIONSTORE destination key [key ...]
             返回若干个集合的并集,并存储在目标集合

本文转自  zddnd  51CTO博客,原文链接:
http://blog.51cto.com/13013666/1940193

网友评论

登录后评论
0/500
评论