Redis 的跳表（Skip List）是一种高效的数据结构，用于实现 Redis 的有序集合（Sorted Set）功能。

跳表是一种概率平衡的数据结构，它通过在多层链表上添加“快捷路径”来实现快速查找，类似于在一本书的不同章节开始页加上索引，以便快速跳转到某个章节。

跳表的效率可以媲美平衡树（如红黑树），对于插入、删除、查找操作，跳表的平均时间复杂度和最坏时间复杂度都是 O(logN)。

跳表的结构

跳表由多层链表组成，底层是原始链表，包含所有元素。

每一层都是上一层的子集，第 i 层的元素通过一个或多个指针指向第 i-1 层的元素。

最顶层的链表包含的元素最少（可能只有一个或几个）。

搜索从最顶层开始，如果在当前层找不到目标元素，就下降到下一层继续查找。

Redis 中的跳表

Redis 使用跳表来实现有序集合（ZSet）类型，这允许它执行各种与顺序相关的操作，例如：

  • 插入元素时保持顺序。
  • 查找某个分数范围内的所有元素。
  • 获取元素的排名或者根据排名区间查询元素。

跳表之所以适用于 Redis，主要有以下几个原因：

  1. 效率高：跳表的增删改查操作的时间复杂度为 O(logN)，这使得即使在包含大量元素的情况下，跳表操作仍然非常快速。

  2. 实现相对简单：与平衡树（如 AVL 树、红黑树）相比，跳表的代码实现更为简单直接。这降低了代码的复杂性和维护难度。

  3. 支持范围查询：跳表支持高效的范围查询操作，这对于实现 Redis 的有序集合特性非常关键。

  4. 有序：跳表内部元素是有序的，这直接支持了有序集合的语义。

Redis 的跳表实现不仅仅依靠跳表本身。

为了提高效率，Redis 的有序集合同时使用了哈希表和跳表两种数据结构。

哈希表用于存储元素（成员）到分数的映射，以实现 O(1) 时间复杂度的元素访问；跳表则用于按分数排序和范围查询，以支持各种基于顺序的操作。

总的来说，跳表是 Redis 实现有序集合这一复杂数据结构的关键，使得 Redis 能够高效地支持一系列与顺序和排名相关的操作。