快捷導(dǎo)航

redis中跳表zset的具體使用

更新時(shí)間：2024年01月15日 09:40:48 作者：大牛寫(xiě)代碼

Redis跳表zset是一種結(jié)合了跳表和有序集合的高效數(shù)據(jù)結(jié)構(gòu),適用于實(shí)現(xiàn)排序和大規(guī)模數(shù)據(jù)的快速查詢,本文主要介紹了redis中跳表zset的具體使用,感興趣的可以了解一下

跳表的基本思想

Skip List(跳躍列表)這種隨機(jī)的數(shù)據(jù)結(jié)構(gòu)，可以看做是一個(gè)二叉樹(shù)的變種，它在性能上與紅黑樹(shù)、AVL樹(shù)很相近；但是Skip List(跳躍列表)的實(shí)現(xiàn)相比前兩者要簡(jiǎn)單很多，目前Redis的zset實(shí)現(xiàn)采用了Skip List(跳躍列表)。

在這里插入圖片描述

特點(diǎn)

1、分層，每層由有序鏈表構(gòu)成
2、頭節(jié)點(diǎn)在每層出現(xiàn)
3、某個(gè)節(jié)點(diǎn)如果在上層出現(xiàn)，那在下層也出現(xiàn)
4、節(jié)點(diǎn)的層數(shù)是隨機(jī)的

節(jié)點(diǎn)與結(jié)構(gòu)

跳躍表節(jié)點(diǎn)zskiplistNode

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

屬性

ele：存儲(chǔ)字符串?dāng)?shù)據(jù)
score：存儲(chǔ)排序分值
*backward：指針，指向當(dāng)前節(jié)點(diǎn)最底層的前一個(gè)節(jié)點(diǎn)
level[]：柔性數(shù)組，隨機(jī)生成1-64的值
forward：指向本層下一個(gè)節(jié)點(diǎn)
span：本層下個(gè)節(jié)點(diǎn)到本節(jié)點(diǎn)的元素個(gè)數(shù)

跳躍表鏈表

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

屬性

header，tail：頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
length：跳躍表長(zhǎng)度（不包括頭節(jié)點(diǎn)）
tail：跳躍表高度

跳表的設(shè)計(jì)思想和優(yōu)勢(shì)

1、能夠同時(shí)擁有鏈表和數(shù)優(yōu)勢(shì)的數(shù)據(jù)結(jié)構(gòu)，既有鏈表插入快的特點(diǎn)又有數(shù)組查詢快的特點(diǎn)
2、隨機(jī)跨越層數(shù)
3、最底層的鏈表是雙向鏈表，包含所有元素
4、對(duì)于有序鏈表查詢優(yōu)化，相比較于平衡數(shù)來(lái)說(shuō)，更好實(shí)現(xiàn)
5、內(nèi)存占用上來(lái)看，相比較于平衡數(shù)會(huì)更少

API解析

Tip：以下的zsl為zskiplist

zslCreate（創(chuàng)建跳躍表）

/* Create a new skiplist. */
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、定義一個(gè)zsl，申請(qǐng)內(nèi)存，賦初始值
2、調(diào)用zslCreateNode創(chuàng)建出頭節(jié)點(diǎn)
3、每層頭節(jié)點(diǎn)賦初始值
4、尾節(jié)點(diǎn)賦null值

zslCreateNode（創(chuàng)建節(jié)點(diǎn)）

/* Create a skiplist node with the specified number of levels.
 * The SDS string 'ele' is referenced by the node after the call. */
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}

大致流程：
1、申請(qǐng)內(nèi)存（節(jié)點(diǎn)內(nèi)存和柔性數(shù)組的內(nèi)存）
2、屬性賦值

zslGetRank（查找排位）

排位就是累積跨越的節(jié)點(diǎn)數(shù)量

unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x;
    unsigned long rank = 0;
    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))) {
            rank += x->level[i].span;
            x = x->level[i].forward;
        }

        /* x might be equal to zsl->header, so test if obj is non-NULL */
        if (x->ele && x->score == score && sdscmp(x->ele,ele) == 0) {
            return rank;
        }
    }
    return 0;
}

大致流程：
1、從最上層開(kāi)始遍歷節(jié)點(diǎn)并對(duì)比元素，對(duì)比score
2、如果當(dāng)前分值大雨下一個(gè)分值，則累加span（比對(duì)分值，如果分值一樣就比對(duì)ele）
3、指向本層的下一個(gè)節(jié)點(diǎn)
4、如果找到了，也就是ele相同，則返回

zslDelete（刪除節(jié)點(diǎn)）

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;
    }
    /* We may have multiple elements with the same score, what we need
     * is to find the element with both the right score and object. */
    x = x->level[0].forward;
    if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
        zslDeleteNode(zsl, x, update);
        if (!node)
            zslFreeNode(x);
        else
            *node = x;
        return 1;
    }
    return 0; /* not found */
}

大致流程：
1、遍歷跳表
2、比對(duì)分值，比對(duì)ele
3、如分值小于或等于當(dāng)前值，并且ele不相等，繼續(xù)下一個(gè)并記錄節(jié)點(diǎn)
4、如分值和ele都相同，調(diào)用zslDeleteNode刪除該節(jié)點(diǎn)

跳表是在很多排名以及分?jǐn)?shù)相關(guān)的場(chǎng)景中使用頻率極高的數(shù)據(jù)結(jié)構(gòu)，也是設(shè)計(jì)的極其巧妙的一種結(jié)構(gòu)，希望本篇文章能幫助各位更加深入的理解這種結(jié)構(gòu)。

到此這篇關(guān)于redis中跳表zset的具體使用的文章就介紹到這了,更多相關(guān)redis 跳表zset內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: