Redis基本数据类型：有序集合(sorted set)

Redis内部使用两种结构来实现sorted set

• 压缩列表(ziplist)
• 跳跃列表(skiplist)

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

当存储的节点大于128或者某一个值得长度大于64时，sorted set会使用跳跃列表，否则使用压缩列表

1. 压缩列表(ziplist)

前面已经介绍过，这里就略过了
使用这种结构时，redisObject.encoding = OBJ_ENCODING_ZIPLIST

2. 跳跃列表(skiplist)

使用这种结构时，redisObject.encoding = OBJ_ENCODING_SKIPLIST
先来看一下zset的结构：

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

zset采用这种编码方式时，底层其实是由hashtable和skiplist共同实现的，hashtable主要负责从key查找value，在以前已经介绍过了，而skiplist主要是用来查找一段value，继续来看下skiplist的结构：

typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;

• header - 头指针
• tail - 尾指针
• length - 链表长度
• level - 层数的最大值

typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;

• ele - 存放的数据
• score - 数据分数
• backward - 前向指针，只有level[0]才有
• level - 后向指针，每层对应一个后向指针，保存在forward里面，span记录这一层跨越了几个节点

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements /
#define ZSKIPLIST_P 0.25 / Skiplist P = 1/4 */

Redis里定义的最大层数是64，上面level数组的最大长度是64。概率是1/4，意思是出现下一个跳跃指针的概率是1/4。看下面例子应该会更清楚：
第一层：双向链表，每个节点都会有第一层，节点只有第一层的概率是1-P
第二层：节点出现第二层的概率是P，节点只有第二层的概率是P*(1-P)
第三层：节点出现第三层的概率是P * P，节点只有第三层的概率是P * P * (1-P)
第四层：节点出现第四层的概率是P * P * P，节点只有第四层的概率是P * P * P * (1-P)
以此类推
以顺序插入6，5，4，3，2，1为例

可以看到lv[0]就是一个顺序链表，lv[n]实现了跳跃。当要查找6时，按照普通链表，就是从1遍历到6，查找6次；按照跳跃链表，首先找到2，然后找到5，然后找到6，查找3次。随着数据量和层数的增加，效果会越来越明显。

3. command

• BZPOPMAX - Remove and return the member with the highest score from one or more sorted sets, or block until one is available
• BZPOPMIN - Remove and return the member with the lowest score from one or more sorted sets, or block until one is available
• ZADD - Add one or more members to a sorted set, or update its score if it already exists
• ZCARD - Get the number of members in a sorted set
• ZCOUNT - Count the members in a sorted set with scores within the given values
• ZINCRBY - Increment the score of a member in a sorted set
• ZINTERSTORE - Intersect multiple sorted sets and store the resulting sorted set in a new key
• ZLEXCOUNT - Count the number of members in a sorted set between a given lexicographical range
• ZPOPMAX - Remove and return members with the highest scores in a sorted set
• ZPOPMIN - Remove and return members with the lowest scores in a sorted set
• ZRANGE - Return a range of members in a sorted set, by index
• ZRANGEBYLEX - Return a range of members in a sorted set, by lexicographical range
• ZRANGEBYSCORE - Return a range of members in a sorted set, by score
• ZRANK - Determine the index of a member in a sorted set
• ZREM - Remove one or more members from a sorted set
• ZREMRANGEBYLEX - Remove all members in a sorted set between the given lexicographical range
• ZREMRANGEBYRANK - Remove all members in a sorted set within the given indexes
• ZREMRANGEBYSCORE - Remove all members in a sorted set within the given scores
• ZREVRANGE - Return a range of members in a sorted set, by index, with scores ordered from high to low
• ZREVRANGEBYLEX - Return a range of members in a sorted set, by lexicographical range, ordered from higher to lower strings
• ZREVRANGEBYSCORE - Return a range of members in a sorted set, by score, with scores ordered from high to low
• ZREVRANK - Determine the index of a member in a sorted set, with scores ordered from high to low
• ZSCAN - Incrementally iterate sorted sets elements and associated scores
• ZSCORE - Get the score associated with the given member in a sorted set
• ZUNIONSTORE - Add multiple sorted sets and store the resulting sorted set in a new key

上一篇：Redis学习小计(7) - 基本数据类型：集合(set)
下一篇：