Skip to main content

redis 跳表，如何快速查找

你提的这个问题非常关键，确实容易混淆。

核心澄清：
随机算法 只决定节点出现在哪些层级上（即节点的高度），并不改变节点之间的顺序。
在每个层级上，所有节点依然是 严格按照分数（score）从小到大排列 的有序链表。

也就是说：

  • 垂直方向：每个节点有一个随机的层数（比如层3、层1…），层级越高，节点越少。
  • 水平方向：在每一层中，节点始终按 score 升序链接。

因此，查找时不是“乱找”，而是从最高层的有序链表开始，逐层下降，利用高层链表的稀疏性实现“跳跃”。

跳表查找的具体过程（以查找分数 68 为例）​

假设某个跳表如下（只画了 forward 指针，数字表示分数）：

Level 3:  头 ---> 10 -------------------------> 90 ---> NULL
Level 2:  头 ---> 10 -------> 40 ------------> 90 ---> NULL
Level 1:  头 ---> 10 -> 20 -> 40 -> 60 -> 68 -> 90 -> NULL

查找步骤：

  1. 从当前最高层（Level 3）的头节点开始。

    • 比较下一个节点的分数 10 < 68，前进到 10。
    • 再看 10 的下一个节点是 90，90 > 68，不能继续前进。
    • 下降到 Level 2。

  2. 在 Level 2，从 10 节点继续。

    • 下一个节点是 40 < 68，前进到 40。
    • 40 的下一个是 90 > 68，停下。
    • 下降到 Level 1。

  3. 在 Level 1，从 40 节点继续。

    • 下一个节点 60 < 68，前进到 60。
    • 再下一个节点 68，相等 → 找到目标。

这样，原本在单链表中需要比较 7 次（10→20→40→60→68），现在只需 5 次（3 次高层跳跃 + 2 次底层遍历），数据量大时优势明显。

为什么随机化不影响查找正确性？​

  • 每个新节点插入时，虽然它的层数是随机的，但它会在 每一层 都被插入到正确的有序位置（通过比较 score）。
  • 因此，所有层上的链表都是完全有序的。
  • 查找时，只要在每一层利用“下一个节点分数 <= 目标”就向右走，不能走就下降，保证不会错过目标。

随机化的唯一作用是让高层节点稀疏且分布均匀，从而平均时间复杂度为 O(log N)，而不需要像平衡树那样维护严格的平衡因子。

对比：如果层级完全随机且不维护顺序会怎样？​

那就不叫跳表了，而是一个随机堆叠的链表集合，无法加速查找。
Redis 的跳表始终维护每一层的顺序性，随机性只用于决定哪些节点出现在高层，这是一种概率平衡技术。

总结一句话：
顺序性由比较 score 保证，层级随机性用于控制跳跃步长，两者结合实现高效查找。