网站设计建设维护,邯郸做网站就找安联网络,网站建设课结课感受,wordpress自适应画廊集合对象 集合对象的编码可以是intset或者hashtable#xff0c;intset编码的集合对象使用整数集合作为底层实现#xff0c;集合对象包含的所有元素都被保存在整数集合里面。举个栗子#xff0c;以下代码将创建一个图1-12所示的intset编码集合对象#xff1a; 127.0.0.1:637…集合对象 集合对象的编码可以是intset或者hashtableintset编码的集合对象使用整数集合作为底层实现集合对象包含的所有元素都被保存在整数集合里面。举个栗子以下代码将创建一个图1-12所示的intset编码集合对象 127.0.0.1:6379 SADD numbers 1 3 5
(integer) 3
127.0.0.1:6379 OBJECT ENCODING numbers
intset图1-12 inset编码的numbers集合对象 另一方面hashtable编码的集合对象使用字典作为底层实现字典的每个键都是一个字符串对象每个字符串对象包含了一个集合元素而字典的值则全部被设置为NULL以下的示例将创建一个如图1-13所示的hashtable编码集合对象 127.0.0.1:6379 SADD fruits apple banana cherry
(integer) 3
127.0.0.1:6379 OBJECT ENCODING fruits
hashtable图1-13 hashtable编码的fruits集合对象 编码的转换 当集合对象可以同时满足以下两个条件时对象使用intset编码 集合对象保存的所有元素都是整数值集合对象保存的元素数量不超过512个不能满足以上两个条件对的集合对象需要使用hashtable编码注意第一个条件是无法修改的但第二个条件的上限值可以修改具体请看配置文件中关于set-max-intset-entries选项的说明 对于使用intset编码的集合对象来说当使用intset编码所需的两个条件的任意一个不能被满足时就会执行对象的编码转换操作原本保存在整数集合中的所有元素都会被转移并保存到字典里面并且对象的编码也会从intset变为hashtable 举个栗子以下代码创建一个只包含整数元素的集合对象该对象原来的编码为intset但我们只要添加一个字符串元素集合对象的编码转移操作就会被执行 127.0.0.1:6379 SADD numbers 1 3 5
(integer) 3
127.0.0.1:6379 OBJECT ENCODING numbers
intset
127.0.0.1:6379 SADD numbers seven
(integer) 1
127.0.0.1:6379 OBJECT ENCODING numbers
hashtable除此之外如果我们创建一个包含512个整数元素的集合对象那么对象的编码应该是intset。但是只要我们再往集合添加一个整数元素使得这个集合的元素变为513那么对象的编码转换操作就会被执行 127.0.0.1:6379 EVAL for i1, 512 do redis.call(SADD, KEYS[1], i) end 1 integers
(nil)
127.0.0.1:6379 SCARD integers
(integer) 512
127.0.0.1:6379 OBJECT ENCODING integers
intset
127.0.0.1:6379 SADD integers 10086
(integer) 1
127.0.0.1:6379 SCARD integers
(integer) 513
127.0.0.1:6379 OBJECT ENCODING integers
hashtable集合命令的实现 因为集合键的值为集合对象所以用于集合键的所有命令都是针对集合对象来操作的表1-10列出了其中一部分集合键的命令以及这些命令在不同编码的集合对象下的实现方法 表8-10集合命令的实现方法命令intset编码的实现方法hashtable编码的实现方法SADD调用intsetAdd函数将所有新元素添加到整数集合里面调用dictAdd以新元素为键NULL为值将键值对添加到字典里面SCARD调用intsetLen函数返回整数集合所包含的元素数量这个数量就是集合对象所包含的元素数量调用dictSize函数返回字典所包含的键值对数量这个数量就是集合对象所包含的元素数量SISMEMBER调用intsetFind函数在整数集合中查找给定的元素如果找到了说明元素存在于集合没找到则说明元素不存在于集合调用dictFind 函数在字典的键中查找给定的元素如果找到了说明元素存在于集合没找到则说明元素不存在于集合SMEMBERS遍历整个整数集合使用intsetGet函数返回集合元素遍历整个字典使用dictGetKey函数返回字典的键作为集合元素SRANDMEMBER调用intsetRandom函数从整数集合中随机返回一个元素调用dictGetRandomKey函数从字典中随机返回一个字典键SPOP调用intsetRandom函数从整数集合中随机取出一个元素在将这个随机元素返回给客户端之后调用intsetRemove函数 将随机元素从整数集合中删除掉调用dictGetRandomKey函数从字典中随机取出一个字典键在将这个随机字典键的值返回给客户端之后调用 dictDelete函数从字典中删除随机字典键所对应的键值对SREM调用intsetRemove函数从整数集合中删除所有给定的元素调用dictDelete函数从字典中删除所有键为给定元素的键值对 有序集合对象 有序集合的编码可以是ziplist或者skiplistziplist编码的压缩列表中每个集合元素使用两个紧挨在一起的压缩列表节点来保存第一个节点保存元素的成员member而第二个元素保存元素的分值score。压缩列表内的集合元素按分值从小到大进行排序分值较小的元素被放置在靠近表头的方向而分值较大的元素则被放置在靠近表尾的方向 举个栗子如果我们执行以下ZADD命令那么服务器将创建一个有序集合对象作为price键的值 127.0.0.1:6379 ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3
127.0.0.1:6379 OBJECT ENCODING price
ziplistprice这个值对象如图1-14所示而对象所使用的的压缩列表如图1-15所示 图1-14 ziplist编码的有序集合对象 图1-15 有序集合元素在压缩列表中按分值从小到大排列 skiplist编码的有序集合对象使用zset结构作为底层实现一个zset结构同时包含一个字典和一个跳跃表 redis.h typedef struct zset {dict *dict;zskiplist *zsl;
} zset;typedef struct zskiplistNode {robj *obj;double score;struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned int span;} level[];
} zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level;
} zskiplist;zset结构中的的zsl跳跃表按分值从小到大保存了所有集合元素每个跳跃表节点都保存了一个集合元素跳跃表节点的obj属性保存了元素的成员而跳跃表节点的score属性则保存了元素的分值。通过这个跳跃表程序可以对有序集合进行范围型操作比如ZRANK、ZRANGE等命令就是基于跳跃表API来实现的 除此之外zset结构中的dict字典为有序集合创建了一个从成员到分值的映射字典中的每个键值对都保存了一个集合元素字典的键保存了元素的成员而字典的值则保存了元素的分值。通过这个字典程序可以在O(1)的时间复杂度内查找给定成员的分值ZSCORE命令就是根据这一特性实现的而很多其他有序集合命令都在实现的内部用到了这一特性 有序集合中每个元素的成员都是一个字符串对象而每个元素的分值都是一个double类型的浮点数。值得一提的是虽然zset结构同时使用跳跃表和字典来保存有序集合元素但这两种数据结构都会通过指针来共享相同元素的成员和分值所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或分值也不会因为浪费额外的内存 为什么有序集合需要同时使用跳跃表和字典来实现在理论上有序集合可以单独使用字典或者跳跃表其中一种数据结构来实现但无论使用字典还是跳跃表在性能上比起同时使用字典和跳跃表都会有所降低。举个例子如果我们只是用字典来实现有序集合那么虽然可以在O(1)的时间复杂度内查找成员对应的分值但是因为字典以无序的方式来保存集合元素所以每次在执行范围型操作——比如ZRANK、ZRANGE等命令时程序都需要对字典的所有元素进行排序完成这种排序至少需要O(N logN)的时间复杂度以及额外的O(N)内存空间因为要创建一个数组来保存排序后的元素 另一方面如果我们只使用跳跃表来实现有序集合那么跳跃表执行范围型操作时的所有优点都会被保留但因为没有了字典所以根据成员查找分值这一操作的时间复杂度将从O(1)上升至O(logN)。因为以上原因为了让有序集合的查找和范围型操作都尽可能快地执行Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合 举个栗子如果前面的price键创建的不是ziplist编码的有序集合对象而是skiplist编码的有序集合对象那么这个有序集合对象将会是图1-16所示的样子而对象所使用的zset结构将会是图8-17所示的样子 图1-16 skiplist编码的有序集合对象 图1-17 有序集合元素同时被保存在字典和跳跃表中 编码的转换 当有序集合对象可以同时满足以下条件时对象使用ziplist编码 有序集合保存的元素数量小于128个有序集合保存的所有元素的长度小于64字节不能满足以上两个条件的有序集合对象将使用skiplist编码 # 对象包含了 128 个元素
127.0.0.1:6379 EVAL for i1, 128 do redis.call(ZADD, KEYS[1], i, i) end 1 numbers
(nil)
127.0.0.1:6379 ZCARD numbers
(integer) 128
127.0.0.1:6379 OBJECT ENCODING numbers
ziplist
# 再添加一个新元素
127.0.0.1:6379 ZADD numbers 3.14 pi
(integer) 1
# 对象包含的元素数量变为 129 个
127.0.0.1:6379 ZCARD numbers
(integer) 129
# 编码已改变
127.0.0.1:6379 OBJECT ENCODING numbers
skiplist以下代码则展示了有序集合对象因为元素的成员过长而引发编码转换的情况 # 向有序集合添加一个成员只有三字节长的元素
127.0.0.1:6379 ZADD blah 1.0 www
(integer) 1
127.0.0.1:6379 OBJECT ENCODING blah
ziplist
# 向有序集合添加一个成员为 66 字节长的元素
127.0.0.1:6379 ZADD blah 2.0 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
(integer) 1
# 编码已改变
127.0.0.1:6379 OBJECT ENCODING blah
skiplist有序集合命令的实现 因为有序集合键的值为哈希值所以用于有序集合键的所有命令都是针对哈希对象来构建的表1-11列出了其中一部分有序集合键命令以及这些命令在不同编码的哈希对象下的实现方法 表 8-11有序集合命令的实现方法命令ziplist编码的实现方法zset编码的实现方法ZADD调用ziplistInsert函数 将成员和分值作为两个节点分别插入到压缩列表先调用zslInsert函数将新元素添加到跳跃表然后调用dictAdd 函数将新元素关联到字典ZCARD调用ziplistLen函数获得压缩列表包含节点的数量将这个数量除以2得出集合元素的数量访问跳跃表数据结构的length属性 直接返回集合元素的数量ZCOUNT遍历压缩列表统计分值在给定范围内的节点的数量遍历跳跃表统计分值在给定范围内的节点的数量ZRANGE从表头向表尾遍历压缩列表返回给定索引范围内的所有元素从表头向表尾遍历跳跃表返回给定索引范围内的所有元素ZREVRANGE从表尾向表头遍历压缩列表返回给定索引范围内的所有元素从表尾向表头遍历跳跃表返回给定索引范围内的所有元素ZRANK从表头向表尾遍历压缩列表查找给定的成员沿途记录经过节点的数量当找到给定成员之后途经节点的数量就是该成员所对应元素的排名从表头向表尾遍历跳跃表查找给定的成员沿途记录经过节点的数量当找到给定成员之后途经节点的数量就是该成员所对应元素的排名ZREVRANK从表尾向表头遍历压缩列表查找给定的成员沿途记录经过节点的数量当找到给定成员之后 途经节点的数量就是该成员所对应元素的排名从表尾向表头遍历跳跃表查找给定的成员沿途记录经过节点的数量当找到给定成员之后 途经节点的数量就是该成员所对应元素的排名ZREM遍历压缩列表删除所有包含给定成员的节点以及被删除成员节点旁边的分值节点遍历跳跃表删除所有包含了给定成员的跳跃表节点。 并在字典中解除被删除元素的成员和分值的关联ZSCORE遍历压缩列表查找包含了给定成员的节点然后取出成员节点旁边的分值节点保存的元素分值直接从字典中取出给定成员的分值转载于:https://www.cnblogs.com/beiluowuzheng/p/9737243.html
