面试题：Redis跳跃表中节点的结构是怎样的，以及它如何支持快速查找？

Question

请详细描述Redis跳跃表中节点的数据结构组成，包括每个部分的作用。并解释基于这种节点结构，跳跃表是怎样实现快速查找功能的。

Answer 1

Redis跳跃表节点数据结构组成及作用

1. 层（level）：
   • 是一个数组，数组中的每个元素包含两个部分：前进指针（forward）和跨度（span）。
   • 前进指针：指向表中位于更高级别的节点，用于快速在跳跃表中向前移动，以实现快速查找。例如，在查找某个元素时，可以通过层中的前进指针跳过一些中间节点，直接定位到可能包含目标元素的区域。
   • 跨度：记录了从当前节点到前进指针指向节点之间的节点数量。在计算排名等操作时会用到跨度信息，通过累加跨度可以知道某个节点在跳跃表中的位置。
2. 后退指针（backward）：
   • 指向当前节点的前一个节点，主要用于在跳跃表中反向遍历。例如，在实现范围查找等功能时，如果需要从后向前遍历跳跃表，就会用到后退指针。
3. 分值（score）：
   • 是一个双精度浮点数，用于对跳跃表中的节点进行排序。跳跃表中的节点按分值从小到大排序，当查找某个分值对应的节点时，基于分值的有序性可以快速缩小查找范围。
4. 成员对象（obj）：
   • 是一个指向Redis对象的指针，用于存储与节点相关联的值。例如，在使用跳跃表实现有序集合时，obj可以指向集合中的成员元素。

基于该节点结构跳跃表实现快速查找功能的原理

1. 多层次索引：
   • 跳跃表通过节点中的层数组实现多层次索引结构。最底层包含所有节点，而每一层都是下一层的“稀疏”版本，即高层节点稀疏地分布在底层节点之上。例如，假设最底层有100个节点，第一层可能每隔几个节点（如5个）有一个节点，第二层可能每隔更多节点（如25个）有一个节点。
   • 在查找时，从最高层开始，通过层中的前进指针，比较当前节点的分值与目标分值。如果当前节点的分值小于目标分值，就沿着前进指针移动到下一个节点；如果当前节点的分值大于目标分值，就下降到下一层继续查找。这样通过不断地在高层跳跃和向下层移动，可以快速接近目标节点。
2. 快速定位：
   • 由于跳跃表的这种结构，在查找时可以跳过大量无关节点。例如，要查找分值为x的节点，从高层开始查找，高层节点稀疏，能够快速跨越较大范围，缩小查找区域。当到达某一层，发现当前节点分值小于x且下一个节点分值大于x时，下降到下一层继续查找，不断重复这个过程，最终可以快速定位到目标节点。这种方式避免了在底层链表中逐个遍历节点，大大提高了查找效率，其时间复杂度平均为O(log n)，n为跳跃表中的节点数量。