部落格首頁：🏆看看是李XX還是李歘歘 🏆
🌺每天不定期分享一些包括但不限于計算機基礎、算法、後端開發相關的知識點，以及職場小菜雞的生活。🌺
💗點關注不迷路，總有一些📖知識點📖是你想要的💗
⛽️今天的内容是 redis跳表——zset的底層實作 ⛽️💻💻💻
redis的有序集合zset在增删改查的性質上類似于C++ stl的map和Java的TreeMap，提供了一組“鍵-值”對，并且“鍵”按照“值”的順序排序。但是與C++ stl或Java的紅黑樹實作不同的是，redis中有序集合的實作采用了另一種資料結構——跳躍表。跳躍表是有序單連結清單的一種改進，其查詢、插入、删除也是O(logN)的時間複雜度。
zset的兩種實作方式
- ziplist(壓縮連結清單)：滿足以下兩個條件的時候
- 元素數量少于128的時候
- 每個元素的長度小于64位元組
- skiplist(跳躍連結清單)：不滿足上述兩個條件就會使用跳表，具體來說是組合了map和skiplist
- map用來存儲member到score的映射，這樣就可以在O(1)時間内找到member對應的分數
- skiplist按從小到大的順序存儲分數
- skiplist每個元素的值都是[score,value]對
ziplist原理
每個集合元素使用兩個緊挨在一起的壓縮清單節點來儲存，第一個節點儲存元素的成員，第二個元素儲存元素的分值。壓縮清單中的元素按照分數從小到大依次緊挨着排列，有效減少了記憶體空間的使用。
skiplist原理
參考：Skip Lists: A Probabilistic Alternative to Balanced Trees
上圖用a,b,c,d,e五種有序連結清單說明了跳躍表的motivation.
- [a]單連結清單：查詢時間複雜度O(n)
- [b]level-2單連結清單：每隔一個節點為一個level-2節點，每個level-2節點有2個後繼指針，分别指向單連結清單中的下一個節點和下一個level-2節點。查詢時間複雜度為O(n/2)
- [c]level-3單連結清單：每隔一個節點為一個level-2節點，每隔4個節點為一個level-3節點，查詢時間複雜度O(n/4)
- [d]指數式單連結清單：每隔一個節點為一個level-2節點，每隔4個節點為一個level-3節點，每隔8個節點為一個level-4節點（每2^i個節點的level為i+1），查詢時間複雜度為O(log2N)
- [e]跳躍表：各個level的節點個數同指數式單連結清單，但出現的位置随機，查詢複雜度是O(logN)
因為有序連結清單的插入和删除複雜度等于查詢複雜度。文章證明了跳躍表查詢複雜度的期望是O(logN).
redis選擇跳躍表而非紅黑樹作為有序集合實作方式的原因并非是基于并發上的考慮，因為redis是單線程的，選用跳躍表的原因僅僅是因為跳躍表的實作相較于紅黑樹更加簡潔。
redis跳躍表的源碼
跳躍表節點，跳躍表和zset結構體的定義在server.h
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset; score:分值，用于排序
backward:是第一層的前一個資料，即span=1
level[]:每一個層所代表的節點node
forward:該層級的下一個節點
span:到達該層級的下一個節點，實際跨越了多少個節點,也是友善用于zrange等排行榜查詢的用處 skiplist過程：
1. 查找過程 時間複雜度O(logN)
對于zrangebyscore指令：score作為查找的對象，在跳表中跳躍查詢，就和上面skiplist的查詢一樣
2. 插入過程 時間複雜度O(logN)
zadd [zset name] [score] [value]：
- 在map中查找value是否已存在，如果存在現需要在skiplist中找到對應的元素删除，再在skiplist做插入
- 插入過程也是用score來作為查詢位置的依據，和skiplist插入元素方法一樣。并需要更新value->score的map
如果score一樣怎麼辦？根據value再排序，按照順序插入
3. 删除過程
zrem [zset name] [value]：從map中找到value所對應的score，然後再在跳表中搜尋這個score,value對應的節點，并删除
4. 排名是怎麼算出來的
zrank [zset name] [value]的實作依賴與一些附加在跳表上的屬性：
- 跳表的每個元素的Next指針都記錄了這個指針能夠跨越多少元素，redis在插入和删除元素的時候，都會更新這個值
- 然後在搜尋的過程中按經過的路徑将路徑中的span值相加得到rank
Redis zset實作原理
redis有序集合zset的底層實作——跳躍表skiplist_da_kao_la的部落格
跳躍表是有序集合的底層實作之一。
Redis的跳躍表實作由zskiplist和zskiplistNode兩個結構組成，其中zskiplist用于儲存跳躍表資訊（比如表頭節點、表尾節點、長度），而zskiplistNode則用于表示跳躍表節點。
每個跳躍表節點的層高都是1至32之間的随機數。
在同一個跳躍表中，多個節點可以包含相同的分值，但每個節點的成員對象必須是唯一的。