[[332515]]

本文轉(zhuǎn)載自微信公眾號(hào)「 學(xué)習(xí)Java的小姐姐」，作者學(xué)習(xí)Java的小姐姐0618。轉(zhuǎn)載本文請(qǐng)聯(lián)系學(xué)習(xí)Java的小姐姐公眾號(hào)。

前言

hello，大家好，前面幾周我們一起看了Redis底層數(shù)據(jù)結(jié)構(gòu)，如動(dòng)態(tài)字符串SDS，雙向鏈表Adlist，字典Dict，如果有對(duì)Redis常見(jiàn)的類(lèi)型或底層數(shù)據(jù)結(jié)構(gòu)不明白的請(qǐng)看上面?zhèn)魉烷T(mén)。

今天我們來(lái)看下ZSET的底層架構(gòu)，如果不知道ZSET是什么的，可以看上面?zhèn)魉烷T(mén)第一篇。簡(jiǎn)單來(lái)說(shuō)，ZSET是Redis提供的根據(jù)數(shù)據(jù)和分?jǐn)?shù)來(lái)判斷其排名的數(shù)據(jù)結(jié)構(gòu)。最常見(jiàn)的就是微信運(yùn)動(dòng)的排名，每個(gè)用戶(hù)對(duì)應(yīng)自己的步數(shù)，每天晚上可以給出用戶(hù)的排名。

有小伙伴可能會(huì)想，如果是實(shí)現(xiàn)排名的話，各種排序方法都可以實(shí)現(xiàn)的，沒(méi)必要引入Redis的ZSET結(jié)構(gòu)啊?

當(dāng)然，如果是采用排序方法的話，是可以實(shí)現(xiàn)相同功能的，但是代碼里面需要硬編碼，會(huì)添加工作量，還會(huì)提供代碼的Bug哦，哈哈哈。而且Redis的底層是C實(shí)現(xiàn)的，直接操作內(nèi)存，速度也會(huì)比Java方法實(shí)現(xiàn)提升。

綜上，使用Redis的ZSET結(jié)構(gòu)，好處多多。那話不多說(shuō)，開(kāi)始把。在正式開(kāi)始之前，我們需要引入下跳躍表的概念，其是ZSET結(jié)構(gòu)的底層實(shí)現(xiàn)。以下可能有點(diǎn)枯燥，我盡量說(shuō)的簡(jiǎn)單點(diǎn)哈。(一定要看哦，這寫(xiě)的太累了哈)

什么是跳躍表?

對(duì)于數(shù)據(jù)量大的鏈表結(jié)構(gòu)，插入和刪除比較快，但是查詢(xún)速度卻很慢。那是因?yàn)闊o(wú)法直接獲取某個(gè)節(jié)點(diǎn)，需要從頭節(jié)點(diǎn)開(kāi)始，借助某個(gè)節(jié)點(diǎn)的next指針來(lái)獲取下一節(jié)點(diǎn)。即使數(shù)據(jù)是有序排放的，想要查詢(xún)某個(gè)數(shù)據(jù)，只能從頭到尾遍歷變量，查詢(xún)效率會(huì)很低，時(shí)間復(fù)雜度為O(n)。

如果我們需要快速查詢(xún)鏈表有啥辦法呢?有同學(xué)說(shuō)用數(shù)組存放，但是如果不改數(shù)據(jù)結(jié)構(gòu)呢?

我們可以先想想在有序數(shù)組結(jié)構(gòu)中有二分法，每次將范圍都縮小一半，這樣查詢(xún)速度提升了很多，那么在鏈表中能不能也使用這種思想。

這就到了今天講的主角——跳躍表。(一點(diǎn)也生硬的引出概念😊)

步驟一 新建有序單項(xiàng)鏈表

先看下圖有序單向鏈表，存放了1，2，3，4，5，6，7這7個(gè)元素。

步驟二 抽取二級(jí)索引節(jié)點(diǎn)

我們可以在鏈表中抽取部分節(jié)點(diǎn)，下圖抽取了1，3，5，7四個(gè)節(jié)點(diǎn)，也就是每?jī)蓚€(gè)節(jié)點(diǎn)提取了一個(gè)節(jié)點(diǎn)到上級(jí)，抽取出來(lái)的叫做索引。

