前言这里我们先回忆一下普通链表的时间复杂度，可以看出除了查找操作是O(n)，其他操作都是O(1)时间复杂度。也就是说，如果你需要随机访问其中的任意一个元素，它的平均时间复杂度是O(n)，这就是链表的问题。由此可见，没有所谓完美的数据结构。如果完美的话，就不需要Array或者LinkedList这两种数据结构并存，直接使用最强大的数据结构即可。所以每个人都有自己的优点和缺点。这取决于你的使用场景在哪里。作为一个完整的比较，我将在这里列出两个时间复杂度。链表的时间复杂度数组的时间复杂度注：一般情况下，数组前置操作的时间复杂度为O(n)，但可以专门优化为O(1)。使用的方法是申请稍微大一点的内存空间，然后在数组开头预留一部分空间，然后prepend的操作就是把表头下标向前移动一个位置。跳跃表SkipList回顾了Array和LinkedList两种结构的时间复杂度。在一种情况下，链表的速度是O(n)，这是不够的。我们来看看这个情况指的是什么？链表元素有序的时候，注意整个元素。如果是有序的，有时候，比如在数据库中，或者在查询一些有序树的时候，即使是存储在链表中，我们发现它的元素是有序的。比如下面的升序链表中，134578910是升序排列的。这时候我们需要快速查询，比如9在哪里或者查询5，是否出现在这个链表中？这时候你会发现，如果用普通的数组进行二分查找，可以很快找到5的位置，并查看某个元素是否存在。有一个有序数组，那么问题来了，如果是有序的，但是在链表的情况下如何有效加速呢？所以在近代1990年左右，出现了一种新的数据结构。它的名字叫做跳表。跳表的特点注意事项：只能在元素有序的情况下使用。因此，跳跃表（skiplist）是一种平衡树（AVLTree）和二分查找，是一种插入/删除/查找复杂度为O(logn)的数据结构。1989年出现。不管是平衡树，二叉查找树，还是其他什么树，都是在1960年和196年出现的，比平衡树，二分查找，以及一些所谓的高级数据结构的出现要晚。比其他人晚了将近30年，终于出现了。这也是为什么很多老的数据结构使用平衡二叉树的多一点，而一些新的，尤其是在元素数量不多的情况下，用的都是跳表，也就是更新的意思。它最大的优点是原理简单，易于实现，易于扩展，效率更高。因此，在一些流行的项目中，如Redis、LevelDB等，用它来代替平衡树。跳表（skiplist）是一种随机数据，由WilliamPugh在论文《Skip lists: a probabilistic alternative to balanced trees》中提出，跳表将元素保存在有序的层次链表，其效率可与平衡树相媲美——查找、删除、添加等操作可以在对数期望时间内完成，与平衡树相比，跳表的实现更简单，更直观。如何对一个有序链表进行加??速假设有一个有序链表，134578910这样一个原始链表。它的时间复杂度查询肯定是O(n)，那怎么优化呢？如何进行简单的优化？它可以使它的查询时间复杂度更低，也就是加快它的查询速度。我们可以想一想，如果你来了，比如说我想快速的找到7，它存在于链表中吗，它在哪里，你能不能很快的查询出来呢？时间复杂度：查询O(n)简单优化：在头尾指针上面加这样一个结构，它是一个一维的数据结构，现在是有序的，也就是说我们有了额外的信息，那么如何加快速度，对吧？总的来说，这种提速的方法类似于星际穿越中的玄学，但是一定要记住一个概念。如果一维数据结构需要加速，常用的方法是增加维度，也就是变成二维的。为什么要多一个维度，因为多了一个维度之后，里面就会多一层信息，这样多一层信息可以帮助你快速得到一个维度，你得一层一层去go如何给元素加上一级索引，提高链表线性查找的效率？具体的，我们看上图。在原有链表的情况下，我们再增加一个维度，即在其上再增加一层索引。我们称它为一级索引，那么一级索引并不是指向它的元素的下一个元素，而是指向它的nextnext，也就是说你可以理解为next+1，所以第一个级索引是第一个元素，紧接着是第三个元素，第五个元素，第七个元素。这里你会发现，如果要找到7，我们应该怎么做呢？我们这样查找，先查找一级索引，看是否有147，如果有，说明这个链表中存在7，说明我们查询到了。我们再看看另一个元素，比如8，我们怎么走？还是先找第一层，8大于1，所以后面达到4索引的值，8大于4，继续下7和8也大于7，再继续找9大于8，说明在7和9这两个索引之间的元素中存在8，那么此时从一级元素往下到原链表，从对应的链表中逐一找到8位置。8也存在。如果加上二级索引，有些朋友可能会认为，如果加上一级索引，就相当于每次都在pace上加2，只是速度比之前稍微快了一些。能不能快点？？这个想法很合理，对你也有好处。然后在一级指标的基础上，再增加一个指标。也就是说，可以得出同样的道理。我们在一级索引的基础上，把它当成一个原始链表，再增加一个Level索引，也就是每次对一级索引走两步。那么就相当于原来的链表，相当于每次走四步。对，乘以2就好了，这样的话，速度会更有效率。比如我举个例子，搜索8，先找到1，8大于1，然后搜索7，然后你会发现8也大于7，再搜索，假设单词这个元素后面是11或者12，这时候你会发现8比它后面的元素小，所以这里如果是7，就必须往下一级索引，到第一级索引的7，并且然后就和之前7到9之间的那个差不多了，然后走到8就这样往下走。添加多级索引等等，添加多级索引假设有这样一个原始链表，它有一个五级索引，那么我们需要检查一个元素，比如要检查62个元素或者中间元素，类似下图，一层一层往下走，最后，我们就可以找到我们需要的62号元素了。当然，如果你最后找到原始链表，你会发现，比如我们要查63或者61，如果原始链表中没有元素，我们就会说元素不存在，而且是在我们的有序链表中，也就是在跳表中。如果找不到这样的元素，那么最后可以得出这样的结论。跳表查询时间复杂度分析跳表n/2、n/4、n/8的时间复杂度计算，k级索引节点个数为n/(2^k)假设索引有h级，最高级别索引有2个节点。n/(2^h)=2，从而得到h=log2(n)-1举个例子，在查询跳表的时候，假设索引的高度：logn，每次遍历的节点数indexlayer:3，假设去到第8个节点。每层一共要遍历3个元素，所以这里如果用log28就是它的时间复杂度。最后一句话可以证明：时间复杂度是log2n。即从最简单的原始链表，将其O(n)时间复杂度降为log2n时间复杂度。这已经是很大的进步了。假设是1024，你会发现原来的链表需要查找1024次才能最终得到这个元素，所以这里只需要查（2的10次方就是1024次）十次这个数量级。现实中跳表的形式在现实中使用跳表的情况下，会因为这个元素的增删而导致它的索引。有些数字并不是完全整齐的，最后经过多次修改最终它的最终索引有的地方会走几步，有的地方只有两步。这是因为它里面有些元素会被增删改查，它的维护成本比较高，也就是说当你添加一个元素的时候，你需要更新它的索引。如果要删除一个元素，还需要更新它的索引。如果在这个过程中是增删改查，那么它的时间复杂度就会变成O(logn)。跳表查询任意数据的平均时间复杂度为O(logn)。这里skiptablequery的空间??复杂度分析，我们假设它的长度是n，那么根据前面的例子，如果每两个节点都被选中做一个索引，那么它的主索引就是n/half，对吧？.最终如下：原链表大小为n，每2个节点选取一个，每层索引节点数：n2,n4,n8...,8,4,2原链表大小为n，每3个节点取1个，每个索引的节点数：n3,n9,n27...,9,3,1空间复杂度为O(n)的组成跳表如下：已知跳表主要由以下部分组成：表头（head）：负责维护跳表的节点指针。跳表节点：保存元素值和多层。层：保存指向其他元素的指针。高级指针传递的元素个数大于等于低级指针。为了提高查找效率，程序总是从高层开始访问，然后随着元素取值范围的缩小逐渐降低层级。Endoftable：全部由NULL组成，表示跳表结束。Redis跳跃列表的实现Redis跳跃列表由两个结构定义：redis.h/zskiplistNode和redis.h/zskiplist。zskiplistNode结构体用于表示跳跃表节点，而zskiplist结构体用于存储跳跃表节点的相关信息。比如节点的个数，指向头节点和尾节点的指针等等。上图显示了跳过列表的示例。图片最左边的zskiplist结构包含如下属性：header：指向skiplist的头节点。tail：指向跳转列表的尾节点。level：记录当前跳表中level最大的节点的level（header节点的level不算在内）。length：记录跳表的长度，即跳表当前包含的节点数（头节点不算）。位于zskiplist结构右侧的是4个zskiplistNode结构，包含以下属性：Level：节点的每一层都标有L1、L2、L3等，L1代表第一层，L2代表第二层，等等。每层都有两个属性：前向指针和跨度。前向指针用于访问表尾方向的其他节点，span记录前向指针指向的节点到当前节点的距离。上图中，导线上带有数字的箭头代表前向指针，这个数字就是跨度。当程序从表头遍历表尾时，会沿着层的前向指针进行访问。后向指针：节点中标有BW的节点的后向指针，指向位于当前节点的前一个节点。当程序从链表的尾部遍历到链表的头部时，会用到后向指针。score：每个节点中的1.0、2.0、3.0是该节点保存的分数。在跳表中，节点按照保存的分数升序排列。成员对象（obj）：每个节点中的o1、o2、o3是该节点保存的成员对象。注：header节点的结构和其他节点一样：header节点也有backpointer、score和member对象，但是不会用到header节点的这些属性，所以这些部分省略了图中，只展示了表头节点的各个层。跳表节点的实现由redis.h/zskiplistNode结构定义：typedefstructzskiplistNode{//backwardpointerstructzskiplistNode*backward;//scoredoublescore;//memberobjectrobj*obj;//layerstructzskiplistLevel{//forwardpointerstructzskiplistNode*forward;//spanunsignedintspan;}level[];}zskiplistNode;layerskiplist节点的level数组可以包含多个元素，每个元素包含一个指向其他节点的指针，程序可以利用这些层来加快访问其他节点的速度，一般来说，层数越高，更快地访问其他节点。每创建一个新的跳表节点，程序根据幂律（幂律，数字越大，出现的概率越小）随机生成一个1到32之间的值作为层次数组的大小。大小是层的“高度”。下图展示了三个高度分别为1层、3层和5层的节点，因为C语言的数组索引总是从0开始，所以节点的第一层是level[0]，第二层是level[1]等。前向指针每一层都有一个指向链表尾部的前向指针（level[i].forward属性），用于访问从链表头部到链表尾部的节点。上图虚线表示程序从头到尾遍历跳表中所有节点的路径：迭代程序先访问跳表的第一个节点（头），然后从第四层的前向指针开始移动到表中的第二个节点。在第二个节点，程序沿着二级前向指针移动到列表中的第三个节点。在第三个节点，程序也沿着二级前向指针移动到表中的第四个节点。当程序再次沿着第四个结点的前向指针移动时，遇到了NULL，程序知道此时已经到达了跳表的末尾，于是结束本次遍历。span层的span（level[i].span属性）用于记录两个节点之间的距离：两个节点之间的span越大，说明它们之间的距离越远。所有指向NULL的前向指针的步幅为0，因为它们没有连接到任何节点。乍一看，很容易认为跨度与遍历操作有关，但事实并非如此——仅使用前向指针即可完成遍历操作，而跨度实际上是用来计算秩的：结点过程，将沿途访问的所有层的span累加起来，得到的结果就是目标结点在跳表中的排名。例如在跳表中搜索得分为3.0且成员对象为o3的节点时，沿途遍历的层用虚线标记如下：搜索过程只经过一层，跨度layer的为3，所以target节点在跳转列表中的rank为3。再比如，虚线标记了搜索得分为2.0的节点和o2的成员对象时沿途的层数在跳表中：程序在查找节点的过程中，经过了两个跨度为1的节点，因此可以计算出目标节点在跳表中的rank为2。向后指针（backward后向指针节点的属性）用于访问链表尾部到链表头的节点：它不同于前向指针可以一次跳过多个节点，因为每个节点只有一个后向指针，所以每次只能倒退到前一个节点。上面的虚线表示如何从尾向头遍历跳转链表中的所有节点：程序先通过跳转链表的尾指针访问尾节点，然后通过后指针访问倒数第二个节点，然后沿着指针往回走，访问倒数第三个节点，然后遇到一个指向NULL的往回指针，于是访问结束。score和member节点的score（score属性）是一个double类型的浮点数，跳转列表中的所有节点按照score从小到大排序。一个节点的成员对象（obj属性）是一个指针，指向一个字符串对象，字符串对象持有一个SDS（simpledynamicstring）值。在同一个跳表中，每个节点保存的成员对象必须是唯一的，但多个节点保存的分数可以相同：分数相同的节点将按照成员对象的字典序大小进行排序，具有较小成员对象的节点将排列在前面（朝向列表的头部），而具有较大成员对象的节点将排列在后面（朝向列表的末尾）。例如下图所示的跳表，三个跳表节点都存储了相同的score值10086.0，但是存储成员对象o1的节点排在存储成员对象o2和o3的节点之前，而存储成员对象o2和o3的节点成员对象对象o2的节点位于存储成员对象o3的节点之前。可以看出，o1、o2、o3这三个成员对象在字典中的顺序是o1<=o2<=o3。虽然一个跳转表可以由多个跳转表节点组成，如下图所示：但是通过使用一个zskiplist结构来保存这些节点，程序可以更方便的处理整个跳转表，比如快速访问跳转表头表的节点和尾节点，或者快速获取跳表节点个数（即跳表长度）等信息，如下图：zskiplist结构体定义如下：typedefstructzskiplist{//表头节点和表尾节点structzskiplistNode*header,*tail;//表中的节点数unsignedlonglength;//层数最多的节点的层数intlevel;}zskiplist;Header和tail指针分别指向skiplist的header和tailNode，通过这两个指针，程序定位头节点和尾节点的复杂度为O(1)。通过使用length属性记录节点数，程序可以在O(1)的复杂度内返回跳表的长度。level属性用于在O(1)复杂度内获取跳表中层高最高的节点的层数。请注意，不包括头节点的层高。SkipTableAPI列出了skiptable的所有操作API。专访：为什么redis使用skiplist而不是红黑？skiplist的复杂度和红黑树一样，实现起来更简单。Skiplist在并发环境中还有另一个优势。红黑树在插入和删除的时候可能需要做一些rebalance操作。这样的操作可能会涉及整棵树的其他部分，而skiplist操作显然更局部化。需要挂钩的节点更少，因此在这种情况下性能更好。附：开发商为什么选择skiplist？Redis的跳表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于存储跳表信息（如头节点、尾节点、长度），zskiplistNode用于表示跳表节点。每个跳表节点的层高是1到32之间的随机数。在同一个跳表中，多个节点可以包含相同的分数，但每个节点的成员对象必须是唯一的。跳转列表中的节点按照分数的大小排序，当分数相同时，节点按照成员对象的大小排序。参考跳过列表：http://redisbook.com/preview/skiplist/datastruct.html
