6、Redis系统-数据结构-06-跳表

六、跳表（Skiplist）

跳表是一种高效的动态数据结构，可以用于实现有序集合（Sorted Set，Zset）。与平衡树相比，跳表具有实现简单、效率高的优点，因此被 Redis 选用作为有序集合的底层数据结构之一。

1. 跳表的结构设计

跳表通过多级链表的形式实现，每一级链表都跳过一些元素，从而在查询时能够快速跳过不必要的元素。跳表的每个节点包含一个或多个前进指针，这些前进指针指向不同级别的节点，使得跳表具有高效的查询性能。

节点结构

跳表节点的结构定义如下：

typedef struct zskiplistNode {
    struct zskiplistNode *backward; // 后退指针，指向前一个节点
    double score;                   // 节点的分值，用于排序
    sds ele;                        // 节点的元素
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针，指向下一个节点
        unsigned int span;             // 跨度，表示当前节点和下一个节点之间的距离
    } level[]; // 按级别划分的前进指针数组
} zskiplistNode;

跳表结构

跳表的结构定义如下：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 跳表的头节点和尾节点
    unsigned long length;                // 跳表的长度，即节点数量
    int level;                           // 跳表的最大级别
} zskiplist;

2. 跳表的操作

跳表支持多种操作，包括插入、删除、查找等。以下是一些常见操作的实现示例：

插入操作

插入新节点时，首先确定新节点的级别，然后在每一级链表中找到插入位置，将新节点插入到相应的位置。

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    zskiplistNode *x;
 
    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;
    }
 
    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;
}

查找操作

在跳表中查找目标节点时，从最高级别的链表开始，通过前进指针逐级向下查找，直到找到目标节点或确认目标节点不存在。

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;
    }
}

删除操作

删除节点时，通过查找操作确定节点位置，然后在每一级链表中移除该节点，并调整相关节点的前进指针和跨度。

int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    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;
        }
        update[i] = x;
    }
 
    x = x->level[0].forward;
    if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
        for (i = 0; i < zsl->level; i++) {
            if (update[i]->level[i].forward == x) {
                update[i]->level[i].span += x->level[i].span - 1;
                update[i]->level[i].forward = x->level[i].forward;
            } else {
                update[i]->level[i].span -= 1;
            }
        }
        if (x->level[0].forward) {
            x->level[0].forward->backward = x->backward;
        } else {
            zsl->tail = x->backward;
        }
        while (zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
            zsl->level--;
        zsl->length--;
        if (node) *node = x;
        else zslFreeNode(x);
        return 1;
    } else {
        return 0;
    }
}

3. 跳表的优点

1. 高效查询：跳表的查询性能接近于平衡树，时间复杂度为 O(log N)。
2. 实现简单：与红黑树等平衡树相比，跳表的实现相对简单，容易理解和维护。
3. 动态调整：跳表能够高效地进行插入和删除操作，同时保持整体结构的有序性。

4. 跳表的使用示例

以下是一些使用 Redis 跳表实现有序集合的示例，展示了如何利用跳表进行数据的存储和操作。

插入数据

ZADD myzset 1 "one"
ZADD myzset 2 "two"
ZADD myzset 3 "three"

获取数据

ZRANGE myzset 0 -1 WITHSCORES
# 1) "one"
# 2) "1"
# 3) "two"
# 4) "2"
# 5) "three"
# 6) "3"

删除数据

ZREM myzset "two"
ZRANGE myzset 0 -1 WITHSCORES
# 1) "one"
# 2) "1"
# 3) "three"
# 4) "3"

结论

通过上述解析，我们可以更好地理解跳表的设计思想和实现原理，从而在实际开发中更好地利用跳表提供的优势。在 Redis 中，跳表通过高效的多级链表结构，实现了有序集合的快速插入、删除和查询操作，适用于需要有序数据存储的场景。了解跳表的内部实现，可以帮助我们在实际应用中更好地利用 Redis 的性能和功能。