注意不是每次都能抽取到這么完美，這其實(shí)就跟拋硬幣一樣，每個(gè)硬幣的正反兩面的概率是一樣的，都是1/2。當(dāng)數(shù)據(jù)量小的時(shí)候，正反的概率可能差別較大。但是隨著數(shù)據(jù)量的加大，正反的概率越來(lái)越接近于1/2。類(lèi)比過(guò)來(lái)是一個(gè)意思，每個(gè)節(jié)點(diǎn)的機(jī)會(huì)都是一樣的，要么停留原級(jí)，要么提取到上級(jí)，概率都是1/2。但是隨著節(jié)點(diǎn)數(shù)量的增加，抽取的節(jié)點(diǎn)越來(lái)越接近與1/2。

步驟三 抽取三級(jí)索引節(jié)點(diǎn)

我們可以在鏈表中抽取部分節(jié)點(diǎn)，下圖抽取了1，5兩個(gè)節(jié)點(diǎn)，也就是每?jī)蓚€(gè)節(jié)點(diǎn)提取了一個(gè)節(jié)點(diǎn)到上級(jí)，抽取出來(lái)的叫做索引。

步驟四 類(lèi)二分法查詢(xún)

我們假設(shè)要查找值為6的節(jié)點(diǎn)，先從三級(jí)索引開(kāi)始，找到值為1的節(jié)點(diǎn)，發(fā)現(xiàn)比5小，根據(jù)值為1節(jié)點(diǎn)的next指針，找到值為5的節(jié)點(diǎn)，5后面沒(méi)有其他的三級(jí)索引啦。

于是順著往下找，到了二級(jí)索引，根據(jù)值為5的節(jié)點(diǎn)的next指針找到值為7的節(jié)點(diǎn)，發(fā)現(xiàn)比6小，說(shuō)明要找到的節(jié)點(diǎn)6在此范圍內(nèi)。

再接著到了一級(jí)索引位置，根據(jù)值為5的節(jié)點(diǎn)next指針指向值為6的節(jié)點(diǎn)，發(fā)現(xiàn)是想要查詢(xún)的數(shù)據(jù)，所以查詢(xún)過(guò)程結(jié)束。

根據(jù)上面的查詢(xún)過(guò)程(下圖的藍(lán)色連線)，我們發(fā)現(xiàn)其采用的核心思想是二分法，不斷縮小查詢(xún)范圍，如果在上層索引找到區(qū)間，則順延深入到下一層找到真正的數(shù)據(jù)。

總結(jié)

從上面的整個(gè)過(guò)程中可以看出，數(shù)據(jù)量小的時(shí)候，這種拿空間換時(shí)間，消耗內(nèi)存方法的并不是最優(yōu)解。所以Redis的zset結(jié)構(gòu)在數(shù)據(jù)量小的時(shí)候采用壓縮表(這邊先放著哈，下下篇說(shuō)，立個(gè)flag)，數(shù)據(jù)量大的時(shí)候采用跳躍表。

像這種鏈表加多級(jí)索引的結(jié)構(gòu)，就是跳躍表。這名字起的形象，過(guò)程是跳躍著來(lái)查詢(xún)的。旋轉(zhuǎn)跳躍，我閉著眼，bgm響起來(lái)。

Redis中跳躍表圖解

下圖簡(jiǎn)單來(lái)說(shuō)是對(duì)跳躍表的改進(jìn)和再封裝，首先引入了表頭的概念，這與雙向鏈表，字典結(jié)構(gòu)一樣，都是對(duì)數(shù)據(jù)的封裝，因?yàn)樗麄兌际遣捎玫闹羔?，而指針必然?dǎo)致在計(jì)算長(zhǎng)度，獲取最后節(jié)點(diǎn)的數(shù)據(jù)問(wèn)題上會(huì)產(chǎn)生查詢(xún)太慢的性能問(wèn)題，所以封裝表頭是為了在這些問(wèn)題上提升速度，浪費(fèi)的只是添加，刪除等操作的時(shí)間，與此對(duì)比，是可以忽略的。

其次是引入管理所有節(jié)點(diǎn)的層數(shù)數(shù)組，我們可以看到有32層，即32個(gè)數(shù)組，這和后面的數(shù)據(jù)節(jié)點(diǎn)結(jié)構(gòu)是一樣的。引入它是為了便于直接根據(jù)此數(shù)組的層數(shù)定位到每個(gè)元素。

