面试题：Redis跳跃表在搜索场景中相比传统链表的优势有哪些

Question

在搜索场景下，Redis跳跃表通过什么结构特性实现比传统链表更高效的搜索？请简要阐述这些特性是如何提升搜索效率的。

Answer 1

1. 分层结构
   • 结构特性：Redis跳跃表具有多层结构，最底层是普通的链表结构，包含所有的节点。从底层向上，每一层都是下一层的“稀疏化”版本，高层节点是从底层节点中随机抽取出来的。
   • 提升搜索效率原理：在搜索时，首先从最高层开始，利用高层节点跨度大的特点进行快速跳跃式查找。比如要查找一个较大值的节点，在高层可以快速跳过很多小值节点，当在某一层找到一个节点值大于等于目标值时，再下降到下一层继续查找，如此反复，大大减少了需要遍历的节点数量，就像走楼梯一样，每层楼梯可以跨越更多的距离，从而提升了搜索效率。
2. 有序性
   • 结构特性：跳跃表中的节点是按照一定顺序排列的，无论是在哪一层，节点都是有序的。
   • 提升搜索效率原理：这种有序性使得在搜索时可以利用二分查找的思想。在每一层查找时，当遇到一个节点值大于目标值时，就不需要再往后遍历该层的节点了，直接下降到下一层继续查找。这样就避免了在无序结构中需要遍历所有节点才能确定目标值是否存在的情况，进一步提高了搜索效率。