深入理解跳表及其在Redis中的应用( 四 ) _Redis

文章插图
1.ZSet中跳表的实现细节随机层数的实现原理：
跳表是一个概率型的数据结构，元素的插入层数是随机指定的。Willam Pugh在论文中描述了它的计算过程如下：指定节点最大层数 MaxLevel，指定概率 p，默认层数 lvl 为1；
生成一个0~1的随机数r，若r<p，且lvl<MaxLevel ，则lvl ++；
重复第 2 步，直至生成的r >p 为止，此时的 lvl 就是要插入的层数。
论文中生成随机层数的伪码：

文章插图
在Redis中对跳表的实现基本上也是遵循这个思想的，只不过有微小差异，看下Redis关于跳表层数的随机源码src/z_set.c：

/* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. */int zslRandomLevel(void) {int level = 1;while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;}

其中两个宏的定义在redis.h中：
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */#define ZSKIPLIST_P 0.25/* Skiplist P = 1/4 */可以看到while中的：
(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF)第一眼看到这个公式，因为涉及位运算有些诧异，需要研究一下Antirez为什么使用位运算来这么写？
最开始的猜测是random()返回的是浮点数[0-1]，于是乎在线找了个浮点数转二进制的工具，输入0.5看了下结果：

文章插图
可以看到0.5的32bit转换16进制结果为0x3f000000，如果与0xFFFF做与运算结果还是0，不符合预期。
实际应用时对于随机层数的实现并不统一，重要的是随机数的生成，在LevelDB中对跳表层数的生成代码是这样的：

template <typename Key, typename Value>int SkipList<Key, Value>::randomLevel() {static const unsigned int kBranching = 4;int height = 1;while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {height++;}assert(height > 0);assert(height <= kMaxLevel);return height;}uint32_t Next( uint32_t& seed) {seed = seed & 0x7fffffffu;if (seed == 0 || seed == 2147483647L) {seed = 1;}static const uint32_t M = 2147483647L;static const uint64_t A = 16807;uint64_t product = seed * A;seed = static_cast<uint32_t>((product >> 31) + (product & M));if (seed > M) {seed -= M;}return seed;}

可以看到leveldb使用随机数与kBranching取模，如果值为0就增加一层，这样虽然没有使用浮点数，但是也实现了概率平衡。
2.跳表结点的平均层数我们很容易看出，产生越高的节点层数出现概率越低，无论如何层数总是满足幂次定律越大的数出现的概率越小。

如果某件事的发生频率和它的某个属性成幂关系，那么这个频率就可以称之为符合幂次定律。
幂次定律的表现是少数几个事件的发生频率占了整个发生频率的大部分，而其余的大多数事件只占整个发生频率的一个小部分。

幂次定律应用到跳表的随机层数来说就是大部分的节点层数都是黄色部分，只有少数是绿色部分，并且概率很低。
定量的分析如下：
•节点层数至少为1，大于1的节点层数满足一个概率分布。
•节点层数恰好等于1的概率为p^0(1-p)
•节点层数恰好等于2的概率为p^1(1-p)
•节点层数恰好等于3的概率为p^2(1-p)
•节点层数恰好等于4的概率为p^3(1-p)
依次递推节点层数恰好等于K的概率为p^(k-1)(1-p)
因此如果我们要求节点的平均层数，那么也就转换成了求概率分布的期望问题了：

文章插图
??表中P为概率，V为对应取值，给出了所有取值和概率的可能，因此就可以求这个概率分布的期望了。方括号里面的式子其实就是高一年级学的等比数列，常用技巧错位相减求和，从中可以看到结点层数的期望值与1-p成反比。对于Redis而言，当p=0.25时结点层数的期望是1.33 。
总结跳表的时间复杂度与AVL树和红黑树相同，可以达到O(logN)，但是AVL树要维持高度的平衡，红黑树要维持高度的近似平衡，这都会导致插入或者删除节点时的一些时间开销，所以跳表相较于AVL树和红黑树来说，省去了维持高度的平衡的时间开销，但是相应的也付出了更多的空间来存储多个层的节点，所以跳表是用空间换时间的数据结构。以Redis中底层的数据结构zset作为典型应用来展开，进一步看到跳跃链表的实际应用。