再其次是數(shù)據(jù)節(jié)點(diǎn)的每個(gè)level都有層級(jí)和span(也就是下圖箭頭指針上的數(shù)字，其是為了方便統(tǒng)計(jì)兩個(gè)節(jié)點(diǎn)相距多少長(zhǎng)度)。

最后就是數(shù)據(jù)節(jié)點(diǎn)的后退指針backward，引入目的是Level數(shù)組只有前指針，即只能指向下一個(gè)節(jié)點(diǎn)地址，而后退指針是為了能往回找節(jié)點(diǎn)。

上圖主要分為3大塊：(這邊大致看下就行，下面將對(duì)各模塊進(jìn)行代碼詳細(xì)解釋)

表頭

主要包括四個(gè)屬性，分別是頭指針header,尾指針tail,節(jié)點(diǎn)長(zhǎng)度length,所有節(jié)點(diǎn)的最大level。

header：指向跳躍表的表頭節(jié)點(diǎn)，通過(guò)這個(gè)指針地址可以直接找到表頭，時(shí)間復(fù)雜度為O(1)。

tail：指向跳躍表的表尾節(jié)點(diǎn)，通過(guò)這個(gè)指針可以直接找到表尾，時(shí)間復(fù)雜度為O(1)。

length：記錄跳躍表的長(zhǎng)度，即不包含表頭節(jié)點(diǎn)，整個(gè)跳躍表中有多少個(gè)元素。

level：記錄當(dāng)前跳躍表內(nèi)，所有節(jié)點(diǎn)層數(shù)最大的level(排除表頭節(jié)點(diǎn))。

管理所有節(jié)點(diǎn)層數(shù)level的數(shù)組

其對(duì)象值為空，level數(shù)組為32層，目的是為了管理真正的數(shù)據(jù)節(jié)點(diǎn)。關(guān)于具體的level有哪些屬性放在數(shù)據(jù)節(jié)點(diǎn)來(lái)說(shuō)。

數(shù)據(jù)節(jié)點(diǎn)

主要包括四個(gè)屬性對(duì)象值obj，分?jǐn)?shù)score，后退指針backward和level數(shù)組。每個(gè)數(shù)據(jù)的Level數(shù)組有多少層，是隨機(jī)產(chǎn)生的，這跟上面說(shuō)過(guò)的跳躍表是一樣的。

成員對(duì)象obj：真正的實(shí)際數(shù)據(jù)，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)都是唯一的，但是節(jié)點(diǎn)的分?jǐn)?shù)可能相同。兩個(gè)相同分?jǐn)?shù)的節(jié)點(diǎn)是按照成員對(duì)象在字典中的大小進(jìn)行排序的，成員對(duì)象較小的節(jié)點(diǎn)會(huì)排在前面，成員對(duì)象較大的節(jié)點(diǎn)會(huì)排在后面。

分?jǐn)?shù)score:各個(gè)節(jié)點(diǎn)中的數(shù)字是節(jié)點(diǎn)所保存的分?jǐn)?shù)，在跳躍表中，節(jié)點(diǎn)按各自所保存的分?jǐn)?shù)從小到大排列。

后退指針backward:用于從表尾向表頭遍歷，每個(gè)節(jié)點(diǎn)只有一個(gè)后退指針，即每次只能后退一步。

層級(jí)level：節(jié)點(diǎn)中用1，2，3等字樣標(biāo)記節(jié)點(diǎn)的各個(gè)層，L1代表第一層，L2代表第二層，L3代表第三層，并以此類(lèi)推。

跳躍表的定義

表頭結(jié)構(gòu)zskiplist

typedef struct zskiplist { 
    //表頭的頭指針header和尾指針tail 
    struct zskiplistNode *header, *tail; 
    //一共有多少個(gè)節(jié)點(diǎn)length 
    unsigned long length; 
    // 所有節(jié)點(diǎn)最大的層級(jí)level 
   int level; 
} zskiplist; 

具體數(shù)據(jù)節(jié)點(diǎn)zskiplistNode

