redis源码之zset结构的实现

zset为有序的，自动去重的集合数据类型，zset数据结构底层实现为字典(dict)+跳表(skiplist)当数据比较少时，用ziplist编码数据结构存储，当满足以下条件之一时，则采用字典+跳表来存储

zset-max-ziplist-entries 128 //元素个数超过128，将用skiplist编码 zset-max-ziplist-value 64 //单个元素大小超过64byte，将用skiplist编码

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

对于字典(dict)的数据结构来说，可以用O(1)的复杂度拿到对应元素 比如zscore命令 zscore key value 就可以拿到以key为键，value的对应的分值，这个就是在字典(dict)的数据结构中取的，字典(dict)数据结构主要用于判断值是否存在以及拿对应的分值，这个不是我们文章阐述的重点，重点看一下跳跃表(skiplist)的数据结构，看看它是如何实现排序的

skiplist的实现

首先我们来看一看链表的数据结构示意图

链表的话查找我们所需的元素的时间复杂度为O(n)，显然这是我们不能接受的，所以需要对链表进行一步改造

我们每隔两个元素给加一层，然后我们查询从索引层开始查询，遇到了比目标元素大的元素再返回，前往数据层来查询，这样速度会快一些，但是这样速度快的不明显，大概也就快了一半左右，于是我们便想到了加高层数

其实按照上图我们可以计算一下 元素的总个数为N 那么在上图的所以第一层,元素的个数为n/2 index: 1 n/2

那么在上图的所以第二层,元素的个数为n/2^2 index: 2 n/2^2

那么在上图的所以第三层,元素的个数为n/2^3 index: 3 n/2^3

那么在上图的所以第K层,元素的个数为n/2^k index: k n/2^k

比如顶层为2个节点 2 = n/2^k 也就是说 2^k = n/2 ----> k=log2(n-1) 加上数据层的话 k = log2 n 所以我们的层高是 log2 n 查找的时候的时间复杂度是log n

我们可以来看一下skiplist的源码

// zskiplistNode包含了数据和索引，也就是跳表中的一列
typedef struct zskiplistNode {
    sds ele;  //元素
    double score; //分数
    struct zskiplistNode *backward; //往前指的指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;//往后指的指针
        unsigned long span; // 从当前节点到下一个节点的跨度
    } level[];
} zskiplistNode;


typedef struct zskiplist {
    struct zskiplistNode *header, *tail;   //header和tail是方便双向遍历
    unsigned long length; //当前数据包含元素个数
    int level;  // 层高
} zskiplist;

skiplist.png

如何确定索引层的层高

索引层的层高是由一个随机函数，幂次定律实现的

int zslRandomLevel(void) { //幂次定律，随机生成层高，越高的层出现概率越低
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}