MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Redis跳跃表API的使用方法与技巧

2023-11-205.0k 阅读

Redis跳跃表概述

Redis中的跳跃表（Skip List）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表以其高效的插入、删除和查找操作，在Redis的有序集合（Sorted Set）等数据结构中得到了广泛应用。

跳跃表的基本思想是在链表的基础上，为每个节点增加多级索引。例如，普通链表查找一个节点需要依次遍历每个节点，时间复杂度为O(n)。而跳跃表通过建立多层索引，使得在查找时可以跳过一些节点，从而将平均时间复杂度降低到O(log n)。

Redis跳跃表API相关数据结构

在深入探讨API使用方法之前，先了解一下Redis跳跃表相关的数据结构。

跳跃表节点结构

Redis跳跃表的节点结构定义在sds.h文件中，主要结构如下：

typedef struct zskiplistNode {
    sds ele;      // 成员对象，在有序集合中为成员的名称
    double score; // 分值，用于对节点进行排序
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span; // 跨度，表示当前指针到下一个节点之间跨越的节点数
    } level[]; // 柔性数组，用于存储不同层级的指针和跨度
} zskiplistNode;
  • ele：存储节点的值，在Redis有序集合中，这个值通常是一个字符串对象，代表有序集合的成员。
  • score：是一个双精度浮点数，作为节点排序的依据。在有序集合中，通过score对成员进行排序。
  • backward：指向当前节点的前一个节点，方便从后往前遍历跳跃表。
  • level：是一个柔性数组，每个元素包含一个forward指针，指向下一个节点，以及一个span跨度值。不同层级的forward指针可以跳过不同数量的节点，实现快速查找。

跳跃表结构

跳跃表整体结构定义如下：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头节点和尾节点
    unsigned long length; // 跳跃表的节点数量
    int level; // 跳跃表的当前最大层数
} zskiplist;
  • header：指向跳跃表的头节点，头节点是一个特殊节点，不存储实际数据，主要用于方便跳跃表的操作。它的层级数在初始化时通常设置为一个较大的值（如32），随着节点的插入和删除，头节点的层级可能会动态调整。
  • tail：指向跳跃表的尾节点，方便从后往前遍历跳跃表。
  • length：记录跳跃表中除头节点外的实际节点数量。
  • level：表示当前跳跃表的最大层级数。层级数会随着节点的插入动态增加，以维持跳跃表的高效性。

Redis跳跃表API使用方法

创建跳跃表

在Redis中，通过zslCreate函数来创建一个新的跳跃表。以下是简化后的代码示例（实际Redis源码中还包含更多细节和内存管理操作）：

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

在上述代码中：

  1. 首先分配zskiplist结构体的内存空间。
  2. 初始化跳跃表的层级为1，长度为0。
  3. 创建头节点，头节点的层级数为ZSKIPLIST_MAXLEVEL（通常定义为32），并初始化每个层级的forward指针为NULL，span为0。
  4. 设置头节点的backward指针为NULL，尾节点指针也为NULL。

插入节点

插入节点是跳跃表的核心操作之一，Redis中通过zslInsert函数实现。下面以简化的代码来分析其主要逻辑：

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

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->level-1)? 0 : rank[i+1];
        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)))
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }

    x = x->level[0].forward;
    if (x && x->score == score && sdscmp(x->ele,ele) == 0) {
        // 节点已存在，更新分值等操作
        return x;
    } else {
        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;
        }

        for (i = level; i < zsl->level; i++) {
            update[i]->level[i].span++;
        }

        x->backward = (update[0] == zsl->header)? NULL : update[0];
        if (x->level[0].forward)
            x->level[0].forward->backward = x;
        else
            zsl->tail = x;
        zsl->length++;
        return x;
    }
}
  1. 查找插入位置：
    • 从最高层级开始，通过while循环找到每个层级中小于待插入节点score的最后一个节点，并记录下来，同时记录跨越的节点数rank。这些记录的节点将用于后续插入新节点时更新指针。
  2. 检查节点是否已存在：
    • 如果找到的下一个节点的score和ele与待插入的相同，则说明节点已存在，直接返回该节点（在有序集合中可能会更新其他属性）。
  3. 确定新节点层级：
    • 通过zslRandomLevel函数随机生成新节点的层级。这个函数的实现通常基于一定的概率（例如，新节点有50%的概率在第1层，25%的概率在第2层，以此类推）。
    • 如果新节点的层级大于当前跳跃表的最大层级，需要更新跳跃表的层级信息，并初始化新层级的指针和跨度。
  4. 插入新节点：
    • 创建新节点，并根据之前记录的update数组更新各级指针。同时，根据rank数组计算并更新新节点各级的跨度以及前驱节点的跨度。
    • 设置新节点的backward指针，并更新后继节点的backward指针以及跳跃表的尾节点指针。最后，更新跳跃表的长度。

删除节点

删除节点在Redis中通过zslDelete函数实现，以下是简化的代码逻辑：

