跳表为什么还需要字典结构配合？

跳表（SkipList）是 一种有序链表的多级索引结构，通过增加多层索引来加快查找速度。

  • 最底层：完整的有序链表（包含所有元素）。
  • 上层索引：抽取部分节点作为快捷通道，减少查找步数。
  • 查找过程：从最高层索引开始，能向右就向右，不能向右就向下，直到找到目标或最接近的位置。

举例（每层越上节点越少）：

1
2
3
Level 3:  1 ---------  9
Level 2:  1 --- 5 ---  9
Level 1:  1  3  5  7  9

找元素 7 的过程：

  • 从 Level 3 的 1 → 9（超了，往下）
  • Level 2 的 1 → 5 → 9（超了，往下）
  • Level 1 的 5 → 7（找到）

时间复杂度

跳表的平均性能和 平衡二叉树（AVL/红黑树） 类似：

操作 平均复杂度 最坏复杂度
查找 O(log N) O(N)
插入/删除 O(log N) O(N)
范围查询 O(log N + m) O(N)

m 为返回的结果数量。

在随机化层数 + 合理概率（Redis 用 1/4）下，O(N) 出现概率极低。

为什么 ZSet 还需要 字典结构（hash） 配合

在 Redis 的有序集合 ZSet 里，底层是 跳表（skiplist） + 字典（dict） 组合：

  • 跳表：
    • 按分值（score）排序。
    • 支持范围查询（如 ZRANGEBYSCORE）。
    • 插入、删除、按排名查询效率高。
  • 字典：
    • key：成员（member）
    • value：分值（score）
    • O(1) 时间 根据成员查分值（比如 ZSCORE、ZREM 先定位成员）。
    • 跳表按 score 排序，没法快速通过成员查 score，所以需要字典辅助。

为什么不只用跳表？

  • 如果只用跳表，查一个成员的分值需要 O(logN)，而有了字典就是 O(1)。
  • 删除成员时，需要先 O(1) 定位到 score，再 O(logN) 从跳表删除，整体性能更好。

总结一句话

跳表保证了 有序存储 + 范围查询的高效性，字典保证了 按成员快速定位。

Redis 的 ZSet 用 双结构冗余存储，是空间换时间的设计，既能 O(1) 找成员，又能 O(logN) 做有序操作。