redis-skiplist

为什么引出跳表

先从一个单链表来说对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高O(N)
痛点

解决方法：升维，也即空间换时间
优化
案例：画一个包含64个节点的链表，按前面思路，建立五级索引

是什么

跳表是可以实现二分查找的有序链表

skiplist是一种以空间换取时间的结构。由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点(索引)，先在关键节点上查找，再进入下层链表查找，提取多层关键节点，就形成了跳跃表。

但是，由于索引也要占据一定空间的，所以，索引添加的越多，空间占用的越多

总结来说，跳表=链表+多级索引

跳表时间和空间复杂度介绍

跳表的时间复杂度，O(logN)

跳表查询的时间复杂度分析，如果链表里有N个结点，会有多少级索引呢？

按照我们前面笔记，两两取首。每两个结点会抽出一个结点作为上一级索引的结点，以此估算:

第一级索引的结点个数大约就是n/2

第二级索引的结点个数大约就是n/4.

第三级索引的结点个数大约就是n/8，依次类推......

也就是说，第k级索引的结点个数是第k-1级索引的结点个数的1/2，那第k级索引结点的个数就是n/(2^k)

假设索引有h级，最高级的索引有2个结点。通过上面的公式，

我们可以得到n/(2^h)=2，从而求得h=log2n-1(log以2为底，n的对数)

如果包含原始链表这一层，整个跳表的高度就是log2n(log以2为底，n的对数)
跳表空间复杂度

跳表查询的空间复杂度分析

比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢?

我们来分析一下跳表的空间复杂度。

第一步：首先原始链表长度为n，

第二步：两两取首，每层索引的结点数: n/2,n/4,n/8 ...,8,4,2 每上升一级就减少一半，直到剩下2个结点,以此类推，如果我们把每层索引的结点数写出来，就是一个等比数列。

这几级索引的结点总和就是n/2+n/4+/8.+8+4+2=n-2。所以，跳表的空间复杂度是O(n)。也就是说，如果将包含n个结点的单链表构造成跳表，我们需要额外再用接近n个结点的存储空间。

同理，若三三取首，每层索引的节点数： n/3, n/9, n/27, ..., 9, 3, 1，以此类推：

第一级索引的结点个数大约就是n/3，第二级索引的节点个数大约就是n/9，第三级索引的结点个数大约就是n/27，每往上一级，索引节点个数都除以3，。为了方便计算，我们吧最高一级的索引节点个数视为1.我们把每级索引节点个数写出来，就是一个等比数列。

通过等比数列求和公式，总的索引大概是n/3+n/9+n/27+...+9+3+1=n/2。所以，三三取首的跳表的空间复杂度也是O(n),但是比上面两两取首的跳表，节省了一半的索引空间。

一般来说使用两两取首和三三取首就已经足够了，不需要再增加了。因为，如果我们继续增加，比如四四取首，五五取首，那空间复杂度就会越来越大，跳表的优势就没有那么明显了。