今天我們來聊聊Redis中一個非常有趣且實用的數(shù)據(jù)結(jié)構(gòu)——有序集合(zset)。就像我們平時在超市購物時，商品會按照價格從低到高排列一樣，zset也能幫我們維護一個有序的數(shù)據(jù)集合。那么Redis是如何實現(xiàn)這種高效的有序結(jié)構(gòu)的呢？讓我們一起來探索它的底層實現(xiàn)原理。

1. zset的基本概念

在開始深入之前，我們先簡單回顧一下zset的基本特性。zset是Redis提供的一種有序集合數(shù)據(jù)結(jié)構(gòu)，它類似于普通的集合(set)，但每個成員都會關(guān)聯(lián)一個分數(shù)(score)，Redis會根據(jù)這個分數(shù)對集合中的成員進行從小到大的排序。

zset在實際應用中非常有用，比如我們可以用它來實現(xiàn)：

• 排行榜系統(tǒng)（按分數(shù)排序）
• 帶權(quán)重的任務(wù)隊列
• 時間線功能（按時間戳排序）
• 范圍查詢（如查找分數(shù)在80-90之間的學生）

zset的一個關(guān)鍵特性是：雖然成員是唯一的，但分數(shù)可以重復。這就像班級里每個學生學號唯一，但可以有多個學生考同樣的分數(shù)。

2. zset的底層實現(xiàn)結(jié)構(gòu)

理解了zset的基本概念后，我們來看看Redis是如何實現(xiàn)它的。Redis的zset實際上使用了兩種數(shù)據(jù)結(jié)構(gòu)組合來實現(xiàn)：

2.1 哈希表(Hash Table)

Redis使用一個哈希表來存儲成員(member)到分數(shù)(score)的映射關(guān)系。這就像我們有一個學生名冊，可以快速通過學生姓名查找到他的考試成績。

哈希表的優(yōu)勢在于：

• O(1)時間復雜度查找成員對應的分數(shù)
• 快速判斷某個成員是否存在
• 高效更新成員的分數(shù)

2.2 跳躍表(Skip List)或壓縮列表(Zip List)

為了維護成員的有序性，Redis會根據(jù)數(shù)據(jù)量的大小選擇使用跳躍表或壓縮列表：

• 當元素數(shù)量較少或元素較小時，使用壓縮列表(Zip List)
• 當元素數(shù)量超過閾值或元素較大時，使用跳躍表(Skip List)

這種設(shè)計是Redis典型的"小數(shù)據(jù)優(yōu)化"思想，對于小數(shù)據(jù)集使用更緊湊的存儲方式，對于大數(shù)據(jù)集則使用性能更好的結(jié)構(gòu)。

以上流程圖說明了zset的底層實現(xiàn)結(jié)構(gòu)。它同時使用了哈希表和有序結(jié)構(gòu)（可能是壓縮列表或跳躍表）來滿足不同的操作需求。

3. 壓縮列表實現(xiàn)細節(jié)

現(xiàn)在我們來詳細看看zset在小數(shù)據(jù)情況下的實現(xiàn)——壓縮列表(Zip List)。壓縮列表是Redis為了節(jié)省內(nèi)存而設(shè)計的一種特殊編碼方式。

3.1 壓縮列表的結(jié)構(gòu)

壓縮列表是一塊連續(xù)的內(nèi)存空間，它按照特定的格式存儲數(shù)據(jù)。想象一下，這就像我們把所有數(shù)據(jù)整齊地打包在一個行李箱里，而不是分散放在房間各處。

一個壓縮列表包含以下部分：

+--------+--------+--------+--------+--------+--------+--------+--------+
| zlbytes | zltail | zllen  | entry1 | entry2 |  ...   | entryN | zlend  |
+--------+--------+--------+--------+--------+--------+--------+--------+
    

其中：

• zlbytes: 整個壓縮列表占用的內(nèi)存字節(jié)數(shù)
• zltail: 最后一個節(jié)點的偏移量，方便快速定位
• zllen: 節(jié)點數(shù)量
• entry1..N: 各個節(jié)點數(shù)據(jù)
• zlend: 結(jié)束標記(0xFF)

3.2 壓縮列表中的元素存儲

在zset中使用壓縮列表時，每個成員和它的分數(shù)會作為兩個連續(xù)的節(jié)點存儲。這就像我們把學生的姓名和成績寫在相鄰的兩張卡片上。

例如，存儲一個zset {“alice”: 85, “bob”: 92}，在壓縮列表中的布局如下：

