跳躍表節(jié)點

typedef struct zskiplistNode {
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
struct zskiplistNode *backward;
double score;
robj *obj;
} zskiplistNode;

1. 層

跳躍表節(jié)點的level數(shù)組可以包含多個元素,每個元素都包含一個指向其他節(jié)點的指針,程序可以通過這些層來加快訪問其他節(jié)點的速度,一般來說,層的數(shù)量越多,訪問其他節(jié)點的速度就越快。

每次創(chuàng)建一個新跳躍表節(jié)點的時候,程序都根據(jù)冪次定律(power law,越大的數(shù)出現(xiàn)的概率越?。╇S機生成一個介于1和32之間的值作為level數(shù)組的大小,這個大小就是層的“高度”。

2. 前進指針

每個層都有一個指向表尾方向的前進指針(level[i].forward屬性),用于從表頭向表尾方向訪問節(jié)點。

3. 跨度

層的跨度(level[i].span屬性)用于記錄兩個節(jié)點之間的距離:

  • 兩個節(jié)點之間的跨度越大,它們相距得就越遠。
  • 指向NULL的所有前進指針的跨度都為0,因為它們沒有連向任何節(jié)點。

初看上去,很容易以為跨度和遍歷操作有關(guān),但實際上并不是這樣,遍歷操作只使用前進指針就可以完成了,跨度實際上是用來計算排位(rank)的:在查找某個節(jié)點的過程中,將沿途訪問過的所有層的跨度累計起來,得到的結(jié)果就是目標節(jié)點在跳躍表中的排位。

4. 后退指針

節(jié)點的后退指針(backward屬性)用于從表尾向表頭方向訪問節(jié)點:跟可以一次跳多個節(jié)點的前進指針不同,因為每個節(jié)點只有一個后退指針,所以每次只能后退至前一個節(jié)點。

5. 分值和成員

節(jié)點的分值(score屬性)是一個double類型的浮點數(shù),跳躍表中的所有節(jié)點都按分值從小到大來排序。

節(jié)點的成員對象(obj屬性)是一個指針,它指向一個字符串對象,而字符串對象則保存著一個SDS值。

在同一個跳躍表中,各個節(jié)點保存的成員對象必須是唯一的,但是有多個節(jié)點保存的分值卻可以是相同的:分值相同的節(jié)點將按照成員對象在字典序的大小來進行排序,成員對象較小的節(jié)點會排在前面(靠近表頭的方向),而成員對象較大的節(jié)點則會排在后面(靠近表尾的防線)。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

  • 位于圖片最左邊的是 zskiplist 結(jié)構(gòu), 該結(jié)構(gòu)包含以下屬性,右邊是各個跳躍表節(jié)點左邊的zskiplist結(jié)...
    顏灝_2181閱讀 390評論 0 0
  • 本文為筆者對在學習Redis過程中所收集資料的一個總結(jié),目的是為了以后方便回顧相關(guān)的知識,大部分為非原創(chuàng)內(nèi)容。特此...
    EakonZhao閱讀 14,630評論 0 9
  • 國家電網(wǎng)公司企業(yè)標準(Q/GDW)- 面向?qū)ο蟮挠秒娦畔?shù)據(jù)交換協(xié)議 - 報批稿:20170802 前言: 排版 ...
    庭說閱讀 12,301評論 6 13
  • 跳躍表(zskiplist)是一種有序的數(shù)據(jù)結(jié)構(gòu),通過在一個節(jié)點中維持多個指向其他節(jié)點的指針,從而達到從當前節(jié)點快...
    舒小賤閱讀 821評論 0 1
  • 文/達文西誠 每年的農(nóng)歷十五以及清明,我才會特別記起那些有關(guān)您的日子。我的曾祖母是在她九十一歲的高齡離開的,記憶當...
    達文西誠閱讀 409評論 0 0

友情鏈接更多精彩內(nèi)容