天天看點

redis資料結構實作--跳躍表(zskiplist)

redis資料結構實作--跳躍表(zskiplist)

4 跳表的實作

結構圖:

redis資料結構實作--跳躍表(zskiplist)

跳表由zskiplistNode和構成zskiplist構成

zskiplist結構:

header: 指向跳躍表的頭節點
    tail: 指向跳躍表的尾節點
    level: 跳躍表中層數最大節點的層數(表頭的層數不計入)
    length: 跳表儲存的節點數(空表頭不計入)           

zskiplistNode結構:

level數組:層,每次建立一個新的跳表節點都會根據幂次定律計算出level數組的大小,也就是次層的高度.
每一層帶有兩個屬性-前進指針和跨度.
前進指針用于通路表尾方向的其他指針;跨度用于記錄目前節點與前進指針所指節點的距離
   backward: 後退指針,指向目前節點的前一個節點
   score:分值,用來排序,如果分值相同看成員變量在字典序大小排序
   obj: 成員對象是一個指針,指向一個字元串對象裡面儲存着一個sds;
            在跳表中各個節點的成員對象必須唯一,分值可以相同           

繼續閱讀