redis資料結構實作--跳躍表(zskiplist)
4 跳表的實作
結構圖:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLlhjNmdDOiZ2MkJzN4kjY4EGN3czNmNjYjFWZ2IDOhVWZ5EGMhBDZx8CXt92Yu4GZjlGbh5SZslmZxl3Lc9CX6MHc0RHaiojIsJye.png)
跳表由zskiplistNode和構成zskiplist構成
zskiplist結構:
header: 指向跳躍表的頭節點
tail: 指向跳躍表的尾節點
level: 跳躍表中層數最大節點的層數(表頭的層數不計入)
length: 跳表儲存的節點數(空表頭不計入)
zskiplistNode結構:
level數組:層,每次建立一個新的跳表節點都會根據幂次定律計算出level數組的大小,也就是次層的高度.
每一層帶有兩個屬性-前進指針和跨度.
前進指針用于通路表尾方向的其他指針;跨度用于記錄目前節點與前進指針所指節點的距離
backward: 後退指針,指向目前節點的前一個節點
score:分值,用來排序,如果分值相同看成員變量在字典序大小排序
obj: 成員對象是一個指針,指向一個字元串對象裡面儲存着一個sds;
在跳表中各個節點的成員對象必須唯一,分值可以相同