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)的概率越忻础)隨機(jī)生成一個介于1和32之間的值作為level數(shù)組的大小,這個大小就是層的“高度”烫映。
2. 前進(jìn)指針
每個層都有一個指向表尾方向的前進(jìn)指針(level[i].forward屬性)沼本,用于從表頭向表尾方向訪問節(jié)點。
3. 跨度
層的跨度(level[i].span屬性)用于記錄兩個節(jié)點之間的距離:
- 兩個節(jié)點之間的跨度越大锭沟,它們相距得就越遠(yuǎn)抽兆。
- 指向NULL的所有前進(jìn)指針的跨度都為0,因為它們沒有連向任何節(jié)點族淮。
初看上去辫红,很容易以為跨度和遍歷操作有關(guān),但實際上并不是這樣瞧筛,遍歷操作只使用前進(jìn)指針就可以完成了厉熟,跨度實際上是用來計算排位(rank)的:在查找某個節(jié)點的過程中,將沿途訪問過的所有層的跨度累計起來较幌,得到的結(jié)果就是目標(biāo)節(jié)點在跳躍表中的排位揍瑟。
4. 后退指針
節(jié)點的后退指針(backward屬性)用于從表尾向表頭方向訪問節(jié)點:跟可以一次跳多個節(jié)點的前進(jìn)指針不同,因為每個節(jié)點只有一個后退指針乍炉,所以每次只能后退至前一個節(jié)點绢片。
5. 分值和成員
節(jié)點的分值(score屬性)是一個double類型的浮點數(shù)滤馍,跳躍表中的所有節(jié)點都按分值從小到大來排序。
節(jié)點的成員對象(obj屬性)是一個指針底循,它指向一個字符串對象巢株,而字符串對象則保存著一個SDS值。
在同一個跳躍表中熙涤,各個節(jié)點保存的成員對象必須是唯一的阁苞,但是有多個節(jié)點保存的分值卻可以是相同的:分值相同的節(jié)點將按照成員對象在字典序的大小來進(jìn)行排序,成員對象較小的節(jié)點會排在前面(靠近表頭的方向)祠挫,而成員對象較大的節(jié)點則會排在后面(靠近表尾的防線)那槽。