redis-sorted set(zset)实现

       redis支持多种数据结构，本文仅就sorted set展开讨论。

       sorted set与set结构一样均不允许重复的元素，但与set不同的是sorted set除了member(元素)之外，每个member都会关联一个分数score。sorted set根据score对元素进行升序排列，如果有多个元素的分数相同，那么按照member的字典序升序排列，sorted set中元素不允许相同，但score允许相同。

适用场景：

1. 排行榜，以用户id为member，充值总金额或得分作为score，那么就可以得到排行榜，但是需要注意的是sorted set是升序排列的，所以如果想要取前10的话，需要从最后一个元素开始。
2. 消息延迟发送，将消息体作为member，发送时间戳以score的形式存储，通过定时任务扫描sorted set，对score小于等于当前时间的score对应的消息体进行发送。

底层实现：

       sorted set有两种实现方式，一种是ziplist压缩表，一种是zset(dict、skiplist)，redis.conf有两个配置来控制，当sorted set中的元素个数小于128时(即元素对member score的个数，共256个元素)，使用ziplist，若ziplist中所有元素的总长度超过64字节时使用zset。

        ziplist是一个双向链表按照score升序排列，当插入一个(member score)对时，ziplist中插入两个数据项，数据在前，score在后。ziplist只能顺序(正 逆)查找，每一步前进两个数据项(member score)。

      当元素数量或member长度达到限制时，将转为使用zset(dict、skiplist)实现，在dict中提供通过member查询score，而skiplist提供从score到member的查询，skiplist的代码结构如下所示：

//skiplist数据结构定义
#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25
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;

       skiplist也是一种list的形式，但不同的是它是分层的，在开头有两个有两个常量ZSKIPLIST_MAXLEVEL代表每个节点它最多有32层，ZSKIPLIST_P表示当节点有第n层的情况下，它拥有第n+1层的概率为p。zskiplist 结构体中的header和tail表示skiplist有一个头节点一个尾节点，这两个节点中都不存储元素，length表示该调表有多少个元素(member score)，level表示该跳表中最大有多少层。一个节点有多少层是由一个随机函数计算的，如下

randomLevel()
    level := 1
    // random()返回一个[0...1)的随机数
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

       zskiplistNode结构体表示skiplist中的节点的实现形式，该list中一个节点至少有一层，而单从第一层而言，该list是一个双向链表。backward指针指向前一个元素；*obj表示元素中的member，score表示它的分数，当两个元素的score相同时，按照member的字典序升序排列；刚才我们说过skiplist中的元素拥有多层，level数组中forward表示它每一层所指向的下一个元素是什么，span则表示元素与它当层的下个元素之间跨过了几个元素(不包括当前元素，包括指向的元素)。下图为一个简单的skiplist：

       每个向后指的线上面的数字就表示span，表示当前元素在某一层到下个元素跨越了几个元素。下面以查找89为例，该skiplist最大有3层，从head的第三层开始，到78，78后无元素，再从78的第2层到87，87.5第2层后无元素，走87.5的第一层，找到89，路线即为图中标红的部分。如果我们想求89的排名，即把路线的span加起来，(2+2+1)-1=4，从0开始，这是从小到大，降序的顺序为6-2-2-1=1。插入的话与查找相似，即在查找之后再加入一个修改前后元素指针的操作。

       当我们通过member查找score时使用的是dict，时间复杂度为o(1)，通过分数查询member时使用的时skiplist时间复杂度为o(lgn)。为什么redis用skiplist不用平衡树，首先用score查询member，它们的时间复杂度均为o(lgn)；但是从实现复杂度而言，平衡树的增删有可能会造成子树的调整，逻辑较复杂，但是skiplist仅需要调整前后节点的指针。