Redis跳跃表生成节点层数及其查找值若不在分值范围的探究

一、问题

1. 在Redis的跳跃表中，每个节点的层数分布几乎就决定了这个跳跃表的查找效率。我们知道层数最高为32层，那么会不会出现这种极端情况：表的节点逐层数递减？这样就会导致跳跃表查找时还是一个节点一个节点地查找，就失去了跳跃表提高查询效率的意义。

跳跃表各节点层数逐层递减图

2. 如果我们要查找的值为10000，然而跳跃表的分值范围是1-9999，这时候还会按一般逻辑查找吗？

二、解答

1. 我们知道，对于一个节点，创建它时生成的层数根据幂次定律来决定的。那么这个幂次定律又是如何保证它的表中的层数不会逐层递减呢？(请注意，幂次定律是一个理论，并不是代码)。

我找到了跳跃表创始人William Pugh的关于生成层数的代码。

randomLevel()

    lvl := 1

    -- random() that returns a random value in [0...1)

    while random() < p and lvl < MaxLevel do

        lvl := lvl + 1

        return lvl

从代码中可以看到，初始的层数lvl为1，当随机生成数小于概率p且层数小于最大层数时就可以加1层。

接下来再看看Redis源码中关于增加层数的代码。

int zslRandomLevel(void) {

     int level = 1;

     while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))

     level += 1;

     return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;

}

计算生成层数时，先初始化层数为1，再做一个判断(random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)，结果为true则层数增加1，最后返回层数。

random()方法返回[0,1)之间的数，ZSKIPLIST_MAXLEVEL值为最高层数32的值，ZSKIPLIST_P为概率1/4。ZSKIPLIST_P * 0xFFFF值很好理解，就是0.25*65535。random()&0xFFFF是一个小数与65535二进制形式的与操作，我还没能搞明白运算的结果。总之while判断条件的成立概率也为1/4。

节点层数恰好等于1的概率为1-p(p为1/4)。

节点层数恰好等于2的概率为(1-p)。

节点层数恰好等于3的概率为(1-p)。

节点层数恰好等于4的概率为(1-p)。

节点层数恰好等于n的概率为。

那么节点层数恰好等于32的概率为，这个值的分子是3，分母是（18,446,744,073,709,551,616），是个千亿亿级的数字，比中彩票的概率还小。

如果相邻节点要达到逐层递减，先不说从32层开始，就说从10层开始递减到1层，看看概率是多少。

*(*********

可以发现这个值的概率比节点层数恰好为32的概率还小得多。因为递减层数的每层的概率必须相乘。

所以，可以认为Redis跳跃表中层数不会出现多个node逐层递减的情况，如果是少数node有这种情况可以接受，也不会影响查询效率。

2. 如果查询的值不在Redis跳跃表的分值范围内怎么办呢？

Redis并没有机制使得在常数时间内返回不在分值范围内的结果(我并没有找到)，但是可以当作平常的查找就行了，以跳跃表的效率可以接受这样的结果。

个人建议：在zskiplist中有指针指向头节点和尾节点，可以根据头节点在常量时间内获取第一个节点的分值，也可以在常量时间内获取尾节点的分值。这样就可以在常量时间内知道要查找的值是否在zskiplist分值范围内。

                                                                                                                                        2019-06-30