数据结构-跳表
-
跳表是基于有序链表的一种二分查找法，通过构建多级索引（空间换时间），来提高查询的效率，因此跳表的删除、添加、查询，时间复杂度都不高，都为O(log n)，但是空间复杂度有点高为O(n)；
-
图
-
跳表索引动态更新
极端的情况下，动态的添加元素，两个索引之间可能会有非常多的数据，这个时候两个索引的数据相当于单链表。那如何来解决这个问题呢，我们可以通过随机函数来决定这个数要插入到多少级的缓存中。 -
红黑树与跳表对比
删除、插入、查询时间复杂度都一样，都为O(log n)
代码实现上跳表要简单很多，而且跳表在其顺序遍历和区间查找非常方便，所以现在底层数据都采用了跳表。