//跳表的具體節(jié)點(diǎn) 
typedef struct zskiplistNode { 
    sds ele; //具體的數(shù)據(jù)，對(duì)應(yīng)張三 
    double score;//分?jǐn)?shù)，對(duì)應(yīng)70 
    struct zskiplistNode *backward;//后退指針backward 
     //層級(jí)數(shù)組    struct zskiplistLevel { 
        struct zskiplistNode *forward;//前進(jìn)指針forward 
        unsigned int span;//跨度span 
    } level[]; 
} zskiplistNode; 

跳躍表的實(shí)現(xiàn)(源碼分析)

redis關(guān)于跳躍表的API都定義在t_zset.c文件中。

千萬(wàn)不要看到源碼分析就跑開(kāi)了，一定要看哦。

創(chuàng)建跳躍表

創(chuàng)建空的跳躍表，其實(shí)就是創(chuàng)建表頭和管理所有的節(jié)點(diǎn)的level數(shù)組。首先，定義一些變量，嘗試分配內(nèi)存空間。其次是初始化表頭的level和length，分別賦值1和0。接著創(chuàng)建管理所有節(jié)點(diǎn)的Level的數(shù)組，是調(diào)用zslCreateNode函數(shù)，輸入?yún)?shù)為數(shù)組大小宏常量ZSKIPLIST_MAXLEVEL(32)，分?jǐn)?shù)為0，對(duì)象值為NULL。(此為跳躍表得以實(shí)現(xiàn)重點(diǎn))。再接著就是為此數(shù)組每個(gè)元素的前指針forword和跨度span初始化。最后初始化尾指針并返回值。

可以參照下面的圖解和源碼：

//創(chuàng)建一個(gè)空表頭的跳躍表 
zskiplist *zslCreate(void) { 
    int j; 
    zskiplist *zsl; 
    //嘗試分配內(nèi)存空間 
    zsl = zmalloc(sizeof(*zsl)); 
    //初始化level和length 
    zsl->level = 1; 
    zsl->length = 0; 
    //調(diào)用下面的方法zslCreateNode,傳入的參數(shù)有數(shù)組長(zhǎng)度ZSKIPLIST_MAXLEVEL 32 
    //分?jǐn)?shù)0，對(duì)象值NuLL 
    //這一步就是創(chuàng)建管理所有節(jié)點(diǎn)的數(shù)組 
    //并且設(shè)置表頭的頭頭指針為此對(duì)象的地址 
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); 
    //為這32個(gè)數(shù)組賦值前指針forward和跨度span 
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) { 
        zsl->header->level[j].forward = NULL; 
        zsl->header->level[j].span = 0; 
    } 
    //設(shè)置尾指針 
    zsl->header->backward = NULL; 
    zsl->tail = NULL; 
    //返回對(duì)象 
    return zsl; 
} 

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

插入節(jié)點(diǎn)

比如有下圖6個(gè)元素，需要插入值為趙六，分?jǐn)?shù)為101的元素，我們大致想一想，大致的步驟包括找到要插入的位置，新建一個(gè)數(shù)據(jù)節(jié)點(diǎn)，然后調(diào)整與之相關(guān)的頭尾指針的level數(shù)組。那就看看redis咋做的，和我們想的一樣不一樣呢?

噔噔噔噔，答案揭曉。當(dāng)然了大框架是相同的。

正文開(kāi)始了：(先來(lái)圖片)

1.遍歷管理所有節(jié)點(diǎn)的level數(shù)組，從最大的level開(kāi)始，即3，挨個(gè)對(duì)比值，如果有分?jǐn)?shù)比他大的值或者分?jǐn)?shù)相同，但是數(shù)據(jù)的值比他大，記錄到數(shù)組里面，同時(shí)記錄跨度。

這樣說(shuō)太抽象了。拿上圖舉個(gè)例子，從表頭的level即3開(kāi)始，首先到張三的L3，發(fā)現(xiàn)分?jǐn)?shù)70，比目標(biāo)分?jǐn)?shù)101小跳過(guò)，根據(jù)其前指針找到趙六的L3,發(fā)現(xiàn)分?jǐn)?shù)102，比目標(biāo)分?jǐn)?shù)101大，將趙六L3記錄在待更新數(shù)組update中，同時(shí)記錄跨度span為4。接著到下一層，張三的L2層，發(fā)現(xiàn)分?jǐn)?shù)70比目標(biāo)分?jǐn)?shù)101小跳過(guò)，根據(jù)前指針找到王五的L2，發(fā)現(xiàn)分?jǐn)?shù)90，比目標(biāo)分?jǐn)?shù)101小跳過(guò)，根據(jù)前指針找到趙六的L2，發(fā)現(xiàn)分?jǐn)?shù)102比目標(biāo)分?jǐn)?shù)101大，將趙六的L2記錄到待更新數(shù)組update中，同時(shí)記錄跨度span為2。最后到下一層，張三的L1層，邏輯和剛才一樣的，也是記錄趙六的L1層和跨度span為1。

