男人的av一区二区资源,亚洲日韩国产精品无码av,蜜桃久久久aaaa成人网一区,亚洲日韩中文字幕一区,在线观看国产亚洲视频免费

簡(jiǎn)介

跳躍表將有序鏈表中的部分節點(diǎn)分層，每一層都是一個(gè)有序鏈表。在查找時(shí)優(yōu)先從最高層開(kāi)始向后查找，當到達某節點(diǎn)時(shí)，如果next節點(diǎn)值大于要查找的值或next指針指向NULL，則從當前節點(diǎn)下降一層繼續向后查找，這樣可以有效提升效率。如下圖所示使用跳表查找51的路徑為1->21->41->51需要查找4次。如果使用鏈表查找路徑為1->11->21->31->41->51需要查找6次，效率明顯提升了，當數據量較大是提升更為明顯。

跳躍表的實(shí)現過(guò)程下圖所示：

• 跳躍表由很多層構成。
• 跳躍表有一個(gè)頭（header）節點(diǎn)，頭節點(diǎn)中有一個(gè)64層的結構，每層的結構包含指向本層的下個(gè)節點(diǎn)的指針，指向本層下個(gè)節點(diǎn)中間所跨越的節點(diǎn)個(gè)數為本層的跨度（span）。
• 除頭節點(diǎn)外，層數最多的節點(diǎn)的層高為跳躍表的高度（level），上圖中跳躍表的高度為3。
• 每層都是一個(gè)有序鏈表，數據遞增。
• 除header節點(diǎn)外，一個(gè)元素在上層有序鏈表中出現，則它一定會(huì )在下層有序鏈表中出現。
• 跳躍表每層最后一個(gè)節點(diǎn)指向NULL，表示本層有序鏈表的結束。
• 跳躍表?yè)碛幸粋€(gè)tail指針，指向跳躍表最后一個(gè)節點(diǎn)。
• 最底層的有序鏈表包含所有節點(diǎn)，最底層的節點(diǎn)個(gè)數為跳躍表的長(cháng)度（length）（不包括頭節點(diǎn)）。
• 每個(gè)節點(diǎn)包含一個(gè)后退指針，頭節點(diǎn)和第一個(gè)節點(diǎn)指向NULL；其他節點(diǎn)指向最底層的前一個(gè)節點(diǎn)。

跳躍表每個(gè)節點(diǎn)維護了多個(gè)指向其他節點(diǎn)的指針，所以在跳躍表進(jìn)行查找、插入、刪除操作時(shí)可以跳過(guò)一些節點(diǎn)，快速找到操作需要的節點(diǎn)。歸根結底，跳躍表是以犧牲空間的形式來(lái)達到快速查找的目的。

跳躍表數據結構

跳躍表由多個(gè)節點(diǎn)構成，每個(gè)節點(diǎn)由很多層構成，每層都有指向本層下個(gè)節點(diǎn)的指針，接下來(lái)講述跳躍表的數據結構。

跳躍表節點(diǎn)結構

下面我們來(lái)看跳躍表節點(diǎn)的zskiplistNode結構體:

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

• ele：用于存儲字符串類(lèi)型的數據。
• score：用于存儲排序的分值（todo：分值計算方法）。
• backward：后退指針，只能指向當前節點(diǎn)最底層的前一個(gè)節點(diǎn)，頭節點(diǎn)和第一個(gè)節點(diǎn)——backward指向NULL，從后向前遍歷跳躍表時(shí)使用。
• level：為柔性數組。每個(gè)節點(diǎn)的數組長(cháng)度不一樣，在生成跳躍表節點(diǎn)時(shí)，隨機生成一個(gè)1～64的值，值越大出現的概率越低。level數組的每項包含以下兩個(gè)元素。
• forward：指向本層下一個(gè)節點(diǎn)，尾節點(diǎn)的forward指向NULL。
• span：forward指向的節點(diǎn)與本節點(diǎn)之間的元素個(gè)數。span值越大，跳過(guò)的節點(diǎn)個(gè)數越多。

跳躍表是Redis有序集合的底層實(shí)現方式之一，所以每個(gè)節點(diǎn)的ele存儲有序集合的成員member值，score存儲成員score值。所有節點(diǎn)的分值是按從小到大的方式排序的，當有序集合的成員分值相同時(shí)，節點(diǎn)會(huì )按member的字典序進(jìn)行排序。

跳躍表結構

除了跳躍表節點(diǎn)外，還需要一個(gè)跳躍表結構來(lái)管理節點(diǎn)，Redis使用zskiplist結構體，定義如下：

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

• header：指向跳躍表頭節點(diǎn)。頭節點(diǎn)是跳躍表的一個(gè)特殊節點(diǎn)，它的level數組元素個(gè)數為64。頭節點(diǎn)在有序集合中不存儲任何member和score值，ele值為NULL，score值為0；也不計入跳躍表的總長(cháng)度。頭節點(diǎn)在初始化時(shí)，64個(gè)元素的forward都指向NULL，span值都為0。
• tail：指向跳躍表尾節點(diǎn)。
• length：跳躍表長(cháng)度，表示除頭節點(diǎn)之外的節點(diǎn)總數。
• level：跳躍表的高度。