+-------+-------+-------+-------+-------+-------+-------+-------+
| ... | 85  | alice | 92  | bob  | ... |
+-------+-------+-------+-------+-------+-------+-------+-------+
    

這種存儲方式非常緊湊，沒有額外的指針開銷，因此在小數(shù)據(jù)量時非常高效。

需要注意的是，當zset使用壓縮列表存儲時，所有操作都需要遍歷整個列表，因此時間復雜度是O(N)。這就是為什么Redis會在數(shù)據(jù)量大時切換到跳躍表的原因。

4. 跳躍表實現(xiàn)細節(jié)

當zset中的元素數(shù)量超過zset-max-ziplist-entries（默認128）或元素大小超過zset-max-ziplist-value（默認64字節(jié)）時，Redis會將底層結(jié)構(gòu)轉(zhuǎn)換為跳躍表(Skip List)。

4.1 跳躍表的基本概念

跳躍表是一種概率平衡的數(shù)據(jù)結(jié)構(gòu)，可以看作是多層鏈表。想象一下地鐵系統(tǒng)：有普通站（每站都停）和快速站（只停大站），這樣乘客可以根據(jù)需要選擇不同速度的線路。

一個簡單的跳躍表示例：

Level 3: 1 --------------------------------> 9
Level 2: 1 ------------> 5 ------------> 9
Level 1: 1 ---> 3 ---> 5 ---> 7 ---> 9
Level 0: 1->2->3->4->5->6->7->8->9
    

在這個結(jié)構(gòu)中，查找時可以跳過一些節(jié)點，從而將查找時間復雜度從O(N)降低到O(logN)。

4.2 Redis中跳躍表的具體實現(xiàn)

Redis中的跳躍表實現(xiàn)包含兩個主要結(jié)構(gòu)：

1. zskiplistNode（跳躍表節(jié)點）

typedef struct zskiplistNode {
    robj *obj;                  // 成員對象
    double score;               // 分數(shù)
    struct zskiplistNode *backward; // 后退指針
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前進指針
        unsigned int span;             // 跨度
    } level[];                  // 層級數(shù)組
} zskiplistNode;
    

2. zskiplist（跳躍表）

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 頭尾節(jié)點
    unsigned long length;       // 節(jié)點數(shù)量
    int level;                  // 當前最大層數(shù)
} zskiplist;
    

跳躍表在Redis中的實際內(nèi)存布局如下圖所示：

[圖片位置1：Redis跳躍表內(nèi)存布局示意圖]

4.3 跳躍表的操作原理

讓我們以插入操作為例，看看跳躍表是如何工作的：

以上流程圖說明了在跳躍表中插入一個新元素的完整過程。關(guān)鍵在于從高層開始快速定位，然后逐步精確到插入位置，最后通過隨機算法決定新節(jié)點的層數(shù)。

4.4 為什么Redis選擇跳躍表而不是平衡樹

很多同學可能會問，為什么Redis不使用更常見的平衡樹（如AVL樹或紅黑樹）來實現(xiàn)有序集合呢？這主要有以下幾個原因：

1. 實現(xiàn)簡單：跳躍表的實現(xiàn)比平衡樹簡單得多，代碼更易于維護
2. 范圍查詢高效：跳躍表在范圍查詢時非常高效，因為底層是一個鏈表
3. 并發(fā)友好：跳躍表比平衡樹更容易實現(xiàn)無鎖并發(fā)操作
4. 性能相當：對于大多數(shù)操作，跳躍表的平均時間復雜度與平衡樹相同

5. zset的常用操作分析

了解了zset的底層結(jié)構(gòu)后，我們來看看一些常用操作在這些結(jié)構(gòu)上是如何執(zhí)行的。

5.1 ZADD操作

ZADD key score member 是向zset中添加元素的基本命令。它的執(zhí)行流程如下：

檢查zset是否存在，不存在則創(chuàng)建

如果底層是壓縮列表：

• 檢查是否需要轉(zhuǎn)換為跳躍表（根據(jù)元素數(shù)量和大?。?/li>
• 如果不需要轉(zhuǎn)換，則遍歷壓縮列表查找插入位置
• 插入新元素（可能需要重新分配內(nèi)存）

如果底層是跳躍表：

• 使用跳躍表查找算法定位插入位置
• 創(chuàng)建新節(jié)點并插入到適當位置
• 更新哈希表中的member->score映射

5.2 ZRANGE操作

ZRANGE key start stop 用于獲取指定范圍內(nèi)的元素。它的執(zhí)行流程：

檢查zset是否存在

如果底層是壓縮列表：

