zset底層數(shù)據(jù)結(jié)構(gòu)-redis
點擊“藍字”，關注，置頂公眾號
每日技術(shù)干貨，第一時間送達！
zset是Redis提供的一個非常特別的數(shù)據(jù)結(jié)構(gòu)，常用作排行榜等功能，以用戶id為value，關注時間或者分數(shù)作為score進行排序。與其他數(shù)據(jù)結(jié)構(gòu)相似，zset也有兩種不同的實現(xiàn)，分別是zipList和skipList。zipList前面我們已經(jīng)介紹過了，這里就不再介紹了。具體使用哪種結(jié)構(gòu)進行存儲，規(guī)則如下：
zipList：滿足以下兩個條件[score,value]鍵值對數(shù)量少于128個；每個元素的長度小于64字節(jié)；
skipList：不滿足以上兩個條件時使用跳表、組合了hash和skipListhash用來存儲value到score的映射，這樣就可以在O(1)時間內(nèi)找到value對應的分數(shù)；skipList按照從小到大的順序存儲分數(shù)skipList每個元素的值都是[socre,value]對
使用zipList的示意圖如下所示：
使用跳表時的示意圖：
1、跳表 skipList
跳表skipList在Redis中的運用場景只有一個，那就是作為有序列表zset的底層實現(xiàn)。跳表可以保證增、刪、查等操作時的時間復雜度為O(logN)，這個性能可以與平衡樹相媲美，但實現(xiàn)方式上卻更加簡單，唯一美中不足的就是跳表占用的空間比較大，其實就是一種空間換時間的思想。跳表的結(jié)構(gòu)如下所示：
Redis中跳表一個節(jié)點最高可以達到64層，一個跳表中最多可以存儲2^64個元素。跳表中，每個節(jié)點都是一個skiplistNode，
每個跳表的節(jié)點也都會維護著一個score值，這個值在跳表中是按照從小到大的順序排列好的。
跳表的結(jié)構(gòu)定義如下所示：
typedf struct zskiplist{
//頭節(jié)點
struct zskiplistNode *header;
//尾節(jié)點
struct zskiplistNode *tail;
// 跳表中元素個數(shù)
unsigned long length;
//目前表內(nèi)節(jié)點的最大層數(shù)
int level;
}zskiplist;header：指向跳表的頭節(jié)點，通過這個指針可以直接找到表頭，時間復雜度為O(1)；
tail：指向跳表的尾節(jié)點，通過這個指針可以直接找到表尾，時間復雜度為o(1)；
length：記錄跳表的長度，即不包括頭節(jié)點，整個跳表中有多少個元素；
level：記錄當前跳表內(nèi)，所有節(jié)點中層數(shù)最大的level；
zskiplist的示意圖如下所示：
zskiplistNode的結(jié)構(gòu)定義如下：
typedf struct zskiplistNode{
sds ele;// 具體的數(shù)據(jù)
double score;// 分數(shù)
struct zskiplistNode *backward;//后退指針
struct zskiplistLevel{
struct zskiplistNode *forward;//前進指針forward
unsigned int span;//跨度span
}level[];//層級數(shù)組 最大32
}zskiplistNode;ele：真正的數(shù)據(jù)，每個節(jié)點的數(shù)據(jù)都是唯一的，但節(jié)點的分數(shù)score可以是一樣的。兩個相同分數(shù)score的節(jié)點是按照元素的字典序進行排列的；
score：各個節(jié)點中的數(shù)字是節(jié)點所保存的分數(shù)score，在跳表中，節(jié)點按照各自所保存的分數(shù)從小到大排列；
backward：用于從表尾向表頭遍歷，每個節(jié)點只有一個后退指針，即每次只能后退一步；
層級數(shù)組：這個數(shù)組中的每個節(jié)點都有兩個屬性，forward指向下一個節(jié)點，span跨度用來計算當前節(jié)點在跳表中的一個排名，這就為zset提供了一個查看排名的方法。數(shù)組中的每個節(jié)點中用1、2、3等字樣標記節(jié)點的各個層，L1代表第一層，L2代表第二層，L3代表第三層；，以此類推；
skiplistNode的示意圖如下所示：
2、增刪改查
以下圖為例，講解一下skiplist的增刪改查過程。
2.1 查
假設現(xiàn)在要查找7這個節(jié)點，步驟如下：
從
head開始遍歷，指針指向4這個節(jié)點，由于4<7，且同層的下一個指針指向NULL，所以下級一層；跳到6節(jié)點所在的層，同理，6<7，且同層的下一個指針指向
NULL，再下降一層；此時到了第一層，第一層是一個雙向鏈表，由于6<7，所以開始向后遍歷，查找到7就返回，不然就返回
NULL；
2.2 刪
刪除的過程前期與查找相似，先定位到元素所在的位置，再進行刪除，最后更新一下指針、更新一下最高的層數(shù)。
2.3 改
先是判斷這個 value 是否存在，如果存在就是更新的過程，如果不存在就是插入過程。在更新的過程是，如果找到了Value，先刪除掉，再新增，這樣的弊端是會做兩次的搜索，在性能上來講就比較慢了，在 Redis 5.0 版本中，Redis 的作者 Antirez 優(yōu)化了這個更新的過程，目前的更新過程是如果判斷這個 value是否存在，如果存在的話就直接更新，然后再調(diào)整整個跳躍表的 score 排序，這樣就不需要兩次的搜索過程。
2.4 增
比如要插入的值為 6
從 head 節(jié)點開始，先是在 head 開始降層來查找到最后一個比 6 小的節(jié)點；
等到查到最后一個比 6 小的節(jié)點的時候(假設為 5 )；
然后需要引入一個隨機層數(shù)算法來為這個節(jié)點隨機地建立層數(shù)；
把這個節(jié)點插入進去以后，同時更新一遍最高的層數(shù)即可；
2.5 隨機層數(shù)算法
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL)
? level : ZSKIPLIST_MAXLEVEL;
}#define ZSKIPLIST_MAXLEVEL 32 #define ZSKIPLIST_P 0.25
3、總結(jié)
來源：https://www.cnblogs.com/reecelin/p/13368374.html
往期推薦