likes
comments
collection
share

Redis 的跳跃表的底层原理及代码实现解读

作者站长头像
站长
· 阅读数 0

最近学习并使用Redis 有序队列做工作项目上相关应用(删除已到达过大货架),则顺便找到了其原理及源码进行学习,发现其本质是使用跳跃表。

Redis 使用跳跃表(skiplist)作为有序集合(sorted set)的底层数据结构之一,允许它执行快速的插入、删除、查找和有序访问操作。跳跃表是一种概率性的数据结构,它通过在多个层上添加额外的前向指针来提高平均查找性能,类似于在链表上增加“快速通道”。

 跳跃表的底层原理:

  1. 多层结构:跳跃表包含多个层次,每个层次都是一个有序的链表。底层(第 0 层)包含所有的元素,而上层包含的元素越来越少。

  2. 前向指针:跳跃表的每个节点包含多个指针,指向同一层次的下一个节点和下面层次的节点。

  3. 概率平衡:在插入新节点时,通过一个随机过程决定新节点的层数。通常,每个节点有 1/2 的概率晋升到更高的层次。

  4. 查找路径:查找操作从最高层开始,沿着节点的前向指针移动,直到找到目标节点或一个比目标节点大的节点。如果当前节点的下一个节点大于目标节点,操作将移动到下一层继续查找。

  5. 插入和删除:插入和删除操作首先使用查找路径来确定节点的位置,然后进行相应的链表操作。在插入时,还需要决定新节点的层数,并更新相关节点的指针。

跳跃表(Skip List)是一种概率性数据结构,它通过在多层链表上添加前向指针来提高查找效率。

在 Redis 中,跳跃表被用于实现有序集合(sorted sets)和某些类型的范围查询。

 优点:

  1. 简单性:跳跃表相对于其他平衡树(如红黑树)来说,算法和数据结构更加简单易懂,易于实现和维护。

  2. 性能:跳跃表提供了接近平衡树的平均时间复杂度(O(log n))的插入、删除和查找操作,同时实现起来比平衡树简单。

  3. 无锁操作:在多线程环境中,跳跃表可以更容易地实现无锁(lock-free)的并发操作,因为它的插入和删除操作可以自然地分解为一系列的局部更新。

  4. 范围查询:跳跃表对于执行范围查询(例如查找所有分数在某个区间的元素)非常有效,因为它可以快速跳过不满足条件的元素。

  5. 可调性:跳跃表的层数和概率因子是可调的,这意味着可以根据数据集的特性进行优化。

缺点:

  1. 空间消耗:由于每个元素需要存储多个指针(每个层级一个),跳跃表通常需要比简单链表更多的内存空间。

  2. 概率性能变化:跳跃表的性能是概率性的,这意味着在最坏的情况下,操作的时间复杂度可能会退化到 O(n)。虽然这种情况很少发生,但它确实是由跳跃表的随机化性质引起的。

  3. 缓存局部性:相比于平衡树,跳跃表的缓存局部性较差。这是因为跳跃表的节点分散在内存中,而平衡树的节点通常更紧凑,这可能导致更多的缓存未命中。

  4. 实时性能:虽然跳跃表的平均性能很好,但由于其概率性质,它无法保证所有操作都有最优的实时性能。

  5. 重平衡:在极端情况下,跳跃表可能需要通过调整层数或重新分布节点来重平衡,以保持高效的操作性能。

总的来说,跳跃表是一种平衡了简单性、性能和可调性的数据结构,非常适合于需要快速插入和范围查询的场景。Redis 选择使用跳跃表作为有序集合的底层实现,正是因为它提供了一种高效且简单的方式来管理有序数据。

Redis 中跳跃表的代码实现:

Redis 的跳跃表实现主要在 server.h(定义数据结构)和 t_zset.c(实现操作)中。

Redis 的跳跃表的底层原理及代码实现解读 zset数据结构底层实现为字典(dict)+跳表(skiplist)

typedef struct zset {
    dict *dict; //字典
    zskiplist *zsl;//跳表
} zset;

zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度)

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头节点和尾节点
    unsigned long length;                // 节点数量
    int level;                           // 层数
} zskiplist;

zskiplistNode则用于表示跳跃表节点

typedef struct zskiplistNode {
    robj *obj;                           // 元素值
    double score;                        // 分数,用于排序
    struct zskiplistNode *backward;      // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;   // 前进指针
        unsigned long span;              // 跨度
    } level[];
} zskiplistNode;

插入操作:

插入新节点的过程包括确定新节点的层数、创建新节点、更新前向指针和后退指针

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    // ......

    /* 随机决定节点层数 */
    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;

        /* 更新跨度 */
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    //.......
    return x;
}

Redis 的跳跃表的底层原理及代码实现解读

查找操作:

查找操作从最高层开始,如果当前节点的下一个节点的分数大于要查找的分数,就下降到下一层继续查找。

zskiplistNode *zslFind(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x = zsl->header;
    int i;

    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
               (x->level[i].forward->score < score || 
                       (x->level[i].forward->score == score &&
                 sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            x = x->level[i].forward;
        }
    }
    x = x->level[0].forward;
    if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
        return x;
    } else {
        return NULL;
    }
}

以上是 Redis 跳跃表的简化版代码示例和解读。实际的 Redis 源码还包括了许多其他的细节,比如内存管理、错误处理和更加复杂的操作(如范围查询和删除)。

跳跃表的性能在大多数情况下可以与平衡树相媲美,而且实现起来更加简单,这使得它成为 Redis 有序集合的理想选择。

Redis 的跳跃表的底层原理及代码实现解读