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

2019-06-30 本文已影响0人 Vic_is_new_Here

一、问题

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的概率为 $p$ (1-p)。