2.為新節(jié)點(diǎn)隨機(jī)生成層級(jí)數(shù)level(通過(guò)位運(yùn)算)，如果生成的level大于目前l(fā)evel最大值3，則將將大于部分挨個(gè)遍歷，并將跨度等信息記錄到上面update表中。

比如，新節(jié)點(diǎn)生成的level為5，目前l(fā)evel最大值為3，說(shuō)明這個(gè)節(jié)點(diǎn)只會(huì)有一個(gè)，并且跨越了之前的所有節(jié)點(diǎn)，那么我們將從第四層和第五層都遍歷下，記錄到待更新數(shù)組update中。

3.準(zhǔn)備工作都做好了，找到了該節(jié)點(diǎn)將插入到哪一位置，處于哪一層，每層對(duì)應(yīng)的跨度是多少，下面就要新增數(shù)據(jù)節(jié)點(diǎn)了。把上兩步的信息都添加到新節(jié)點(diǎn)上，并且調(diào)整位置前后指針即可。

4.最后就是一些收尾工作，比如修改表頭的層級(jí)level，節(jié)點(diǎn)大小length和尾指針tail等屬性。

綜上，整個(gè)流程就已經(jīng)結(jié)束了?？赡芸粗悬c(diǎn)復(fù)雜，可以對(duì)照下面代碼來(lái)。

//插入節(jié)點(diǎn)，輸入?yún)?shù)為 
//zsl:表頭 
//score:插入元素的分?jǐn)?shù)score 
//ele:插入元素的具體數(shù)據(jù)ele 
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { 
    //使用update數(shù)組記錄每層待插入元素的前一個(gè)元素 
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; 
    //記錄前置節(jié)點(diǎn)與第一個(gè)節(jié)點(diǎn)之間的跨度，即元素在列表中的排名-1 
    unsigned int rank[ZSKIPLIST_MAXLEVEL]; 
    int i, level; 
 
    serverAssert(!isnan(score)); 
    x = zsl->header; 
    //從最大的level開(kāi)始遍歷，從頂?shù)降?，找到每一層待插入的位?nbsp;
    for (i = zsl->level-1; i >= 0; i--) { 
        /* store rank that is crossed to reach the insert position */ 
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; 
    //直接找到第一個(gè)分?jǐn)?shù)比該元素大的位置 
    //或者分?jǐn)?shù)與該元素相同但是對(duì)象的ASSICC碼比該元素大的位置 
        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))) 
        { 
            //將已走過(guò)元素的跨越元素進(jìn)行計(jì)數(shù)，得到元素在列表中排名，或者是已搜尋的路徑長(zhǎng)度 
            rank[i] += x->level[i].span; 
            x = x->level[i].forward; 
        } 
    //記錄待插入位置 
        update[i] = x; 
    } 
     //隨機(jī)產(chǎn)生一個(gè)層數(shù)，在1到32之間，層數(shù)越高，生成的概率越低 
    level = zslRandomLevel(); 
    //如果產(chǎn)生的層數(shù)大于現(xiàn)有的最高層數(shù)，則超出層數(shù)都需要初始化 
    if (level > zsl->level) { 
        //開(kāi)始循環(huán) 
        for (i = zsl->level; i < level; i++) { 
            rank[i] = 0; 
            //該元素作為這些層的第一個(gè)節(jié)點(diǎn)，前節(jié)點(diǎn)就是header 
            update[i] = zsl->header; 
            //初始化后這些層每層有兩個(gè)元素，走一步就是跨越所有元素 
            update[i]->level[i].span = zsl->length; 
        } 
        zsl->level = level; 
    } 
    //創(chuàng)建節(jié)點(diǎn) 
    x = zslCreateNode(level,score,ele); 
    for (i = 0; i < level; i++) { 
        //將新節(jié)點(diǎn)插入到各層鏈表中 
        x->level[i].forward = update[i]->level[i].forward; 
        update[i]->level[i].forward = x; 
 
        // rank[0]是第0層的前置節(jié)點(diǎn)P1（也就是底層插入節(jié)點(diǎn)前面那個(gè)節(jié)點(diǎn)）與第一個(gè)節(jié)點(diǎn)的跨度 
        // rank[i]是第i層的前置節(jié)點(diǎn)P2（這一層里在插入節(jié)點(diǎn)前面那個(gè)節(jié)點(diǎn)）與第一個(gè)節(jié)點(diǎn)的跨度 
        // 插入節(jié)點(diǎn)X與后置節(jié)點(diǎn)Y的跨度f(wàn)(X,Y)可由以下公式計(jì)算 
        // 關(guān)鍵在于f(P1,0)-f(P2,0)+1等于新節(jié)點(diǎn)與P2的跨度，這是因?yàn)榭缍瘸噬刃涡蜗蛳卵由斓阶畹讓?nbsp;
        // 記錄節(jié)點(diǎn)各層跨越元素情況span, 由層與層之間的跨越元素總和rank相減而得 
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]); 
               // 插入位置前一個(gè)節(jié)點(diǎn)的span在原基礎(chǔ)上加1即可(新節(jié)點(diǎn)在rank[0]的后一個(gè)位置) 
 
 update[i]->level[i].span = (rank[0] - rank[i]) + 1; 
    } 
 
    /* increment span for untouched levels */ 
    for (i = level; i < zsl->level; i++) { 
        update[i]->level[i].span++; 
    } 
    // 第0層是雙向鏈表, 便于redis常支持逆序類(lèi)查找 
    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; 
} 
 
 
 
 
 
 
 
 
int zslRandomLevel(void) { 
    int level = 1; 
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) 
        level += 1; 
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; 
} 

