Redis数据类型之ZSet（五）

q36988

　　前言：有序集合zset跟其他类型一样，同样有几种编码方式。主要有两种编码方式，REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_SKIPLIST。ziplist可以表示较小的有序集合, skiplist表示任意大小的有序集合。
　　何时用REDIS_ENCODING_ZIPLIST？
　　（1）zset会根据zadd命令添加的第一个元素的长度大小来选择编码方式，满足zset_max_ziplist_entries的值不为0，第一个元素的长度小于server.zset_max_ziplist_value，否则就使用skiplist。
　　（2）当待新加的新的字符串长度超过zset_max_ziplist_value（默认值64）时或者ziplist保存的节点数量超过server.zset_max_ziplist_entries（默认值128）时使用skiplist。
　　相关代码一目了然：创建ziplist前面有介绍，在这里不再敖述相关代码在object.c和ziplist.c中。
　　

  if (zobj == NULL) {if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */　　if (server.zset_max_ziplist_entries == 0 ||
　　server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
　　{
　　zobj = createZsetObject();
　　} else {
　　zobj = createZsetZiplistObject();
　　}
　　dbAdd(c->db,key,zobj);
　　} else {
　　if (zobj->type != OBJ_ZSET) {
　　addReply(c,shared.wrongtypeerr);
　　goto cleanup;
　　}
　　}
　　

　　Skiplist：跳跃表是一种随机化的数据结构，基于链表，其效率可以比拟平衡二叉树，插入、查找、删除都可以在对数期望时间内完成（平均复杂度为O(logN),最坏为O(N)），但是又比平衡树简单直观。
　　维基百科提供的Skiplist图：
　　
　　主要有四部分组成
　　A：head：节点指针
　　B：node：元素值，每个节点有一层或多层
　　C：level： 指向该层下一个节点的指针
　　D：tail：全部为null　　
　　Redis的Skiplist代码如下：
　　

/* ZSETs use a specialized version of Skiplists */　　
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;
　　

　　
typedef
struct zset {　　dict
*dict;　　zskiplist
*zsl;　　
} zset;
　　

　　可以清楚的看到redis的skiplist里面多了dict,forward,span几个元素，这三个元素有什么好处呢？
　　1、dict维护了skiplist的元素值（key）和分数（value）用于快读的查找元素对应的分值以及判断元素是否存在。
　　2、forward前向指针，用于从底层表尾向表头方向遍历。的结构中存在span跨度字段
　　3、span存在于forward中，这个跨度字段的出现有助于快速计算元素在整个集合中的排名
　　另外redis的跳跃表中，允许重复的score出现，多个不同的元素score值可以相同，若score值相同时，需要对比member，按字典排序存储在跳表结构中。
　　相关操作：
　　ZADD key score member [[score member] [score member] ...]
　　将一个或多个元素以及值加入到有序集中。不存在创建，存在更新。
　　ZREM key member [member ...]
　　移除一个或这个成员，不存在忽略
　　ZCARD key
　　返回有序集的基数，不存在返回0
　　ZCOUNT key min max
　　返回score在min和max之间的成员
　　ZSCORE key member
　　返回有序集中，成员的score值
　　ZINCRBY key increment member
　　为有序集的成员的score加上相应的增量，不存在则创建
　　ZRANGE key start stop
　　根据基数返回有序集key中，指定区间内的成员，score值从小到大排列
　　ZREVRANGE key start stop
　　根据基数返回有序集key中，指定区间内的成员，score值从大到小排列
　　ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]
　　返回有序集key中，所有score值介于min和max之间的成员。有序集成员按score值从小到大排列
　　ZREVRANGEBYSCORE key max min [WITHSCORES] [LIMIT offset count]
　　返回有序集key中，所有score值介于min和max之间的成员。有序集成员按score值从大到小排列
　　ZRANK key member
　　返回有序集key中成员member的排名。有序集成员按score值从小到大排列
　　ZREVRANK key member
　　返回有序集key中成员member的排名。有序集成员按score值从大到小排列
　　ZREMRANGEBYRANK key start stop
　　移除有序集key中，指定排名(rank)区间内的所有成员。
　　ZREMRANGEBYSCORE key min max
　　移除有序集key中，所有score值介于min和max之间的成员。
　　ZINTERSTORE destination numkeys key [key ...] [WEIGHTS weight [weight ...]] [AGGREGATE SUM|MIN|MAX]
　　计算一个或多个有序集的交集，其中给定的key必须以numkeys参数指定，并将该交集储存到destination
　　注：结果集中某个成员的score值是所有给定集下该成员score值之和
　　ZUNIONSTORE destination numkeys key [key ...] [WEIGHTS weight [weight ...]] [AGGREGATE SUM|MIN|MAX]
　　算给定的一个或多个有序集的并集，其中给定key的数量必须以numkeys参数指定，并将该并集储存到destination
　　注：结果集中某个成员的score值是所有给定集
　　以上的min和max均包含等于。