int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;

    x = zsl->header;
    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;
        }
        update[i] = x;
    }

    x = x->level[0].forward;
    if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
        zslDeleteNode(zsl, x, update);
        if (!zsl->header->level[0].forward)
            zsl->tail = zsl->header;
        else {
            while (zsl->level > 1 &&
                   zsl->header->level[zsl->level-1].forward == NULL)
            {
                zsl->level--;
            }
        }
        zsl->length--;
        if (node)
            *node = x;
        return 1;
    } else {
        if (node)
            *node = NULL;
        return 0;
    }
}
  1. 查找待删除节点：
    • 与插入节点类似，从最高层级开始查找待删除节点。通过while循环找到每个层级中小于待删除节点score的最后一个节点，并记录在update数组中。
  2. 判断节点是否存在：
    • 如果找到的下一个节点的score和ele与待删除的相同，则执行删除操作。
  3. 执行删除操作：
    • 通过zslDeleteNode函数实际删除节点，该函数会更新跳跃表各级指针和跨度。
    • 如果删除节点后跳跃表为空，更新尾节点指针。否则，调整跳跃表的层级，确保层级数是合理的（去除没有使用的高层级）。最后，更新跳跃表的长度。

查找节点

查找节点是跳跃表的常见操作之一，Redis中并没有单独提供一个公开的查找函数，但可以根据其插入和删除操作中的查找逻辑来理解查找过程。以下是一个简单的查找函数示例：

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

    x = zsl->header;
    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;
    }
}
  1. 层级遍历查找：
    • 从最高层级开始，通过while循环，沿着forward指针移动，跳过分值小于待查找节点分值的节点。如果分值相同，则比较ele，跳过字典序小于待查找节点的节点。
  2. 检查是否找到：
    • 到达第0层后，如果找到的下一个节点的score和ele与待查找的相同，则返回该节点，否则返回NULL。

Redis跳跃表API使用技巧

层级管理技巧

  1. 理解层级生成概率：
    • Redis跳跃表的层级生成是基于概率的，zslRandomLevel函数通常实现为新节点有50%的概率在第1层，25%的概率在第2层，12.5%的概率在第3层，以此类推。这种概率分布有助于维持跳跃表的平衡，使得查找操作的平均时间复杂度接近O(log n)。在实际应用中，如果数据量较小，可以适当调整概率，例如增加高层级的生成概率，以减少层级数，降低内存开销。
  2. 动态调整层级：
    • 在插入和删除节点时，跳跃表会动态调整层级。插入节点时，如果新节点层级大于当前跳跃表的最大层级，会增加跳跃表的层级。删除节点后，如果某些高层级不再使用，会自动降低跳跃表的层级。在设计基于跳跃表的应用时，要考虑到这种动态调整对性能的影响。例如，频繁的插入和删除操作可能导致层级频繁变化，影响性能。可以通过批量操作来减少这种影响，即一次插入或删除多个节点，减少层级调整的次数。

跨度优化

  1. 跨度的作用：
    • 跳跃表节点的跨度（span）记录了从当前节点到下一个节点之间跨越的节点数。跨度在插入和删除节点时用于更新指针和计算新的跨度值，在查找操作中也可以用于快速定位节点。例如，在查找时，如果知道当前层级的跨度，可以快速跳过一些节点，提高查找效率。
  2. 优化跨度计算：
    • 在插入和删除节点时，合理优化跨度计算可以提高性能。在插入节点时，通过记录各级的rank（即从表头到当前位置跨越的节点数），可以更高效地计算新节点各级的跨度以及前驱节点的跨度。在删除节点时，同样可以利用类似的方法更新跨度。此外，对于一些特殊场景，如果可以预先知道数据的分布情况，可以在初始化跳跃表时合理设置跨度，以进一步提高查找性能。

内存管理

  1. 节点内存分配：
    • Redis跳跃表的节点内存分配采用zmalloc函数，该函数在Redis中封装了系统的内存分配函数（如malloc），并提供了一些额外的功能，如内存分配统计等。在使用跳跃表时，要注意节点内存的分配和释放。特别是在删除节点时，要确保释放节点占用的所有内存，包括节点结构体本身以及ele成员（如果是动态分配的字符串）。
  2. 减少内存碎片：
    • 频繁的插入和删除操作可能导致内存碎片，影响系统性能。可以通过使用内存池技术来减少内存碎片。例如，预先分配一块较大的内存，当需要创建节点时，从内存池中分配内存，删除节点时将内存归还到内存池。这样可以减少系统内存分配和释放的次数，提高内存使用效率。

应用场景优化

  1. 有序集合应用：
    • 在Redis的有序集合中，跳跃表用于存储成员及其分值，并通过跳跃表实现高效的插入、删除和查找操作。在实际应用中，如果有序集合的成员数量较少，可以考虑使用更简单的数据结构，如数组或链表，以减少内存开销。但如果成员数量较多且需要频繁进行排序相关操作，跳跃表的优势就非常明显。例如，在排行榜应用中，使用Redis的有序集合和跳跃表可以高效地实现实时排名更新和查询。
  2. 范围查询优化：
    • 跳跃表在范围查询方面具有一定的优势。由于跳跃表是有序的，可以通过从表头开始遍历，快速定位到范围的起始节点，然后逐步遍历找到范围内的所有节点。在实现范围查询时，可以根据范围的大小和数据分布情况，选择合适的层级进行遍历。例如，如果范围较小，可以从较低层级开始遍历，减少不必要的指针跳转；如果范围较大，可以从高层级开始，快速定位到大致范围，然后再从低层级精确查找。

总结

Redis跳跃表API提供了一套高效的有序数据结构操作方法。通过深入理解跳跃表的数据结构、API使用方法以及相关技巧，可以在开发基于Redis的应用时，充分发挥跳跃表的优势，实现高效的插入、删除、查找和范围查询等操作。同时，合理管理跳跃表的层级、跨度、内存等方面，也能进一步提升应用的性能和稳定性。无论是在排行榜、实时统计等场景，还是在需要有序数据管理的各种应用中，掌握Redis跳跃表API的使用方法与技巧都具有重要意义。