目錄
一 、從 "超市貨架" 的痛點看跳躍表的價值
1.1、跳躍表與商場導航系統的結構對應
1. 1.1、zskiplistNode：帶導航標記的 "商品"（跳躍表節點）
1.1.1.1、level []：商品上的多層導航標記
1.1.1.2、backward：商品的 "后退箭頭"
1.1.1.3、score：商品的 "價格標簽"
1.1.1.4、obj：商品的 "名稱牌"（銜接 SDS！）
1.1.2、zskiplist：商場的 "總服務臺"（跳躍表管理結構）
二、跳躍表的工作流程：像顧客找商品一樣簡單
三、設計細節：為什么跳躍表要這樣設計？
3.1、節點層數為什么隨機？——"熱門商品多掛導航"
3.2、為什么不用平衡樹？——"導航系統比復雜樹狀圖更實用"
3.3、與之前結構的配合：Redis 的 "結構組合拳"
四、總結：跳躍表的設計智慧
如果說 SDS 是 "智能價簽"、鏈表是 "貨架"、字典是 "儲物柜"，那么跳躍表就是 Redis 為 "有序商品展示" 設計的商場多層導航系統。當你需要按價格排序展示商品（如電商 APP 的 "價格從低到高"），或者記錄游戲排名這類需要快速定位和范圍查詢的場景時，跳躍表就會像商場的多層導視圖一樣，讓你不用逐個瀏覽就能快速找到目標。
一 、從 "超市貨架" 的痛點看跳躍表的價值
假設你在超市的 "零食區" 貨架上按價格排序擺放著商品：
薯片(5元) → 巧克力(10元) → 牛肉干(15元) → 堅果(20元) → ... → 進口禮盒(100元)
這本質上是一個有序鏈表（類似我們之前講的 list 結構），但有個明顯問題：如果想找 "30 元左右的商品"，你必須從第一個商品開始逐個查看 —— 就像顧客在貨架前從頭走到尾，效率很低（時間復雜度 O (N)）。
超市為了解決這個問題，會在貨架上方加多層導航牌：
- 地面層（對應貨架本身）：每個商品都能看到
- 中層導航（2 米高）：每隔 5 個商品標一個價格區間（如 "5-15 元區→15-30 元區→..."）
- 高層導航（5 米高）：標注大區間（如 "0-50 元區→50-100 元區"）
這種設計讓顧客先看高層導航定位大致區域，再通過中層導航縮小范圍，最后在地面層精確查找 —— 這就是跳躍表的核心思路：用多層索引實現 "跳著找"，把復雜度從 O (N) 降到平均 O (logN)。
1.1、跳躍表與商場導航系統的結構對應
Redis 的跳躍表結構與商場導航系統的對應關系非常直觀，我們結合之前學過的結構知識逐層拆解：
1. 1.1、zskiplistNode：帶導航標記的 "商品"（跳躍表節點）
每個商品就像一個跳躍表節點，不僅有自身信息，還帶著多層導航標記：
typedef struct zskiplistNode {// 層（多層導航標記）struct zskiplistLevel {struct zskiplistNode *forward; // 前進指針（指向遠處的商品）unsigned int span; // 跨度（中間隔了多少個商品）} level[];// 后退指針（只能回到前一個商品）struct zskiplistNode *backward;// 分值（商品價格，排序依據）double score;// 成員對象（商品名稱，用SDS存儲）robj *obj;
} zskiplistNode;
1.1.1.1、level []：商品上的多層導航標記
- 這是跳躍表的核心，每個
level元素對應一層導航。比如level[0]是 "地面層導航"（必有的基礎層），level[1]是 "中層導航"，level[2]是 "高層導航"（最多 32 層）。 - forward 指針：就像商品上貼的 "前方 50 米有 30 元區" 標簽，直接指向遠處的目標節點。比如在 "15 元牛肉干" 的中層導航（level [1]）上，forward 可能直接指向 "30 元餅干"，跳過中間的 20 元、25 元商品。
- span（跨度）：記錄兩個節點之間的 "間隔數"。比如從 15 元牛肉干到 30 元餅干中間有 3 個商品，span 就等于 3—— 這就像導航標簽上寫著 "中間有 3 個商品"，能快速計算排名（比如知道 15 元是第 3 名，span=3，30 元就是第 6 名）。
1.1.1.2、backward：商品的 "后退箭頭"
- 每個節點只有一個 backward 指針，只能指向 "前一個節點"，就像貨架上的 "返回上一個商品" 箭頭，顧客看完當前商品想回頭，只能一步一步往回走（不能跳）。這和鏈表的 prev 指針功能類似，但跳躍表的 forward 指針能跳，backward 不能 —— 因為后退場景少，沒必要浪費空間做多層后退索引。
1.1.1.3、score：商品的 "價格標簽"
score是排序的依據（必須有序），就像商品按價格從小到大排列。在 Redis 的有序集合中，比如ZADD goods 5 "chip" 10 "chocolate"，這里的 5 和 10 就是 score。
1.1.1.4、obj：商品的 "名稱牌"（銜接 SDS！）
obj存儲的是成員名稱（如 "chip"），底層用SDS實現（呼應我們講過的 SDS 結構）：- 比如 "chocolate" 這個名稱，實際存儲為 SDS：
len=9（9 個字符）、free=9（預分配空間）、buf=['c','h','o','c','o','l','a','t','e','\0']。 - 為什么用 SDS？因為商品名稱可能很長（比如 "2024 限量版進口巧克力"），SDS 的動態擴展和二進制安全特性，能高效存儲這些字符串（和我們之前講的字典鍵存儲邏輯一致）。
- 比如 "chocolate" 這個名稱，實際存儲為 SDS：
1.1.2、zskiplist：商場的 "總服務臺"（跳躍表管理結構）
如果說zskiplistNode是單個商品，zskiplist就是商場服務臺的 "總導視圖"，記錄全局信息：
typedef struct zskiplist {struct zskiplistNode *header, *tail; // 首/尾商品位置unsigned long length; // 商品總數int level; // 最高導航層數
} zskiplist;
這幾個字段的作用和服務臺導視圖完全對應：
- header/tail：導視圖上標著 "零食區起點" 和 "零食區終點"，讓你瞬間定位第一個和最后一個商品（O (1) 復雜度）。比如想找最便宜的商品，直接從 header 開始；想找最貴的，直接定位到 tail。
- length：導視圖上寫著 "共 50 種商品"，不用數貨架就知道總數（O (1) 復雜度）—— 這和鏈表的 len 屬性功能相同，但鏈表需要遍歷統計，跳躍表直接記錄。
- level：導視圖上標著 "最高 3 層導航"，告訴你最高層索引是多少，避免在不存在的高層導航中查找（O (1) 復雜度）。
二、跳躍表的工作流程：像顧客找商品一樣簡單
我們用 "找 30 元的商品" 這個場景，看跳躍表的查找過程（對應顧客在商場找 30 元商品）：
-
從最高層導航開始（比如 3 層）：
服務臺導視圖顯示最高 3 層，顧客先看 3 層導航，發現 "0-50 元區" 的起點是 5 元薯片，終點是 50 元禮盒。30 元在這個區間內，于是下到 2 層導航。 -
中層導航縮小范圍（2 層）：
2 層導航標著 "5-15 元→15-30 元→30-50 元"，顧客從 5 元薯片出發，順著 2 層導航的 forward 指針跳到 15 元牛肉干（span=2，中間有 2 個商品），再跳到 30 元餅干（span=3，中間有 3 個商品）。 -
地面層精確查找（1 層）：
到了 30 元餅干的位置，發現正好是目標，查找結束。如果沒找到，就順著 1 層的 forward 指針逐個查看（因為 1 層是完整鏈表）。
這個過程完美體現了 "高層跳大步，低層走小步" 的效率優勢 —— 比從第一個商品逐個查找快得多。
三、設計細節：為什么跳躍表要這樣設計？
3.1、節點層數為什么隨機？——"熱門商品多掛導航"
每個新節點的層數（1-32 層）是隨機生成的，就像商場會給熱門商品掛更多層導航（比如暢銷零食在高、中、低三層都有標記），普通商品可能只在地面層有標記。
隨機層數的好處：
- 避免所有節點都掛 32 層導航（浪費空間）
- 統計上能形成 "高層節點少、低層節點多" 的金字塔結構，保證查找效率
這就像字典的哈希分布策略，通過概率平衡性能和空間。
3.2、為什么不用平衡樹？——"導航系統比復雜樹狀圖更實用"
有序數據結構中，平衡樹（如紅黑樹）也能達到 O (logN) 效率，但 Redis 選跳躍表的原因：
- 實現簡單：跳躍表的多層索引邏輯比平衡樹的 "旋轉調整" 簡單（就像商場導航比復雜的樹狀分布圖好懂）。
- 范圍查詢高效：比如找 "20-50 元的商品"，跳躍表從 20 元節點開始，順著 1 層 forward 指針就能批量獲取（類似鏈表的順序遍歷），平衡樹需要復雜的左右子樹遍歷。
- 空間可控：層數上限 32，不會像平衡樹那樣因頻繁調整導致空間波動（類似商場導航層數固定，不會突然增刪樓層）。
3.3、與之前結構的配合：Redis 的 "結構組合拳"
跳躍表不是孤立存在的，而是和其他結構配合工作：
- 與 SDS 配合：用 SDS 存儲節點的成員名稱（obj），利用其動態字符串特性（如之前講的空間預分配、長度記錄）。
- 與字典配合：在有序集合中，Redis 會同時用字典（記錄 member 到 score 的映射）和跳躍表（按 score 排序），形成 "快速查找 + 有序遍歷" 的組合（就像商場既有儲物柜按編號找東西，又有導航系統按價格找東西）。
四、總結：跳躍表的設計智慧
| 跳躍表組件 | 商場導航系統對應 | 技術價值 | 與其他結構的關聯 |
|---|---|---|---|
| zskiplistNode.level | 商品的多層導航標簽 | 分層查找，平均 O (logN) 效率 | - |
| forward 指針 | 導航標簽的 "指向箭頭" | 快速跳躍定位 | 類似字典的哈希定位，但支持有序 |
| span 跨度 | 導航標簽的 "間隔數" | 快速計算排名（如 ZRANK 命令） | - |
| backward 指針 | 商品的 "后退箭頭" | 支持反向遍歷（如 ZREVRANGE） | 類似鏈表的 prev 指針 |
| score 分值 | 商品價格標簽 | 作為排序依據 | - |
| obj 成員對象 | 商品名稱牌 | 存儲成員信息 | 用 SDS 實現，復用字符串優化 |
| zskiplist 管理結構 | 商場總導視圖 | O (1) 獲取全局信息（首尾、總數等） | 類似鏈表的 list 管理結構 |
跳躍表就像為 "有序數據快速訪問" 量身定制的導航系統，它沒有追求最復雜的結構，而是用 "多層索引 + 隨機優化" 的簡單思路，平衡了效率、實現難度和空間開銷。這種設計思路和 Redis 的整體哲學一致 —— 為不同場景選擇最合適的結構（字符串用 SDS、無序查找用字典、有序查找用跳躍表），最終實現 "又快又穩" 的性能表現。
)
(中))