关于跳表
https://time.geekbang.org/column/article/42896
跳表作为一种特殊的有序单链表结构,由于链表本身并不支持二分查找,而在跳表结构中其通过维护多级索引的方式来实现快速查找(类似于二分查找);
对于其索引的结构为存在两个指针,分别是next指针指向同一层级的下一个节点; 同时存在一个down指针指向下一层相同位置(以及相同数据)的节点;
通过增加多级索引可以实现快速查找的目的,避免由于相邻层相同位置索引之间存在过于密集的数据,因此当发现存在出现密集数据时,需要进行索引优化,将索引再次向上抽取提高查询效率;
对于跳表实际就是通过维护多级索引实现类似于二分查找的目的,虽然不能像数组一样直接定位到中间索引位置来实现快速二分法, 但跳表却可以通过多级索引实现二分法(例如在最高级别索引中可以维护1个或三个节点,就可以基本保证只需要两次查询索引操作就可以定位到中间元素,然后依次类推就可以满满的缩小其可能存在的范围)
对于跳表的插入删除查询等时间复杂度都为 O(logn), 但由于需要维护多级索引,因此需要额外的内存空间,虽然空间复杂度为O(n),但n也不是一个完全可以忽略不计的情况;
和红黑树进行对比,首先限制条件不像红黑树一样多,另外其可以有效的平衡效率和空间问题(例如当认为空间浪费较多或索引之间空洞较大的情况下,可以不维护那么多层级的索引,同时也不会直接影响到效率问题);
而对于红黑树而言,虽然其时间复杂度也为O(logn),但相对而言跳表的代码实现更加简单一些
原文：https://www.cnblogs.com/xingguoblog/p/14189294.html