看完Redis源码还不理解跳跃表吗？( 二 ) _Redis

添加第一级索引【看完Redis源码还不理解跳跃表吗？】如何提高链表线性查找的效率？

文章插图

具体我们来看上图，在原始链表的情况下，我们再增加一个维度，也就是在上面再增加一层索引，我们叫做第一级索引，那么第一级索引的话就不是指向它元素的 next 元素了，而是指向它的 next next，也就是说你可以理解为 next + 1 就行了，所以第一级索引的话就是第一个元素，马上第三个元素、第五个元素、第七个元素。

这里你就会发现如果你要找7的话，我们怎么办？我们这么查找，先查找第一级索引看有没有1 4 7，如果有那就说明 7 存在这个链表里面是存在的，说明我们查询到了。
我们再看要查另一个元素，比如说 8，我们怎么走？还是先找第一级，8是大于 1 的，所以后继往后到达 4 索引的值，8 是大于 4的，继续往后到了7，8 也大于7的，再继续往后发现 9 大于 8 了。说明 8 是存在于 7 和 9 这两个索引之间的元素里面的，那么这个时候从第一级元素向下走到原始的链表了，从对应的位置挨个找就会发现 8 找到了，说明 8 也是存在的。

添加第二级索引那么有的朋友可能就会想了，你加一级索引的话，每次相当于步伐加 2 了，但是它的速度的话也就是比原来稍微快了一点，能不能更快呢？对你这个想法是非常有道理的，也是很好的。
那么在一级索引的基础上，我们可以再加索引就行了，也就是说同理可得，在第一级索引的基础上，我们把它当作是一个原始链表一样，往上再加一级索引，也就是说每次针对第一级索引走两步。那么它相等于原始链表相当于每次就走了四步。对不对，就乘于 2，那这样的话，速度就更加高效了。

比如我举个例子要查8，先找 1，8 比 1要大，再找 7，这时候你会发现 8 也是比 7 大的，再找，假设这个元素后面的话是 11 或者 12 好了，这时候你会发现 8 是小于它后面的元素，所以 7 这里的话就必须向下再走一级索引了，走到第一级索引的 7 来，再类似于之前 7 和 9 之间，然后再走到8 这样一直走下来。

文章插图

添加多级索引以此类推，增加多级索引
假设有五级索引的这么一个原始链表，那么我们要查一个元素，比如说要查 62 元素或者中间元素，就类似于下图，一级一级一级一级走下来，最后的话就可以查到我们需要的62这个元素。当然的话你最后查到原始链表，你会发现比如说是我们要查63或者61，原始链表里面没有，我们就说元素不存在，在我们这个有序的链表里面，也就是说在跳表里面查不到这么一个元素，最后也可以得出这样的结论。

文章插图

跳表查询的时间复杂度分析跳表的时间复杂度计算

n/2、n/4、n/8、第 k 级索引结点的个数就是 n/(2^k)
假设索引有 h 级，最高级的索引有 2 个结点。n/(2^h) = 2，从而求得 h = log2(n)-1

文章插图

举一个例子，跳表在查询的时候，假设索引的高度：logn，每层索引遍历的结点个数：3，假设要走到第 8 个节点。
每层要遍历的元素总共是3个，所以这里的话 log28 的话，就是它的时间复杂度。最后的话得出证明出来：时间复杂度为log2n 。也就是从最朴素的原始链表的话，它的 O(n) 的时间复杂度降到 log2n 的时间复杂度。这已经是一个很大的改进了。假设是1024的话，你会发现原始链表要查1024次最后得到这个元素，那么这里的话就只需要查（2的10次方是1024次）十次这样一个数量级。
现实中跳表的形态在现实中我们在用跳表的情况下，它会由于这个元素的增加和删除而导致的它的索引的话，有些数它并不是完全非常工整的，最后经过多次改动后，它最后索引有些地方会跨几步，有些地方会少只跨两步，这是因为里面的一些元素会被增加和删除了，而且它的维护成本相对较高，也是说当你增加一个元素，你会把它的索引要更新一遍，你要删除一个元素，也需要把它的索引更新一遍。在这种过程中它在增加和删除的话，它的时间复杂度就会变成 O(logn) 了。