Redis内部数据结构详解——skiplist
Redis⾥⾯使⽤skiplist是为了实现sorted set这种对外的数据结构。sorted set提供的操作⾮常丰富，可以满⾜⾮常多的应⽤场景。这也意味着，sorted set相对来说实现⽐较复杂。同时，skiplist这种数据结构对于很多⼈来说都⽐较陌⽣，因为⼤部分学校⾥的算法课都没有对这种数据结构进⾏过详细的介绍。因此，为了介绍得⾜够清楚，本⽂会⽐这个系列的其它⼏篇花费更多的篇幅。
我们将⼤体分成三个部分进⾏介绍：
1. 介绍经典的skiplist数据结构，并进⾏简单的算法分析。这⼀部分的介绍，与Redis没有直接关系。我会尝试尽量使⽤通俗易懂的语⾔
进⾏描述。
2. 讨论Redis⾥的skiplist的具体实现。为了⽀持sorted set本⾝的⼀些要求，在经典的skiplist基础上，Redis⾥的相应实现做了若⼲改
动。
3. 讨论sorted set是如何在skiplist, dict和ziplist基础上构建起来的。
我们在讨论中还会涉及到两个Redis配置（在f中的ADVANCED CONFIG部分）：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
我们在讨论中会详细解释这两个配置的含义。
注：本⽂讨论的代码实现基于Redis源码的3.2分⽀。
skiplist数据结构简介
skiplist本质上也是⼀种查结构，⽤于解决算法中的查问题（Searching），即根据给定的key，快速查到它所在的位置（或者对应的value）。
我们在《Redis内部数据结构详解》系列的中介绍dict的时候，曾经讨论过：⼀般查问题的解法分为两个⼤类：⼀个是基于各种平衡树，⼀个是基于哈希表。但skiplist却⽐较特殊，它没法归属到这两⼤类⾥⾯。
这种数据结构是由发明的，最早出现于他在1990年发表的论⽂《》。对细节感兴趣的同学可以下载论⽂原⽂来阅读。
skiplist，顾名思义，⾸先它是⼀个list。实际上，它是在有序链表的基础上发展起来的。
我们先来看⼀个有序链表，如下图（最左侧的灰⾊节点表⽰⼀个空的头结点）：
在这样⼀个链表中，如果我们要查某个数据，那么需要从头开始逐个进⾏⽐较，直到到包含数据的那个节点，或者到第⼀个⽐给定数据⼤的节点为⽌（没到）。也就是说，时间复杂度为O(n)。同样，当我们要插⼊新数据的时候，也要经历同样的查过程，从⽽确定插⼊位置。
假如我们每相邻两个节点增加⼀个指针，让指针指向下下个节点，如下图：
这样所有新增加的指针连成了⼀个新的链表，但它包含的节点个数只有原来的⼀半（上图中是7, 19, 26）。现在当我们想查数据的时候，可以先沿着这个新链表进⾏查。当碰到⽐待查数据⼤的节点时，再回到原来的链表中进⾏查。⽐如，我们想查23，查的路径是沿着下图中标红的指针所指向的⽅向进⾏的：
23⾸先和7⽐较，再和19⽐较，⽐它们都⼤，继续向后⽐较。
但23和26⽐较的时候，⽐26要⼩，因此回到下⾯的链表（原链表），与22⽐较。
23⽐22要⼤，沿下⾯的指针继续向后和26⽐较。23⽐26⼩，说明待查数据23在原链表中不存在，⽽且它的插⼊位置应该在22和26之间。
在这个查过程中，由于新增加的指针，我们不再需要与链表中每个节点逐个进⾏⽐较了。需要⽐较的节点数⼤概只有原来的⼀半。
利⽤同样的⽅式，我们可以在上层新产⽣的链表上，继续为每相邻的两个节点增加⼀个指针，从⽽产⽣第三层链表。如下图：
在这个新的三层链表结构上，如果我们还是查23，那么沿着最上层链表⾸先要⽐较的是19，发现23⽐19⼤，接下来我们就知道只需要到19的后⾯去继续查，从⽽⼀下⼦跳过了19前⾯的所有节点。可以想象，当链表⾜够长的时候，这种多层链表的查⽅式能让我们跳过很多下层节点，⼤⼤加快查的速度。
skiplist正是受这种多层链表的想法的启发⽽设计出来的。实际上，按照上⾯⽣成链表的⽅式，上⾯每⼀层链表的节点个数，是下⾯⼀层的节点个数的⼀半，这样查过程就⾮常类似于⼀个⼆分查，使得查的时间复杂度可以降低到O(log n)。但是，这种⽅法在插⼊数据的时候有很⼤的问题。新插⼊⼀个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插⼊的节点后⾯的所有节点（也包括新插⼊的节点）重新进⾏调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。
skiplist为了避免这⼀问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，⽽是为每个节点随机出⼀个层数(level)。⽐如，⼀个节点随机出的层数是3，那么就把它链⼊到第1层到第3层这三层链表中。为了表达清楚，下图展⽰了如何通过⼀步步的插⼊操作从⽽形成⼀个skiplist的过程：
从上⾯skiplist的创建和插⼊过程可以看出，每⼀个节点的层数（level）是随机出来的，⽽且新插⼊⼀个节点不会影响其它节点的层数。因此，插⼊操作只需要修改插⼊节点前后的指针，⽽不需要对很多节点都进⾏调整。这就降低了插⼊操作的复杂度。实际上，这是skiplist的⼀个很重要的特性，这让它在插⼊性能上明显优于平衡树的⽅案。这在后⾯我们还会提到。
根据上图中的skiplist结构，我们很容易理解这种数据结构的名字的由来。skiplist，翻译成中⽂，可以翻译成“跳表”或“跳跃表”，指的就是除了最下⾯第1层链表之外，它会产⽣若⼲层稀疏的链表，这些链表⾥⾯的指针故意跳过了⼀些节点（⽽且越⾼层的链表跳过的节点越多）。这就使得我们在查数据的时候能够先在⾼层的链表中进⾏查，然后逐层降低，最终降到第1层链表来精确地确定数据位置。在这个过程中，我们跳过了⼀些节点，从⽽也就加快了查速度。
刚刚创建的这个skiplist总共包含4层链表，现在假设我们在它⾥⾯依然查23，下图给出了查路径：
需要注意的是，前⾯演⽰的各个节点的插⼊过程，实际上在插⼊之前也要先经历⼀个类似的查过程，在确定插⼊位置后，再完成插⼊操作。
⾄此，skiplist的查和插⼊操作，我们已经很清楚了。⽽删除操作与插⼊操作类似，我们也很容易想象出来。这些操作我们也应该能很容易地⽤代码实现出来。
当然，实际应⽤中的skiplist每个节点应该包含key和value两部分。前⾯的描述中我们没有具体区分key和value，但实际上列表中是按照key进⾏排序的，查过程也是根据key在⽐较。
但是，如果你是第⼀次接触skiplist，那么⼀定会产⽣⼀个疑问：节点插⼊时随机出⼀个层数，仅仅依靠这样⼀个简单的随机数操作⽽构建出来的多层链表结构，能保证它有⼀个良好的查性能吗？为了回答这个疑问，我们需要分析skiplist的统计性能。
在分析之前，我们还需要着重指出的是，执⾏插⼊操作时计算随机数的过程，是⼀个很关键的过程，它对skiplist的统计特性有着很重要的影响。这并不是⼀个普通的服从均匀分布的随机数，它的计算过程如下：
⾸先，每个节点肯定都有第1层指针（每个节点都在第1层链表⾥）。
如果⼀个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率
为p。
节点最⼤的层数不允许超过⼀个最⼤值，记为MaxLevel。
这个计算随机层数的伪码如下所⽰：
randomLevel()
level := 1
// random()返回⼀个[0...1)的随机数
while random() < p and level < MaxLevel do
redis八种数据结构level := level + 1
return level
randomLevel()的伪码中包含两个参数，⼀个是p，⼀个是MaxLevel。在Redis的skiplist实现中，这两个参数的取值为：
p = 1/4
MaxLevel = 32
skiplist的算法性能分析
在这⼀部分，我们来简单分析⼀下skiplist的时间复杂度和空间复杂度，以便对于skiplist的性能有⼀个直观的了解。如果你不是特别偏执于算法的性能分析，那么可以暂时跳过这⼀⼩节的内容。
我们先来计算⼀下每个节点所包含的平均指针数⽬（概率期望）。节点包含的指针数⽬，相当于这个算法在空间上的额外开销(overhead)，可以⽤来度量空间复杂度。
根据前⾯randomLevel()的伪码，我们很容易看出，产⽣越⾼的节点层数，概率越低。定量的分析如下：
节点层数⾄少为1。⽽⼤于1的节点层数，满⾜⼀个概率分布。
节点层数恰好等于1的概率为1-p。
节点层数⼤于等于2的概率为p，⽽节点层数恰好等于2的概率为p(1-p)。
节点层数⼤于等于3的概率为p2，⽽节点层数恰好等于3的概率为p2(1-p)。
节点层数⼤于等于4的概率为p3，⽽节点层数恰好等于4的概率为p3(1-p)。
……
因此，⼀个节点的平均层数（也即包含的平均指针数⽬），计算如下：
现在很容易计算出：
当p=1/2时，每个节点所包含的平均指针数⽬为2；
当p=1/4时，每个节点所包含的平均指针数⽬为1.33。这也是Redis⾥的skiplist实现在空间上的开销。
接下来，为了分析时间复杂度，我们计算⼀下skiplist的平均查长度。查长度指的是查路径上跨越的跳数，⽽查过程中的⽐较次数就等于查长度加1。以前⾯图中标出的查23的查路径为例，从左上⾓的头结点开始，⼀直到结点22，查长度为6。
为了计算查长度，这⾥我们需要利⽤⼀点⼩技巧。我们注意到，每个节点插⼊的时候，它的层数是
由随机函数randomLevel()计算出来的，⽽且随机的计算不依赖于其它节点，每次插⼊过程都是完全独⽴的。所以，从统计上来说，⼀个skiplist结构的形成与节点的插⼊顺序⽆关。
这样的话，为了计算查长度，我们可以将查过程倒过来看，从右下⽅第1层上最后到达的那个节点开始，沿着查路径向左向上回溯，类似于爬楼梯的过程。我们假设当回溯到某个节点的时候，它才被插⼊，这虽然相当于改变了节点的插⼊顺序，但从统计上不影响整个skiplist的形成结构。
现在假设我们从⼀个层数为i的节点x出发，需要向左向上攀爬k层。这时我们有两种可能：
如果节点x有第(i+1)层指针，那么我们需要向上⾛。这种情况概率为p。
如果节点x没有第(i+1)层指针，那么我们需要向左⾛。这种情况概率为(1-p)。
这两种情形如下图所⽰：