獲取節(jié)點(diǎn)排名

擔(dān)心大家忘了這張圖，再粘貼一遍。如下圖，這部分邏輯比較簡(jiǎn)單，就不寫(xiě)了，具體參考代碼分析。

//得到節(jié)點(diǎn)的排名 
//輸入?yún)?shù)為表頭結(jié)構(gòu)zsl，分?jǐn)?shù)score，真正的數(shù)據(jù)ele 
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) { 
    zskiplistNode *x; 
    unsigned long rank = 0; 
    int i; 
    //先獲取表頭的頭指針，即找到管理所有節(jié)點(diǎn)的level數(shù)組 
    x = zsl->header; 
     //從表頭的level，即最大值開(kāi)始循環(huán)遍歷 
    for (i = zsl->level-1; i >= 0; i--) { 
        //如果找到分?jǐn)?shù)小于目標(biāo)分?jǐn)?shù)的，排名加上其跨度 
        //或者分?jǐn)?shù)相同，但是具體數(shù)據(jù)小于目標(biāo)數(shù)據(jù)的，排名也加上跨度 
        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; 
        } 
 
        //確保在第i層找到分值相同，且對(duì)象相同時(shí)才會(huì)返回排位值 
        if (x->ele && sdscmp(x->ele,ele) == 0) { 
            return rank; 
        } 
    } 
    return 0; 
} 

結(jié)語(yǔ)

該篇主要講了Redis的ZSET數(shù)據(jù)類(lèi)型的底層實(shí)現(xiàn)跳躍表，先從跳躍表是什么，引出跳躍表的概念和數(shù)據(jù)結(jié)構(gòu)，剖析了其主要組成部分，進(jìn)而通過(guò)多幅過(guò)程圖解釋了Redis是如何設(shè)計(jì)跳躍表的，最后結(jié)合源碼對(duì)跳躍表進(jìn)行描述，如創(chuàng)建過(guò)程，添加節(jié)點(diǎn)過(guò)程，獲取某個(gè)節(jié)點(diǎn)排名過(guò)程，中間穿插例子和過(guò)程圖。

如果覺(jué)得寫(xiě)得還行，麻煩給個(gè)贊👍，您的認(rèn)可才是我寫(xiě)作的動(dòng)力!

如果覺(jué)得有說(shuō)的不對(duì)的地方，歡迎評(píng)論指出。

好了，拜拜咯。

原文鏈接：https://mp.weixin.qq.com/s/EDGrGabrdorgKUdaw6OK5A