跳跃表（跳表）

• 什么是跳跃表？ 跳跃表是将链表改造支持二分法查找的数据结构 ，如果是一个单链表的话，他查找数据的时间复杂度为O(n)，于是给单链表添加一级索引 每两个节点提取一个节点到上一级，我们把诌出来的哪一级叫做索引或者索引层，如下图：

如上图当你查找16的时候，你只需要遍历7次就可以得到结果值 ， 先去第一层索引查到，遍历到13的时候 发现下一个节点是17 那我们就知道此时16就在这两个节点之间，所以我们进行down进入下一层 继续遍历这个时候我们只需要遍历两个节点就可以找到了，所以我们遍历16在建立上层索引的情况下是只需要遍历7次，但是单链表便利需要10次，那我们在继续添加及层索引如下图:

当有64个节点的链表的时候，则会创建多少层索引, 通过计算回事5层，那么每一层的索引个数呢，n/2^k （n为总的索引树，k为创建的索引层数（不包括原始链表数据结构））, 最高的层的索引层的长度为2，那我们计算出 层级为 k = log2^n- 1 ，如果我们每一层遍历M个元素那么我们的时间复杂度为O(m(log2^n-1)) ,我们的是两个元素结合为一个节点那么每一层最多遍历3个元素，那么我们时间复杂度为O(3log2^n -1) 那么时间复杂度为 O（logn） 现在就是在原有的得单链表上创建了多层索引而达到二分法查找，达到很高。 那么现在这样岂不是浪费了很多的内存（空间换用时间）。

• 跳跃表的是如何插入和更新? 插入和更新的时候索引层是如何改变的？