解决问题

• 数组支持随机访问可以用二分查找 用链表改进版跳表可以支持类似二分查找算法

• 代替红黑树

  是什么

  
  

• 把每两个节点提取作为一级索引，一级索引的每两个节点提出作为二级索引直到这层的节点小于等于3个，可以提升查询性能

  跳表查询性能

  时间复杂度

• O(logn) 采取以空间换时间的策略

  空间复杂度

• 跳表的空间复杂度是 O(n)。 n 个结点的单链表构造成跳表，需要额外接近 n 个结点的空间 (等差数列)

• 实际开发 索引不存储对象 可以忽略索引占用空间

跳表插入删除

• 插入操作直接插入 删除操作需要找到前一个节点 并且需要删除索引

  跳表退化

• 退化表示2个索引节点出现很多数据

• 通过随机函数来维护平衡性 插入数据时通过随机函数 来确定把数据加到第1级~第k级索引

  跳表优点

• 比红黑树简单容易实现 以下操作 红黑树不支持区间查找

• 插入一个数据；
  
• 删除一个数据；
  
• 查找一个数据；
  
• 按照区间查找数据（比如查找值在 [100, 356] 之间的数据）；
  
• 迭代输出有序序列。