本文转载自微信公众号《后端技术罗盘》，作者大白鸡。转载本文请联系后台技术指南针公众号。跳转链表及其应用是非常热门的问题。对其中的奥秘有深入的了解，是非常有益的。不吹牛了，让我们开始品尝这美味的知识吧！跳转链表的基本概念。它允许快速查询有序连续元素的数据链表。跳转列表的平均查找和插入时间复杂度为O(logn)，优于普通队列的O(n)。跳表是WilliamPu发明的，发明人对跳表的评价：跳表是一种数据结构，在很多应用中有可能取代平衡树作为一种实现方式。跳跃列表的算法与平衡树具有相同的渐近预期时间界限，并且更简单、更快并且使用更少的空间。这种数据结构是由WilliamPugh（音译为WilliamPugh）发明的，最早出现在他1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中。大白在Google上找到了一篇关于skiplist的作者论文。如果有兴趣，强烈推荐下载阅读：https://epaperpress.com/sortsearch/download/skiplist.pdf查看这篇论文的摘要：Whatwegotfromit信息是：skiptable使用动态查找过程中的非严格平衡机制，使插入和删除更方便快捷。这种非严格平衡是基于概率的，而不是平衡树的严格平衡。说到非严格平衡，第一个想到的就是红黑树RbTree。它还使用非严格平衡来避免像AVL那样调整树结构。红黑树这里就不说了。好像跳表也是类似的方式。但这是基于概率的。动态搜索的数据结构所谓动态搜索就是在搜索过程中对元素进行删除和插入，这对搜索数据结构的实现提出了一定的挑战，因为每次删除和插入都要调整数据结构插入维持秩序。可以作为搜索的数据结构包括：线性结构：数组、链表非线性结构：平衡树下面分析一下各种数据结构应对动态搜索的优缺点吧！数组结构数组结构简单，在内存中连续，可以实现二分查找等。基于下标的操作，我一直认为数组的杀手锏是下标，连续内存也带来了问题。插入和删除时，会面临整体调整，就像在火车站排队买票一样，排在前面的向前一步，排在后面的整体后退一步。这种整体移动操作在数组结构中性能损耗非常高，在数据量大的时候对连续内存的要求非常高。当然，这在大内存机器上可能不是问题。如图，插入6和删除5时数组元素的移动：链表结构链表结构也比较简单，但是不需要连续的内存，不连续的话就没有下标可以加快速度，但是链表只在执行删除和插入时影响插入和删除。点前后的元素，影响很小。但是每次查找一个元素，都需要遍历它。即使知道某个元素的大概位置，也只能一步步走过去。如果你看到有优化的空间，那你就相当厉害了。假设跳表是你几年前的发明。删除第5个元素，插入第49个元素时的处理如图所示：Balancedtree平衡树也是处理动态搜索问题的一把好手。树一般是基于链表实现的，但是树的节点并不是链表的简单线性关系。会有兄弟、姐妹、父亲等节点，每一层都有人数限制。可见这棵树其实还是挺复杂的。一个节点需要存储很多信息，每个指针都来回指向。复杂的结构增加了调整平衡的难度。在不同的情况下，左撇子和右撇子，所以有红黑树之类的工程版AVL，但是在实际场景中可能不需要这些兄弟姐妹和爸爸的关系电影，杀鸡取牛刀的感觉。红黑树节点结构定义：#defineCOLOR_RED0x0#defineCOLOR_BLACK0x1typedefstructRBNode{intkey;unsignedcharcolor;structRBNode*left;structRBNode*right;structRBNode*parent;}rb_node_t,*rb_tree_t;另外，红黑树在调整属性的时候分为三种情况。deletion分为4种情况，比较难理解，除非你穿着红衬衫黑裤子疯狂暗示面试官，否则被问到的概率不会太高。三种结构的比较从上面的比较可以看出，数组并没有很好地满足要求，链表在查找过程中比较笨拙，平衡树有点复杂。我应该怎么办？有一些问题，需要改造。可以看到数组和平衡树的一些特性决定了它们不容易被转化（数组内存连续性、平衡树节点多指针和层级关系），相反链表最有转化优化的潜力.在有序链表中插入和删除相对简单。查找的时候不能靠下标，只能遍历，但是知道要走两步才能到达目的地，但是每次只能走一步。这就是痛点。图中演示了O(n)遍历第35个元素跳转到搜索第35个元素的过程：看来我们看到了曙光，那么如何实现跳转呢？这是正确的！给链表加一个索引，让索引告诉我们下一步要跳转到哪里。看到这里让我想起了经典的中间层理论。遇到问题，试试加个中间层，说不定就能完美解决。跳转链表的实现原理前面已经讲到，可以通过在普通链表上加一个索引来解决，但是具体怎么做，有什么难点呢？我们一步一步来分析。在项目中，跳表的索引层数和节点是否作为索引节点是非常重要的属性。后面我会详细讲。下面我们通过一个简单的场景来说明索引带来的便利。简单索引选取每隔一个节点作为索引节点，索引为一层。这种形式虽然在工程上比较规范，但足以说明指数带来的加速。可以在链表中的偶数节点添加一层指针指向下一个偶数节点，如图：查找过程：添加一个值为55的节点进行查找，并在上查找先上层，从16跳到38，下一跳38会到72，继续往下一层类似查找，找到55。当多级索引是基于偶数节点时，只有两个层，最高层的节点数为n/2。总的来说，搜索复杂度降低到O(n/2)。不要小看这个1/2的系数，看到这里会想把索引层数增加到k，那么复杂度就会降低到O(n/2^k)。索引层数不会无限增加，它取决于该层索引的节点数。如果这一层索引的节点数等于2，那么再往上加层就没有意义了。画个图看看：这个很容易理解，如果层中只有一个索引节点，比如4层索引的节点16，只能向下遍历16，不能跳回其他第4层的节点，所以当该层的索引节点数等于2时，到达最高索引层。这个约束在分析跳表的复杂度时非常重要。索引层数和索引节点的密度跳表的复杂度与索引层数和索引节点的稀疏度有很大关系。从上面我们也看到，索引层数等于索引节点数的比值。如果跳表的索引节点数少，则接近于退化为普通链表。这种情况，当数据量大的时候就很明显了，我们画一张图（蓝色部分代表节点多）：图中，虽然有索引层，但是索引节点数量比较少与总数据相比。在这种情况下，将搜索35与没有索引的情况进行比较。优势不明显。因此，跳表的效率与索引层数和索引节点密度密切相关。当然，索引节点太多就意味着没有索引。索引节点太少和索引节点太多一样效率低下。复杂度分析从前面的分析可以看出，跳表的复杂度与索引层数m和索引节点间隙d直接相关，其中索引节点间隙理解为索引节点相隔几个节点出现，反映了对应层索引节点的稀疏性，当没有索引节点时，只能遍历不能跳转。如何确定最高索引层数m？如果一个链表有n个节点，如果每取出两个节点建立一个索引，那么一级索引的节点数为n/2，二级索引的节点数为n/2points是n/4，依此类推。m级索引的节点数为n/(2^m)。前面说到最高层的节点个数为2，所以有一个关系：算上最底层的原始链表，整个跳转链表的高度为h=logn（底为2），个数每层需要遍历的节点个数为d，则整个过程的复杂度为：O(d*logn)。d表示层间节点的稀疏性，即每2个节点选择索引节点，或者每3个节点选择索引节点，每4个节点选择索引节点......在最密集的情况下，d=2、借用大佬文章中的一张图：但是索引节点的密度也意味着存储空间的增加。与普通链表相比，跳表是典型的以空间换取时间结构的数据，从而达到AVL的复杂度O(logn)。跳表的空间存储以d=2最密集的情况为例，计算跳表的索引节点总数：2+4+8+...n/8+n/4+n/2=n-2从几何级数求和公式看，d=2跳表的额外空间为O(n-2)。跳表的插入和删除项目中的跳表并没有严格要求索引层的节点数遵循2:1的关系，因为这个要求会导致在插入和删除数据时进行调整，代价会很大.每个跳表插入节点时，选择是否为索引节点。如果是索引节点，层数会随机生成。整个过程是基于概率的，但是可以解决索引层数和节点数之间的权衡问题。下面就来看看插入删除的基本操作流程吧！跳表元素17插入：链表的插入和删除是配合查找过程完成的。贴一篇WilliamPugh的论文在跳表中插入元素17（暂且忽略节点17是否为索引节点和索引层数，后面会详细说明）：Skiplistelement1deletion：与普通链表相比，跳跃表元素的删除增加了索引层的判断。如果该节点是非索引节点，则正常处理。如果该节点是索引节点，则需要处理索引层节点。讨论跳跃链表的应用，讨论搜索问题首先想到的是平衡树和哈希表，但是跳跃链表的数据结构也很犀利，其性能和实现复杂度可以和红黑树。1990年发明的黑树，现在广泛应用于各种场景，包括Redis、LevelDB等数据存储引擎，后面会详细介绍。跳表在Redis中的应用ZSet结构中同时包含字典和跳表。跳表按分数从小到大保存所有集合元素。字典保存从成员到分数的映射。这两个结构体通过指针共享同一个元素的member和score，不会浪费额外的内存。typedefstructzset{dict*dict;zskiplist*zsl;}zset;ZSet中的Dictionaryandskiplistlayout:ZSet中skiplist的实现细节随机层数的实现原理Skiplist是一种概率数据结构，元素插入的层数为随机分配。WilliamPugh在论文中描述其计算过程如下：指定节点的最大层数MaxLevel，指定概率p，默认层数lvl为1生成一个从0到1的随机数r。如果r重复步骤2直到生成r>p，此时的lvl就是要插入的层数。论文中生成随机层的伪代码：Redis中跳转表的实现基本遵循了这个思路，但是有细微的差别。关于跳表的层数见Redis的随机源码src/z_set.c：/*Returnssarandomlevelforthenewskiplistnodewearegoingtocreate.*Returnvalueofthisfunctionisbetween1andZSKIPLIST_MAXLEVEL*(bothinclusive),withapowerlaw-alikedistributionwherehigher*levelsarelesslikelytobereturn.*/intzslRandomLevel(void){intlevel=1;while((random()&0xFFFF)<(ZSKIPLIST_P*0xFFFF))level+=1;return(level
