redis 跳跃表-蒲公英云

跳跃表

跳跃表是有序集合的底层实现之一，除此之外它在 Redis 中没有其他应用。
Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成，其中 zskiplist 用于保存跳跃表信息（比如表头节点、表尾节点、长度），而 zskiplistNode 则用于表示跳跃表节点。
每个跳跃表节点的层高都是 1 至 32 之间的随机数。
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

跳跃表是一种随机化的数据，由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出，这种数据结构以有序的方式在层次化的链表中保存元素，它的效率可以和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。

跳跃表（维基百科）：

从图中可以看到，跳跃表主要由以下部分构成：

表头（head）：负责维护跳跃表的节点指针。
跳跃表节点：保存着元素值，以及多个层。
层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
表尾：全部由
允许重复的 member 的 score 值，还要检查 score 值可以重复时，单靠 member 域都一并检查才行。
每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代：当执行 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到这个属性。

这个修改版的跳跃表由 redis.h/zskiplistNode 定义：

typedef  struct zskiplistNode \{  
     //  member 对象   
    robj \*obj;  
     //  分值   
     double score;  
     //  后退指针   
     struct zskiplistNode \*backward;  
     //  层   
     struct zskiplistLevel \{  
         //  前进指针   
         struct zskiplistNode \*forward;  
         //  这个层跨越的节点数量   
        unsigned  int span;  
    \} level\[\];  
\} zskiplistNode;
以下是操作这两个数据结构的 API ，它们的作用以及相应的算法复杂度：
<table style="border:0px; border-collapse:collapse"> 
 <thead> 
  <tr> 
   <th style="padding:1px 8px 1px 5px; border-width:0px 0px 1px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 函数</th> 
   <th style="padding:1px 8px 1px 5px; border-width:0px 0px 1px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 作用</th> 
   <th style="padding:1px 8px 1px 5px; border-width:0px 0px 1px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> zslFreeNode</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 释放给定的跳跃表节点</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 最坏&nbsp;<span style="display:inline; font-size:16px; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; border:0px; padding:0px; margin:0px"> <span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:43px; height:0px; font-size:21px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-46px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math"><em>O<span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">1</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></em></span></span></span></span></span> </span></td> 
  </tr> 
  <tr> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> zslFree</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 释放给定的跳跃表</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 最坏&nbsp;<span style="display:inline; font-size:16px; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; border:0px; padding:0px; margin:0px"> <span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:51px; height:0px; font-size:21px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-46px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math"><em>O<span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px">N</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></em></span></span></span></span></span> </span></td> 
  </tr> 
  <tr> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> score&nbsp;和&nbsp;zslDeleteNode</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 删除给定的跳跃表节点</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 最坏&nbsp;<span style="display:inline; font-size:16px; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; border:0px; padding:0px; margin:0px"> <span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:51px; height:0px; font-size:21px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-46px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math"><em>O<span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px">N</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></em></span></span></span></span></span> </span></td> 
  </tr> 
  <tr> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> member&nbsp;和&nbsp;zslFirstInRange</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 找到跳跃表中第一个符合给定范围的元素</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 最坏&nbsp;<span style="display:inline; font-size:16px; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; border:0px; padding:0px; margin:0px"> <span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:51px; height:0px; font-size:21px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-46px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math"><em>O<span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px">N</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></em></span></span></span></span></span> </span>&nbsp;平均&nbsp;<span style="display:inline; font-size:16px; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; border:0px; padding:0px; margin:0px"> <span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:82px; height:0px; font-size:21px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-46px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math"><em>O<span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">log</span><span style="display:inline; position:static; border:0px; padding:0px 0px 0px 3.5px; margin:0px; vertical-align:0px">N</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></em></span></span></span></span></span> </span></td> 
  </tr> 
  <tr> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> zslDeleteRangeByScore</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 删除&nbsp;zslDeleteRangeByRank</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 删除给定排序范围内的所有节点</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 最坏&nbsp;<span style="display:inline; font-size:16px; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; border:0px; padding:0px; margin:0px"> <span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:63px; height:0px; font-size:21px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-46px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math; font-style:italic">O<span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:30.1px; height:0px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-42px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px">N</span></span><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-47.5px; left:20.6px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-size:15px; font-family:MathJax_Main">2</span></span></span></span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></span></span></span></span></span> </span></td> 
  </tr> 
  <tr> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> zslGetElementByRank</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 根据给定排位，返回该排位上的元素节点</td> 
   <td style="padding:1px 8px 1px 5px; border-top-width:0px; border-right-width:0px; border-left-width:0px; border-bottom-style:solid; border-bottom-color:rgb(170,170,170)"> 最坏&nbsp;<span style="display:inline; font-size:16px; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; border:0px; padding:0px; margin:0px"> <span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:51px; height:0px; font-size:21px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-46px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math"><em>O<span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px">N</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></em></span></span></span></span></span> </span>&nbsp;平均&nbsp;<span style="display:inline; font-size:16px; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; border:0px; padding:0px; margin:0px"> <span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:82px; height:0px; font-size:21px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-46px; left:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math"><em>O<span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">log</span><span style="display:inline; position:static; border:0px; padding:0px 0px 0px 3.5px; margin:0px; vertical-align:0px">N</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></em></span></span></span></span></span> </span></td> 
  </tr> 
 </tbody> 
</table>
##  ##
## 跳跃表的应用 ##
和字典、链表或者字符串这几种在 Redis 中大量使用的数据结构不同， 跳跃表在 Redis 的唯一作用， 就是实现有序集数据类型。
跳跃表将指向有序集的 member 域的指针作为元素， 并以 score 值为索引， 对有序集元素进行排序。
举个例子， 以下代码就创建了一个带有 3 个元素的有序集：

redis> ZADD s 6 x 10 y 15 z
(integer) 3

redis> ZRANGE s 0 -1 WITHSCORES
1) “x”
2) “6”
3) “y”
4) “10”
5) “z”
6) “15”

在底层实现中， Redis 为 y 和 member 分别创建了三个字符串，并为 10 和 double 类型的值，然后用一个跳跃表将这些指针有序地保存起来，形成这样一个跳跃表：

为了展示的方便，在图片中我们直接将 score 值包含在表节点中，但是在实际的定义中，因为跳跃表要和另一个实现有序集的结构（字典）分享 score 值，所以跳跃表只保存指向 score 的指针。更详细的信息，请参考《有序集》章节。

小结

跳跃表是一种随机化数据结构，它的查找、添加、删除操作都可以在对数期望时间下完成。
跳跃表目前在 Redis 的唯一作用就是作为有序集类型的底层数据结构（之一，另一个构成有序集的结构是字典）。
为了适应自身的需求，Redis 基于 William Pugh 论文中描述的跳跃表进行了修改，包括：
1. score 和 memeber 。
2. 每个节点带有高度为 1 层的后退指针，用于从表尾方向向表头方向迭代。