通過(guò)跳躍表結構體的屬性我們可以看到，程序可以在O(1)的時(shí)間復雜度下,快速獲取到跳躍表的頭節點(diǎn)、尾節點(diǎn)、長(cháng)度和高度。

跳躍表基本操作

創(chuàng )建跳躍

節點(diǎn)層高計算

節點(diǎn)層高的最小值為1，最大值是ZSKIPLIST_MAXLEVEL，Redis 5節點(diǎn)層高的值為64。Redis 6、Redis 7版本節點(diǎn)最高層數為32。官方設計的skiplist最大可以容納2^64個(gè)元素，在函數zslRandomLevel中，ZSKIPLIST_P=0.25，則skiplist最大可以容納4^64個(gè)元素，存在大量的空間浪費，所以將ZSKIPLIST_MAXLEVEL調整為32，減少資源浪費。具體原因可以閱讀下面PR：Pull Request #6818 · redis/redis

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */

Redis通過(guò)函數zslRandomLevel函數隨機生成一個(gè)1-32的值，作為新節點(diǎn)的高度。值越大出現的概率越低。節點(diǎn)層高確定之后便不會(huì )再修改。生成層高的函數實(shí)現如下：

#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
int zslRandomLevel(void) {
    /* 計算閾值 */
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1; 
    /* 當隨機數小于閾值時(shí)，level 繼續增加 */
    while (random() < threshold)
        level += 1;
    /* 返回 level，同時(shí)做不要讓 level 大于最大層數的操作 */
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

上面代碼中，level默認為1，通過(guò)while循環(huán)，當產(chǎn)生的隨機數小于RAND_MAX的最大值的0.25倍時(shí)，level的值+1；否則退出循環(huán)，最后返回的level值在1-ZSKIPLIST_MAXLEVEL之間。由zslRandomLevel函數的實(shí)現可以得出下面結論：

• level在第1層的概率為1-p。
• level在第2層的概率為p(1-p)。
• level在第3層的概率為p^2 (1-p)。
• level在第3層的概率為p^k (1-p)。

初始化表節點(diǎn)

跳躍表的每個(gè)節點(diǎn)都是由有序的元素集合。在初始化時(shí)，每個(gè)節點(diǎn)的層高、score、ele都已經(jīng)確定，對于每個(gè)跳躍表節點(diǎn)我們都需要進(jìn)行申請內存，進(jìn)行初始化。初始化代碼如下：

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

在創(chuàng )建節點(diǎn)的時(shí)候會(huì )申請大小為:zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel)) 大小的內存，用于存儲數據。申請內存時(shí)需要指定zskiplistNode 柔性數組的大小，根據柔性數組的大小申請內存。
頭節點(diǎn)時(shí)比較特殊的節點(diǎn)，頭節點(diǎn)的backward指向NULL，初始化的時(shí)候，由于頭節點(diǎn)為第一個(gè)節點(diǎn)，forward為NULL。span為0。初始化代碼如下：

for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
     zsl->header->level[j].forward = NULL;
     zsl->header->level[j].span = 0;
}

創(chuàng )建跳躍表

創(chuàng )建跳躍表的步驟如下：

• 申請跳躍表內存，申請結構體zskiplist 大小的內存。
• 初始化頭節點(diǎn)，具體參考【初始化表節點(diǎn)】。
• 初始化其他信息：長(cháng)度為0；backward為NULL；tail為NULL；

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

插入節點(diǎn)

插入節點(diǎn)是跳表最常見(jiàn)的操作，主要操作流程如下：查找插入位置；調整跳表高度；創(chuàng )建跳表節點(diǎn)，插入新節點(diǎn)；調整backward等；

查找插入位置

查找是跳躍表最常見(jiàn)的操作，主要查找邏輯已經(jīng)在基本操作里面講了，主要代碼實(shí)現如下：

/* 從最高層向下查找插入位置 */
for (i = zsl->level-1; i >= 0; i--) {
     /* rank 存儲到達插入位置而跨越的節點(diǎn)數 */
     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;存儲到達插入位置而跨越的節點(diǎn)數
         x = x->level[i].forward;
     }
     update[i] = x;
 }

為了找到要更新的節點(diǎn)，我們需要以下兩個(gè)長(cháng)度為64的數組來(lái)輔助：

• update[]: 插入節點(diǎn)時(shí)，需要更新被插入節點(diǎn)每層的前一個(gè)節點(diǎn)由于每層更新的節點(diǎn)不一樣，所以將每層需要更新的節點(diǎn)記錄在update[i]中。
• rank[]:記錄當前層從header節點(diǎn)到update[i]節點(diǎn)跨越的步長(cháng)，在更新update[i]的span和設置新插入節點(diǎn)的span時(shí)用到。

如上圖所示跳躍表：長(cháng)度為3，高度為2。想要插入一個(gè)節點(diǎn)，分值為35，層高為3。查找過(guò)程如下：
更新后的rank和update如下：

