excel小程序商店seo网络推广案例

为什么使用跳表？

对于单链表，即使是有序链表，想在其中查找某个数据，也只能从头到尾遍历，查找效率低，时间复杂度是O(n)。

跳表实现

跳表是基于有序单链表建索引来实现的。

时间复杂度和空间复杂度

时间复杂度是O(logn),空间复杂度是O(n)。

跳表索引动态更新？

当频繁地向跳表中插入数据时，如果插入过程不伴随着索引更新，就有可能导致某2个索引节点之间数据非常多，在极端地情况下，跳表就会退化成单链表。

作为一种动态数据结构，为了避免性能下降，我们需要在数据插入，删除的过程中，动态地更新跳表的索引结构。

跳表是借助随机函数来更新索引结构。

随机函数

对于每一个新插入的节点，都需要调用一个随机算法给它分配一个合理的层数，一个节点随机出的层数是 3，那么就把它链入到第 1 层到第 3 层这三层链表中。

源码在 t_zset.c/zslRandomLevel(void) 中被定义：

int zslRandomLevel(void) {int level = 1;while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

直观上期望的目标是 50% 的概率被分配到 Level 1，25% 的概率被分配到 Level 2，12.5% 的概率被分配到 Level 3，以此类推…有 2-63 的概率被分配到最顶层，因为这里每一层的晋升率都是 50%。

Redis 跳跃表默认允许最大的层数是 32，被源码中 ZSKIPLIST_MAXLEVEL 定义，当 Level[0] 有 264 个元素时，才能达到 32 层，所以定义 32 完全够用了。

为什么Redis使用跳表而不是红黑树？

针对增删改查元素来说，跳表和红黑树的效率是一样的。

但按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表可以在 O(logn)

除此之外，跳表相对于复杂的红黑树来说，代码具有更具有可读性。