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)
Links