調整跳表高度

插入節點(diǎn)的高度是隨機的，假設要插入節點(diǎn)的高度為3，大于跳躍表的高度2，所以我們需要調整跳躍表的高度。代碼如下：

/* 獲取隨機最高層數 */
level = zslRandomLevel();
/* 隨機獲取的 level 比跳表原來(lái)的 level 大，則在比原來(lái) level 高的層級上初始化 rank 和 update  */
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;
    }
    /* 將跳表的 level(最高層數) 替換為隨機獲取到的 level */
    zsl->level = level;
 }

調整高度后的跳躍表如下圖所示：

創(chuàng )建跳表及插入節點(diǎn)

當update和rank都賦值且節點(diǎn)已創(chuàng )建好后，便可以插入節點(diǎn)了。創(chuàng )建節點(diǎn)代碼如下：

/* 創(chuàng  )建一個(gè)具有指定層數的跳表節點(diǎn), SDS字符串 'ele' 在調用后被節點(diǎn)引用 */
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;
}

插入節點(diǎn)的代碼如下：

/* 插入新節點(diǎn) */
for (i = 0; i < level; i++) {
    x->level[i].forward = update[i]->level[i].forward;
    update[i]->level[i].forward = x;
    /* 更新 update[i] 所涵蓋的跨度，因為有新節點(diǎn)(x)被插入了 */
    /* 首先更新新節點(diǎn)的跨度 */
    x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
    /* 更新 update 的跨度 */
    update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}

插入節點(diǎn)并更新第0層后的跳躍表如下所示：

插入節點(diǎn)并更新第1層后的跳躍表如下：

插入節點(diǎn)并更新第2層后的跳躍表如下：

調整backward等

調整插入節點(diǎn)與跳表最高層之間的跨度，代碼如下：

/* 對未觸及到的層數（插入節點(diǎn)的最高層與整個(gè)跳表中最高層之間）更新跨度 */
for (i = level; i < zsl->level; i++) {
    update[i]->level[i].span++;
}

跟新backward指針，代碼如下：

x->backward = (update[0] == zsl->header) ? NULL : update[0];
    /* 設置新節點(diǎn)的下一個(gè)節點(diǎn)的后向指針，若下一個(gè)節點(diǎn)不存在，則將尾指針指向新節點(diǎn) */
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;

跳表最終結果如下：

刪除節點(diǎn)

刪除節點(diǎn)的步驟主要如下：

• 查找需要刪除的節點(diǎn)。
• 設置span和forward。

查找需要刪除的節點(diǎn)

查找需要刪除的節點(diǎn)參考查找插入位置章節。

設置span和forward

更新span代碼如下：

/* 更新 update[i] 的前向指針以及跨度 */
    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;
        }
    }

跟新forward代碼如下：

/* 更新 x（被刪除節點(diǎn)） 的下一個(gè)節點(diǎn)的后向指針，如果下一個(gè)節點(diǎn)不存在，則將尾指針指向 x 的上一個(gè)節點(diǎn) */
    if (x->level[0].forward) {
        x->level[0].forward->backward = x->backward;
    } else {
        zsl->tail = x->backward;
    }

若被刪除節點(diǎn)擁有最高的層數，則需要將跳表的最高層數下調至當前剩余節點(diǎn)中的最高層。

while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
        zsl->level--;
    zsl->length--;

設置span和forward后的跳躍表如下：

刪除跳躍表

當刪除跳躍表時(shí)，從頭節點(diǎn)的第0層開(kāi)始，通過(guò)forward指針逐步向后遍歷，每遇到一個(gè)節點(diǎn)便將釋放其內存。當所有節點(diǎn)的內存都被釋放之后，釋放跳躍表對象，即完成了跳躍表的刪除操作，代碼如下：

/* 釋放整個(gè)跳表 */
void zslFree(zskiplist *zsl) {
    zskiplistNode *node = zsl->header->level[0].forward, *next;
    /* 釋放頭指針 */
    zfree(zsl->header);
    /* 遍歷并釋放剩下的所有節點(diǎn) */
    while(node) {
        next = node->level[0].forward;
        zslFreeNode(node);
        node = next;
    }
    /* 釋放跳表結構 */
    zfree(zsl);
}

釋放指定的跳表節點(diǎn)。成員的引用 SDS字符串 也會(huì )被釋放，除非在調用此函數之前將 node->ele 設置為 NULL，代碼如下：

void zslFreeNode(zskiplistNode *node) {
    sdsfree(node->ele);
    zfree(node);
}

跳躍表的應用和優(yōu)化

應用場(chǎng)景

跳躍表主要是zset底層實(shí)現的一種，zset中字典和布局如下所示：

排行榜

有序集合經(jīng)典使用場(chǎng)景。例如視頻網(wǎng)站需要對用戶(hù)上傳的視頻做排行榜，榜單維護可能是多方面：按照時(shí)間、按照播放量、按照獲得的贊數等

帶權重的隊列

相關(guān)參數

skiplist相關(guān)的參數以及功能如下：