跳表
Skip List
Search: O(log n)Delete: O(log n)Insert: O(log n)Space: O(n)
如果每 2^i 个节点都指向前面 2^i 个节点，寻找一个节点的复杂度变成 logn(类似于二分查找)那么问题来了,为什么随机的层数也能保证 logN 的复杂度? 原因就在于,这里说的随机,并不是完全的随机一个层数出来,而是通过随机的算法,算出一个并不随机的层数来，以 redis 中的随机层数的算法来看int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;}这里假设 ZSKIPLIST_P 为 2 (实际为 4,便于理解设置为 2),这段代码我们可以理解为,落到层数为 i + 1 的概率为 0.5^i 而反过来理解,每两个节点出现层数为 2 的期望就是 1,每 4 个节点出现第三层的期望也为 1,每 8 个节点出现第四层(0.5^3)的期望为 1 (期望值 = 单个概率 * 数量)正是基于此,如果我们的数据量越大,越是可以接近期望的值,所以,我们可以认为,我们实现了 “如果每 2^i 个节点都指向前面 2^i 个节点"的效果,也就是说,查找的平均复杂度为 O(logN)