按照慣例，先丟一個官網文檔鏈接。
上篇我們已經了解了高效的數據結構P1-String與Hash。
這篇，我們繼續來了解Redis的 Set 與 Sorted set。
目錄
- 有序集合 Sorted set
- 底層實現
- 集合 Set
- 總結
- 資料引用
有序集合 Sorted set
Redis 有序集合是一組唯一的字符串（成員）集合，這些字符串根據一個關聯的分數進行排序。
這種有序、元素唯一且根據關聯的分數進行排序的高效操作的數據結構，簡稱ZSET。
可以用于：
- 動態排序：比如排行榜，每個元素可以代表一個實體（如用戶、商品），分數表示排序依據（如積分、銷量）。由于ZSET自動維護排序，你可以輕松獲取排名靠前的成員、某個成員的排名，或者按分數范圍查詢。
# 添加
> zadd prices 8 sandwich
(integer) 1> zadd prices 100000 car
(integer) 1> zadd prices 6300 iphone 8900 iphonepro
(integer) 2# 結果展示
> zrange prices 0 9 withscores
1) "sandwich"
2) "8"
3) "iphone"
4) "6300"
5) "iphonepro"
6) "8900"
7) "car"
8) "100000"
- 速率限制器：ZSET可以實現一種基于滑動窗口的速率限制器，利用時間戳作為分數，成員記錄請求標識，自動移除過期的請求。
底層實現
ZSET通過包含跳表和哈希表的二端口數據結構實現。每個ZSET對象包含一個哈希表和一個跳表，成員和分數在兩邊各存一份，哈希表存member -> score，跳表存score -> member的排序關系。
typedef struct zset {dict *dict;zskiplist *zsl;
} zset;
其中哈希結構上章已經了解過了。ZSET的唯一性便是通過Hash Table實現的。總體結構也同Hash類似。
跳表用于維護成員的按分數排序，支持高效的插入、刪除、排名查詢和范圍查詢。
本篇進行跳表skiplist的介紹，并了解skiplist是如何設計以支持排序的。
源碼地址點這，其結構由redis.h/zskiplistNode和redis.h/zskiplist兩個結構定義。
zskiplist和zskiplistNode結構如下：
typedef struct zskiplist {struct zskiplistNode *header, *tail; //頭、尾節點unsigned long length; // 長度int level;//記錄目前跳躍表內，層數最大的那個節點的層數（表頭節點的層數不計算在內）
} zskiplist;typedef struct zskiplistNode {sds ele; // 成員double score; // 分數struct zskiplistNode *backward;// 后退指針struct zskiplistLevel {struct zskiplistNode *forward;// 前進指針unsigned long span;// 跨度，記錄跳過的節點數（前進指針所指向節點和當前節點的距離）} level[];
};
zskiplistNode用于表示跳躍表節點，zskiplist結構用于保存跳躍表節點的相關信息。
zskiplistNode點的level數組可以包含多個元素，每個元素都包含一個指向其他節點的指針，程序可以通過這些層來加快訪問其他節點的速度，一般來說，層的數量越多，訪問其他節點的速度就越快。
較傳統Node與List，zskiplistNode多了一個level[]結構，這是一個動態數組。每個元素表示該節點在某一層級的前進指針（指向下一個節點）和跨度（span，表示跳過的節點數）
struct zskiplistLevel {struct zskiplistNode *forward;// 前進指針unsigned long span;// 跨度，記錄跳過的節點數（前進指針所指向節點和當前節點的距離）} level[];
Redis zskiplistNode這個設計通過level[]存儲的多層索引預計算節點關系（預存關系），讓查找、插入和刪除的復雜度從傳統鏈表的O(N)降到O(log N)，接近二分查找的效率。
跳表的高層索引節點稀疏，低層節點密集，類似二分搜索的層次劃分，快速定位目標節點或分數范圍。
level[]有點類似閉包表的核心表設計，存儲節點關系。
![![[Pasted image 20250417234839.png]]](https://i-blog.csdnimg.cn/direct/023f6a4da5a048fdbaaf56a839fe7b9f.png)
- 核心方法
閱讀Redis的zskiplist.c，重點看zslInsert（插入）和zslGetRank（排名計算），理解level[]和span的實現。
zslInsert源碼如下：
/* 插入一個新節點到跳表中，返回新插入的節點指針* 參數：* zsl: 跳表對象* score: 新節點的分數* ele: 新節點的成員（字符串）* 返回：* 新插入的節點指針*/
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; // update數組記錄每層插入位置的前驅節點unsigned long rank[ZSKIPLIST_MAXLEVEL]; // rank數組記錄每層累積的跨度int i, level;serverAssert(!isnan(score)); // 確保分數不是NaN// 步驟1：查找插入位置，記錄前驅節點和跨度x = zsl->header; // 從頭節點開始for (i = zsl->level-1; i >= 0; i--) { // 從最高層逐層向下查找// 初始化rank，繼承上一層的跨度（若非最高層）rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];// 沿當前層前進，直到遇到分數更大或字典序更大的節點while (x->level[i].forward &&(x->level[i].forward->score < score ||(x->level[i].forward->score == score &&sdscmp(x->level[i].forward->ele, ele) < 0))) {// 累加跨度，記錄跳過的節點數rank[i] += x->level[i].span;x = x->level[i].forward; // 前進到下一個節點}// 記錄當前層的前驅節點update[i] = x;}// 步驟2：隨機生成新節點的層級level = zslRandomLevel(); // 隨機層級，概率遞減（通常p=0.25）if (level > zsl->level) { // 如果新層級超過當前最大層級for (i = zsl->level; i < level; i++) {rank[i] = 0; // 新層級的rank初始化為0update[i] = zsl->header; // 新層級的前驅是頭節點update[i]->level[i].span = zsl->length; // 跨度設為跳表總長度}zsl->level = level; // 更新跳表最大層級}// 步驟3：創建新節點x = zslCreateNode(level, score, ele); // 分配新節點內存，初始化分數和成員for (i = 0; i < level; i++) { // 為每層設置指針和跨度// 插入新節點：將新節點的forward指向前驅的forwardx->level[i].forward = update[i]->level[i].forward;update[i]->level[i].forward = x; // 前驅指向新節點// 更新跨度：新節點的跨度 = 前驅原跨度 - 已跳過的節點數x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);update[i]->level[i].span = (rank[0] - rank[i]) + 1; // 前驅的新跨度}// 步驟4：處理更高層的跨度for (i = level; i < zsl->level; i++) {update[i]->level[i].span++; // 未插入新節點的層，跨度+1}// 步驟5：設置后退指針x->backward = (update[0] == zsl->header) ? NULL : update[0];if (x->level[0].forward)x->level[0].forward->backward = x;elsezsl->tail = x;// 步驟6：更新跳表元數據zsl->length++; // 跳表長度+1return x; // 返回新節點
}
集合 Set
Redis 集合是一個無序且唯一的字符串集合（成員）。您可以使用 Redis 集合高效地：
- 跟蹤唯一的項目（例如，跟蹤訪問特定博客文章的所有唯一 IP 地址。唯一事件ID）
- 表示關系（例如，具有給定角色的所有用戶的集合）
- 執行常見的集合操作，如交集、并集和差集
和Java的HashSet一樣，非常適合刪除重復數據的集合。
Redis Set的底層實現主要依賴兩種數據結構：哈希表（Hash Table）和整數集合（Intset）。
其中哈希結構上章已經了解過了。唯一性便是通過Hash Table實現的。那么整數集合Intset是干什么的呢？
用來提供動態數據結構選擇的。
當Set包含非整數成員（如字符串）或成員數量較多時，使用哈希表。
當Set的所有成員都是整數（支持int16、int32、int64），且成員數量較少時（受set-max-intset-entries配置控制，默認512），使用整數集合Intset。
數量超過閾值會轉換成Hash Table，且Intset到哈希表的轉換是單向的（不可逆），因為哈希表支持任意字符串，而Intset只支持整數。
即，Redis Set的底層數據結構會根據存儲的成員類型和數量動態選擇。
intset源碼地址。
源碼如下：
typedef struct intset {// 編碼類型（INTSET_ENC_INT16/32/64）uint32_t encoding;// 數組長度uint32_t length;// 保存元素的數組int8_t contents[];
} intset;
Intset是一個緊湊的有序數組，存儲整數值，自動選擇最小編碼類型（int16_t、int32_t、int64_t）以節省內存。
Intset有編碼升級機制：
當插入的整數超出當前編碼范圍（如int16_t溢出），Intset自動升級到更高編碼（如int32_t），并重新分配內存。
且Intset有序。Intset按數值大小排序，插入時使用二分查找定位。
Redis通過設計一種轉換機制，使用Intset來專門優化存儲小規模整數集合，達到節省內存（緊湊存儲）的目的，提升內存效率，且支持快速二分查找，適合小集合的查詢。
總結
Redis不負簡單高效的內存數據庫之名，一方面做了大量空間換時間的操作，一方面設計極致壓榨內存、提升內存效率。
比如跳表的預存、hash表的漸進擴容、String sds的預留空間、延遲釋放、intset的極致內存利用、set的動態轉換。
資料引用
《Redis設計與實現》
)
