28. 详细说说 redis 跳表的实现？

PangHu大约 5 分钟

什么是跳表（Skip List）？

跳表（Skip List）是一种用于有序数据存储的动态数据结构，它通过在链表基础上增加多级索引，使得查找、插入和删除操作的平均时间复杂度达到 O(log N)，从而在性能上接近平衡树，但实现上却更加简单。跳表的出现解决了在纯链表中查找速度较慢的问题，并且在 Redis 中，被用于实现有序集合（Sorted Set, ZSet）和其他需要快速查找、插入和删除有序数据的场景。

跳表的结构

跳表的基本结构是由多层链表构成：

最底层：是一个有序的单链表，存储所有元素。每个元素都包含在这一层中。
上层链表：是下层链表的一个“抽样”或“索引”。每一层链表中的元素都是下一层链表中元素的一个子集。

跳表的每一层都是一个链表，越高的层数，包含的元素越少，通常是下层元素的1/2，1/4，1/8……依此类推。因此，查找操作可以从最高层开始，如果元素不在当前层，则在下一层查找，直到最底层的链表。

跳表的关键操作

跳表的关键操作包括查找、插入和删除。下面详细介绍这些操作：

1. 查找

查找操作从跳表的最高层开始，比较目标值与当前节点的值：

如果目标值大于当前节点的值，则向右移动到下一个节点。
如果目标值小于或等于当前节点的值，则向下一层移动，继续查找。
当到达最底层链表时，如果发现目标值，则查找成功；否则，查找失败。

时间复杂度：O(log N)。

2. 插入

插入操作需要首先找到插入位置，然后将元素插入到对应的层中，并根据概率决定是否将该元素的索引添加到上层链表中。

插入步骤：

查找元素在最底层的插入位置。
从底层到顶层依次插入元素。
根据随机函数（通常是抛硬币）决定是否将元素插入到上一层。继续这个过程，直到某一层决定不插入或到达最高层。

时间复杂度：O(log N)。

3. 删除

删除操作首先需要找到元素所在的位置，然后在每一层链表中删除该元素的节点。

删除步骤：

从跳表的最高层开始，查找到需要删除的元素位置。
在找到的元素节点上，向下逐层删除对应的节点。
如果某一层链表在删除节点后变为空，可以选择删除该层，减少空间开销。

时间复杂度：O(log N)。

Redis 中的跳表实现

在 Redis 中，跳表是通过 zskiplist 结构来实现的，主要用于有序集合（ZSet）的实现。Redis 的有序集合需要高效地支持按分数排序的插入、删除和范围查找操作，跳表结构非常适合这些需求。

1. 跳表节点（zskiplistNode）

每个跳表节点存储一个元素的信息，包括元素的值和分数。每个节点还包含一个指向后继节点的数组（指针列表），每个指针对应一个层级。

typedef struct zskiplistNode {
    sds ele;                      // 节点的元素值
    double score;                 // 节点的分数
    struct zskiplistNode *backward; // 后退指针，用于快速倒序访问
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针，指向该层级的下一个节点
        unsigned int span;             // 跨度，表示从当前节点到下一个节点的距离
    } level[];
} zskiplistNode;

ele：存储节点的值。
score：存储节点的分数，用于排序。
backward：用于反向遍历，指向前一个节点。
level[]：指针列表，每个元素指向不同层级的下一个节点。

2. 跳表结构（zskiplist）

跳表的结构体定义如下：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头节点和尾节点
    unsigned long length;                // 节点数量
    int level;                           // 跳表的当前层数（最高层数）
} zskiplist;

header：指向跳表的头节点（通常是一个空节点）。
tail：指向跳表的尾节点，用于快速访问最后一个节点。
length：跳表中节点的数量。
level：跳表的当前层数，随着插入和删除操作而变化。

3. 跳表的插入、删除和查找

Redis 实现的跳表提供了插入、删除和查找操作，通过这些操作，可以高效地管理有序集合中的元素。

插入：新元素插入到合适的位置，并随机决定是否在上层链表中增加索引。
删除：从最高层到最低层逐层删除目标元素，并更新相关指针。
查找：从最高层开始逐层查找，直到找到目标元素或确认不存在。

跳表与其他数据结构的比较

与平衡树（如红黑树）相比，跳表有以下特点：

实现简单：跳表的实现比平衡树简单得多，维护成本低。
性能接近：跳表的时间复杂度与平衡树相当，但在许多实际场景中，跳表的性能表现更优，因为它具有良好的缓存局部性。
动态调整：跳表在元素插入和删除时，动态调整其结构，而不需要像平衡树那样进行复杂的旋转操作。

总结

跳表是一种基于多级链表的高效数据结构，Redis 使用跳表来实现有序集合中的排序和查找功能。通过多层级的链表结构，跳表能够在O(log N)的时间复杂度内完成插入、删除和查找操作，同时具备较好的实现简单性和性能表现。这使得跳表成为Redis实现高效有序数据存储的重要工具。