在redis的zset（有序集合）数据类型中，它有两种实现方式：跳表和压缩列表；
这里介绍跳表；（跳表在我的理解就是空间换时间的方法，存储更多的结点信息，以此来换取更快的查询时间。有点类似于二分查找）

跳表

跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)

对于单个有序列表链表来说，我们要在其中查找数据，只能从头开始遍历查找，这样的时间复杂度是O(n)，效率很低。
假如我们需要找结点6，那么就必须遍历1 2 3 4 5 6,六个结点才能找到它

image.png

如果我们想要提高其查询效率，可以考虑在链表上构建索引的方式，每两个节点提取一个节点到上级，我们把抽出来的那一级就叫做索引.
找结点6：首先遍历L1这层，1 3 5 7，遍历5 和7的时候发现 5 < 6 < 7;
那么进入下一层寻找，直接就能找到6。这样只遍历了5个结点就找到了它。

image.png

我们还可以添加多级索引，当数据量很大的时候，我们的查询效率就会显著提升。

image.png

跳表的时空复杂度分析

时间复杂度

如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的结点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)。

假如一共有 m 级索引，第 m 级的结点数为两个，通过上边我们找到的规律，那么得出 n/(2^m)=2，从而求得 m=log(n)-1。如果加上原始链表，那么整个跳表的高度就是 log(n)。

如果每层需要遍历k个结点，那么我们的时间复杂度就是k*log(n);
其实仔细分析就不难发现，由于我们是每两个结点就提出一个结点上去，（1 3 5就会将1 5提到上一层索引中，没有提出去的数字就是他们的中间数），那么这样就可以看出没层其实只需要遍历两个结点，k就等于2。

最终时间复杂度：2*log(n) ==> log(n)

空间复杂度

如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的结点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)，我们可以看出来这是一个等比数列。
总和就是 n/2+n/4+n/8…+8+4+2=n-2，所以跳表的空间复杂度为 o(n)。

参考