就是单链表的查找的时间复杂度为O(N)，为了提高查询效率，可增加一些索引节点，让查询时间复杂度降低为O(logN)。（只有底层单链表会保存节点数据，上层的节点之后保存几个索引项和分数，也就是向左指向前一个节点的索引，向右指向后一个节点的索引，向下指向上一级的索引。）
时间复杂度的推理过程可以认为，从每一级索引中两个节点中选一个节点作为下一级索引的节点，让下一级索引的节点数量为本级索引节点数量的一半。假设原始链表的长度为n，第一级索引节点个数为n/2,第二级为n/4，一直到最高层。
假设h为层数，f(h)为该层索引节点数量。 f(h)=n/(2^h) 而最高层的索引节点会是只有两个索引节点。 也就是f(maxH)=n/(2^maxH)=2，所以最大层数maxH= log(n) - 1层 ，加上单链表的层数，总层数也就是log(n)层。 例如我们的单链表是1-19的，建立的多层索引如下， 如果我们要查找19，一开始在第四层遍历1，发现19>1,向右走，发现19>9,那么需要到上一级索引去找，然后发现19>13，继续到下一层，一直到第一层，发现19>17，然后往右走遍历17，18，19 所以每一层遍历的节点其实是 1 9 9 13 13 15 17 17 18 19 所以每一层最多遍历的节点数是<=3,这是由于每一层索引节点数是上一层的节点数的一半来得到的，每两个节点的区间，在上一层中都是两个区间，就是第三层的 1 5区间对应上一层的1 3 区间和3 5 区间。 所以时间复杂度=总层数*每层遍历节点数=3logN,去掉常数后是log(N) 第四层 1 9 第三层 1 5 9 13 第二层 1 3 5 7 9 11 13 15 17 第一层 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
但是这种全索引的结构有缺点，就是之后在插入新节点时，是没有办法为新节点添加一些新的索引节点的。所以有可能会导致一个小区间内有很多个节点，查找时近似于单链表，这样时间复杂度就变成O(N)了，所以Redis对跳跃表做了一些优化，可以简单认为会计算出一个随机数，代表这个添加添加的索引层数，然后进行添加。同时假设节点拥有k层索引的概率f(k)，节点拥有k-1层索引结构的概率为f(k-1)，f(k) = f(k-1)P,假设p为1/2，那么也就是f(k)=f(k-1)\0.5，那么第k层的索引节点数也就是为k-1层的0.5倍。最终索引结构跟上面的这种全索引结构是类似的，只是索引节点不一定分布均匀。空间复杂度=每一层索引节点数=n+n/2+n/4….=2n。Redis做了优化，发现P取1/4时，时间复杂度跟P取1/2是一样的，并且空间复杂度更低。
//ZSKIPLIST_P代表获取下一层的概率，是0.25 //ZSKIPLIST_MAXLEVEL代表是最大层数，是32层 int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; }
Redis计算总层数的算法大致是，初始层数是1层，在while循环内，取一个随机数，
有1/4的概率，层数+1。
有3/4的概率，层数不变，结束循环。
要原因是因为作为一种动态的数据结构，其删除和添加的节点是不可预测的，而跳跃表又不能像平衡二叉树那样，可以通过染色或者旋转来维持平衡，如果严格按照两个节点之间建立一个索引，在删除和添加节点时，需要更新的索引太多了。所以在这种情况下，就需要一种概率随机化的方式来自动均衡跳跃表的多级索引，通过这种方式虽然不能完全保证跳跃表的均匀性，但总体上可以使得跳跃表趋于平衡，从而能够达到较高的综合性能。
新插入了很多节点后带来的问题：
时间复杂度与空间复杂度
空间复杂度的公式是 空间复杂度= 1/(1-P)
