跳表（Skip List）是一种各个方面性能都比较优秀的动态数据结构，它可以支持快速插入，删除，查找操作，写起来也不复杂。在Redis中的有序集合（Sorted Set）就是用跳表来实现的。
对于一个存储的数据是有序的链表来说，如果我们想要在该链表中查找某个数据，也必须从头到尾遍历链表，这样查询的效率就会很低，时间复杂度为O(n)。
为了提高查询效率，我们对链表建立一级"索引"，查找起来就会快一些，每两个结点提取一个结点到上一级，我们将提取出来的那一级叫做索引或索引层。同时增加指向下一级结点的指针down。
如果我们这次查找的数据为16时，我们可以先遍历索引，当遍历索引到值为13的结点时，发现下一结点为17，那要查找的结点16肯定就是在两个结点之间。然后我们可以通过索引层结点的down指针，下降到原始链表这一层，继续从13开始遍历，此时查询次数由原来的10次变为了现在的7次。由此可知，当我们加了第一级索引之后，查找一个结点需要遍历的结点数减少了，也就是说查找效率提高了。
同理，我们在第一级索引基础上增加第二级索引，这时候效率也会有有所提高。
增加第二级索引之后，查询次数由与原来的7次变为现在的6次。当存在很大的数据量时，我们可以继续增加索引层，以提高查询效率。
如在包含64个结点的链表中，在我们建立五级索引之后，我们查询62的效率会从没有索引的遍历62个结点到拥有五层索引后遍历11个结点，查询效率提高的比较明显。由此可知，随着数据量的增加，跳表的查询效率会提升的非常明显。
调表的插入，删除以及保证跳表的索引大小和数据大小的平衡性，不至于性能过度退化的随机函数选择有待继续学习。
等我研究了Redis中的zset再来补充。
待续
