面试题：Redis跳跃表在范围查询中的基本优化思路

Question

请阐述Redis跳跃表在范围查询时，相较于普通链表，采用了哪些基本的优化思路来提升查询效率？

Answer 1

• 多层索引结构：普通链表只有一层线性结构，查询时需依次遍历每个节点。而Redis跳跃表构建了多层索引，高层索引节点稀疏，低层索引节点稠密。范围查询时，可先在高层索引快速定位大致范围，减少遍历节点数量，比如查询值在一定区间内的节点，能从高层索引快速跳过大量无关节点，再到低层索引精确查找，提升查询效率。
• 快速定位指针：跳跃表节点除了指向下一个节点的指针，还有多层指向远方节点的指针。在范围查询确定起始节点后，利用这些指针可快速在相关范围内移动，而普通链表只能逐个节点移动，通过这种方式减少了定位范围内节点的时间开销，优化了查询效率。