• 從頭開始遍歷到start位置
• 繼續(xù)遍歷直到stop位置，收集結(jié)果

如果底層是跳躍表：

• 從頭節(jié)點開始，利用跳躍表的層級快速定位到start位置
• 沿著最底層鏈表遍歷到stop位置

5.3 ZSCORE操作

ZSCORE key member 用于獲取成員的分數(shù)。這個操作非常高效，因為它直接通過哈希表查找：

1. 在哈希表中查找member對應的score
2. 返回結(jié)果（無論底層是壓縮列表還是跳躍表，這一步都是O(1)）

從這些操作中我們可以看到，Redis巧妙地結(jié)合了哈希表和有序結(jié)構(gòu)的優(yōu)勢：哈希表提供快速的成員查找，有序結(jié)構(gòu)維護排序和范圍查詢能力。

6. zset的內(nèi)存優(yōu)化技巧

在實際使用中，我們經(jīng)常需要考慮如何優(yōu)化zset的內(nèi)存使用。下面分享幾個實用的技巧：

6.1 合理設(shè)置ziplist參數(shù)

我們可以根據(jù)實際數(shù)據(jù)特點調(diào)整這兩個參數(shù)：

# 修改redis.conf或通過CONFIG SET命令
zset-max-ziplist-entries 256  # 默認128
zset-max-ziplist-value 128    # 默認64
    

上述配置將允許更多的元素或更大的元素使用壓縮列表存儲。但要注意：

• 增加這些值會節(jié)省內(nèi)存，但可能降低操作性能
• 需要根據(jù)實際數(shù)據(jù)特點進行測試和權(quán)衡

6.2 使用更短的成員名稱

由于成員名稱存儲在內(nèi)存中，使用更短的名稱可以顯著節(jié)省內(nèi)存。例如：

• 使用用戶ID而不是用戶名
• 使用縮寫或編碼代替完整名稱

6.3 考慮使用整數(shù)分數(shù)

如果業(yè)務(wù)允許，使用整數(shù)而不是浮點數(shù)作為分數(shù)可以節(jié)省一些內(nèi)存。

6.4 定期清理過期數(shù)據(jù)

對于排行榜等場景，可以定期移除排名靠后的數(shù)據(jù)，保持zset的大小可控。

7. 實際應用案例

讓我們看一個實際的排行榜實現(xiàn)案例，展示如何充分利用zset的特性。

7.1 游戲排行榜實現(xiàn)

假設(shè)我們要實現(xiàn)一個游戲玩家積分排行榜，支持以下功能：

• 記錄玩家分數(shù)
• 獲取前10名玩家
• 查詢玩家排名
• 查詢分數(shù)段內(nèi)的玩家

Redis命令實現(xiàn)：

# 添加或更新玩家分數(shù)
ZADD leaderboard 3500 "player1"
ZADD leaderboard 2800 "player2"
ZADD leaderboard 4200 "player3"

# 獲取前10名玩家（按分數(shù)從高到低）
ZREVRANGE leaderboard 0 9 WITHSCORES

# 查詢特定玩家排名（從0開始）
ZREVRANK leaderboard "player1"

# 查詢分數(shù)在3000-4000之間的玩家
ZRANGEBYSCORE leaderboard 3000 4000 WITHSCORES
    

上述代碼展示了如何使用zset實現(xiàn)一個完整的排行榜系統(tǒng)?？紤]到排行榜需要頻繁更新和查詢，zset的O(logN)操作復雜度非常適合這種場景。

總結(jié)

通過今天的探討，我們對Redis中zset的底層實現(xiàn)有了深入的理解。讓我們總結(jié)一下本文的主要內(nèi)容：

1. zset的基本概念：有序集合，成員唯一但分數(shù)可重復
2. 底層結(jié)構(gòu)：哈希表+有序結(jié)構(gòu)（壓縮列表或跳躍表）
3. 壓縮列表實現(xiàn)：小數(shù)據(jù)時使用，內(nèi)存緊湊但操作復雜度高
4. 跳躍表實現(xiàn)：大數(shù)據(jù)時使用，O(logN)時間復雜度，支持高效范圍查詢
5. 操作分析：不同操作在不同結(jié)構(gòu)上的執(zhí)行流程
6. 優(yōu)化技巧：合理配置參數(shù)、縮短成員名稱等
7. 實際應用：排行榜系統(tǒng)的完整實現(xiàn)

Redis的zset通過巧妙的雙結(jié)構(gòu)設(shè)計，既保證了高效的成員查找，又維護了良好的排序特性，是很多有序場景的理想選擇。

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。