Redis有序集合zset原理及应用

zset主要功能

1）根据value查询对应score；
2）根据score来排序；
3）指定score的范围，查询对应的value列表；

怎么实现

1通过hashtable实现，类似Java的HashMap；
2和3通过跳表实现；
zset是一个混合的数据结构，哈希表+跳表；

score相同怎么办

按照value的字典序排序

跳表是怎么排序的

跳表是一个有序表，比如像下面：

("zs",2) -> ("gh",4) -> （“fv”，5）-> （“kl”，5）

上面的value 中 fv和 kl 重复了，按照字典序，fv排在前面，kl排在后面

跳表可以实现map吗

可以，只要限制要比较的数据不允许重复就行，如果重复就覆盖原来的值。比如Java的ConcurrentSkipListMap就是用跳表实现的map，并且是多线程安全的。

redis的跳表节点层高如何决定的

redis 6.2.6的源码

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

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

结论：
redis 跳表节点的层高最高是32，zslRandomLevel得到1的概率为1-0.25，得到2的概率为(1-0.25)0.75，得到3的概率为(1-0.25)0.750.75，以此类推发现，越大的数出现的概率越小，这也叫做幂次定律（powerlaw）。即拥有层数越多的节点会越少，每个节点至少会有1层。

zset怎么实现范围查询

给定范围[start,end]，找到跳表中比start小的最右节点，那么下一个节点必定>=start，然后遍历后面节点直到>end