跳跃表 Redis 的底层数据结构 _节点

我们都知道单链表有一个致命的弱点，查找任一节点都至少 O(n) 的时间复杂度，它需要遍历一遍整个链表，那么有没有办法提升链表的搜索效率？
跳跃表（）这种数据结构使用空间换时间的策略，通过给链表建立多层索引来加快搜索效率，我们先介绍跳跃表的基本理论，再来看看 redis 中的实现情况。
一、跳跃表（）
这是一条带哨兵的双端链表，大部分场景下的链表都是这种结构，它的好处是，无论是头插法还是尾插法，插入操作都是常量级别的时间复杂度，删除也是一样。但缺点就是，如果想要查询某个节点，则需要 O(n) 。
那如果我们给链表加一层索引呢？当然前提是最底层的链表是有序的，不然索引也没有意义了。
让 HEAD 头指针指向最高索引，我抽出来一层索引，这样即便你查找节点 2222 三次比较。
第一次：与 2019 节点比较，发现大于 2019，往后继续
第二次：与 2100 节点比较，发现依然大于，往后继续
第三次：本层索引到头了，指向低层索引的下一个节点，继续比较，找到节点
而无索引的链表需要四次，效率看起来不是很明显，但是随着链表节点数量增多，索引层级增多，效率差距会很明显。图就不自己画了，取自极客时间王争老师的一张图。
你看，原本需要 62 次比较操作，通过五层索引，只需要 4 次比较，跳跃表的效率可见一瞥。
想要知道具体跳跃表与链表差距多少，我们接下来进行它们各个操作的时间复杂度分析对比。
1、插入节点操作
双端链表（以下我们简称链表）的原本插入操作是 O(1) 的时间复杂度，但是这里我们讨论的是有序链表，所以插入一个节点至少还要找到它该插入的位置，然后才能执行插入操作，所以链表的插入效率是 O(n) 。
跳跃表（以下我们简称跳表）也依然是需要两个步骤才能完成插入操作，先找到该插入的位置，再进行插入操作。我们设定一个具有 N 个节点的链表，它建有 K 层索引并假设每两个节点间隔就向上分裂一层索引。
【跳跃表Redis 的底层数据结构】k 层两个节点，k-1 层 4 个节点，k-2 层 8 个节点 … 第一层 n 个节点，
1：n2：1/2 * n3：1/2^2 * n..........k：1/2^(k-1) * n
1/2^(k-1) * n 表示第 k 层节点数，1/2^(k-1) * n=2 可以得到，k 等于 logn，也就是说，N 个节点构建跳表将需要 logn 层索引，包括自身那层链表层。
而当我们要搜索某个节点时，需要从最高层索引开始，按照我们的构建方式，某个节点必然位于两个索引节点之间，所以每一层都最多访问三个节点。这一点你可能需要理解理解，因为每一层索引的搜索都是基于上一层索引的，从上一层索引下来，要么是大于（小于）当前的索引节点，但不会大于（小于）其往后两个位置的节点，也就是当前索引节点的上一层后一索引节点，所以它最多访问三个节点。
有了这一结论，我们向跳表中插入一个元素的时间复杂度就为：O(logn) 。这个时间复杂度等于二分查找的时间复杂度，所有有时我们又称跳表是实现了二分查找的链表。
很明显，插入操作，跳表完胜链表。
2、修改删除查询
这三个节点操作其实没什么可比性，修改删除操作，链表等效于跳表。而查询，我们上面也说了，链表至少 O(n)，跳表在 O(logn) 。
除此之外，我们都知道红黑树在每次插入节点后会自旋来进行树的平衡，那么跳表其实也会有这么一个问题，就是不断的插入，会导致底层链表节点疯狂增长，而索引层依然那么多，极端情况所有节点都新增到最后一级索引节点的右边，进而使跳表退化成链表。