跳表(Skip List) § 跳表在基础链表的基础上添加了若干个索引链表,以提高查询效率。 跳表查询数据的时间复杂度为O(logn)。 跳表插入和删除数据的时间复杂度也为O(logn)。 索引动态更新 § 当不停地往跳表添加数据的时候,可能会导致间两个索引间数据节点越来越多的情况,导致跳表退化为单链表。 通常的解决方式,是在添加数据的时候,同时更新某几级索引(第1级到第k级)。至于k的值,由一个随机生成函数来实现。