面试题：Redis跳跃表相较于普通链表在查找操作上的优势是什么

Question

请详细阐述Redis跳跃表在查找节点时，是如何利用多层结构提高查找效率的，与普通链表的查找方式有哪些不同，从时间复杂度的角度进行分析。

Answer 1

Redis跳跃表查找节点利用多层结构提高效率的方式

1. 多层索引结构：
   • Redis跳跃表由多层链表组成，最底层是包含所有节点的链表，而上层链表是下层链表的“稀疏”版本。例如，每两个底层节点可能会有一个节点出现在上一层链表中，更高层则更为稀疏。
   • 在查找节点时，从最上层链表开始。因为上层链表节点稀疏，在这一层查找时可以快速地跳过许多节点范围。例如，在一个有100个节点的跳跃表中，最上层可能只有10个节点，通过在这一层查找，可以快速定位到目标节点大致所在的区间。
   • 当在某一层找到一个节点的前驱节点，且前驱节点的后继节点大于目标节点时，就下降到下一层继续查找。这样不断在不同层间切换查找，逐步缩小查找范围，快速逼近目标节点。
2. 随机化分层：
   • 跳跃表节点在插入时，会随机决定该节点向上层“晋升”的层数。这种随机化方式使得跳跃表的结构相对平衡，避免出现极端的不均匀情况，保证了在不同数据规模下都能有较好的查找效率。

与普通链表查找方式的不同

1. 查找路径：
   • 普通链表：普通链表查找节点时，只能从链表头开始，依次遍历每个节点，直到找到目标节点或到达链表尾。例如，在一个有n个节点的链表中查找第n个节点，需要遍历n - 1次。
   • 跳跃表：跳跃表可以从多层链表的上层开始查找，通过在不同层间跳跃式地查找，大大减少了需要遍历的节点数量。如上述100个节点的跳跃表查找某节点，可能只需遍历20 - 30个节点（取决于跳跃表的具体结构）。
2. 查找方向：
   • 普通链表：通常只能单向顺序查找（单向链表），双向链表虽可双向查找，但本质仍是顺序遍历。
   • 跳跃表：查找时可以在不同层间灵活切换，先在高层快速定位大范围，再在底层精确定位，查找方向更具灵活性。

时间复杂度分析

1. 普通链表：
   • 在普通链表中，查找一个节点最坏情况下需要遍历链表的所有节点。如果链表长度为n，时间复杂度为O(n)。这是因为在最糟糕的情况下，目标节点位于链表末尾，需要依次访问每个节点。
2. 跳跃表：
   • 理想情况下，跳跃表每一层的节点数大约是下一层的一半。假设跳跃表高度为h，底层节点数为n。因为每下降一层，需要遍历的节点数大致翻倍，所以可以近似认为n = 2^h ，即h = log₂n。
   • 在跳跃表查找节点时，每一层最多遍历两个节点（一个前驱节点和一个后继节点，用于判断是否下降到下一层）。所以总的时间复杂度为O(log n)，因为高度h = log₂n，在最坏情况下需要遍历的节点数与跳跃表高度相关，而高度与节点数的对数相关。这使得跳跃表在大规模数据下的查找效率远高于普通链表。