跳表(Skip List)

跳表在基础链表的基础上添加了若干个索引链表,以提高查询效率。

跳表查询数据的时间复杂度为O(logn)

跳表插入和删除数据的时间复杂度也为O(logn)

索引动态更新

当不停地往跳表添加数据的时候,可能会导致间两个索引间数据节点越来越多的情况,导致跳表退化为单链表。

通常的解决方式,是在添加数据的时候,同时更新某几级索引(第1级到第k级)。至于k的值,由一个随机生成函数来实现。