redis五種數據結構的底層實現方法

# Redis五種數據結構的底層實現方法

Redis作為高性能的鍵值存儲系統，其核心優勢在于豐富的數據結構設計。這些數據結構并非簡單的語言原生實現，而是針對內存效率和操作性能進行了深度優化。本文將深入剖析Redis五種核心數據結構（String、List、Hash、Set、Sorted Set）的底層實現機制。

## 1. String（字符串）

### 1.1 動態字符串SDS
Redis沒有直接使用C語言的字符數組，而是自定義了**Simple Dynamic String（SDS）**結構：
```c
struct sdshdr {
    int len;    // 已用空間長度
    int free;   // 剩余空間長度
    char buf[]; // 實際數據存儲
};

1.2 優化策略

• 空間預分配：擴展字符串時額外分配冗余空間（小于1MB時加倍，大于1MB時每次+1MB）
• 惰性釋放：縮短字符串時不立即回收內存
• 二進制安全：通過len字段記錄長度而非依賴’\0’終止符

1.3 特殊編碼

根據值類型自動選擇編碼方式： - int：8字節長整型存儲 - embstr：長度≤44字節的短字符串 - raw：長字符串標準SDS存儲

2. List（列表）

2.1 雙向鏈表

基礎實現為典型的雙向鏈表結構：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

2.2 快速鏈表（QuickList）

Redis 3.2后引入的混合結構： - 宏觀上是雙向鏈表 - 每個節點是ziplist（壓縮列表） - 通過list-max-ziplist-size控制單個ziplist大小

2.3 Ziplist壓縮列表

內存緊湊的連續存儲結構：

[zlbytes][zltail][zllen][entry1][entry2][...][zlend]

• 每個entry包含前驅節點長度和當前數據
• 支持整數特殊編碼

3. Hash（哈希表）

3.1 字典結構

typedef struct dict {
    dictType *type;
    dictht ht[2]; // 雙哈希表
    long rehashidx;
} dict;

3.2 漸進式rehash

• 擴容時同時維護新舊兩個哈希表
• 通過rehashidx記錄遷移進度
• 在每次CRUD操作時逐步遷移數據

3.3 哈希沖突解決

采用鏈地址法，但進行了優化： - 新節點總是添加到鏈表頭部 - 鏈表長度超過閾值時轉為跳表

4. Set（集合）

4.1 實現方式選擇

• intset：當元素均為整數且數量較少時

  
  typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
  } intset;
  

• 哈希表：默認實現（值為NULL的特殊字典）

4.2 自動轉換機制

通過set-max-intset-entries配置閾值（默認512），當元素數量或類型不滿足條件時自動轉為哈希表實現。

5. Sorted Set（有序集合）

5.1 跳表+字典組合

typedef struct zset {
    dict *dict;        // 維護member->score映射
    zskiplist *zsl;    // 維護排序結構
} zset;

5.2 跳表實現細節

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

• 通過隨機層數（1-32）實現平均O(logN)復雜度
• 支持范圍查詢和排名操作

5.3 內存優化

當元素較小時使用ziplist存儲（通過zset-max-ziplist-entries和zset-max-ziplist-value配置）

性能優化總結

總結

Redis通過精心設計的數據結構實現，在內存使用和操作效率之間取得了卓越的平衡。理解這些底層機制對于： 1. 合理配置參數（如ziplist相關閾值） 2. 選擇合適的數據類型 3. 性能問題診斷 都具有重要意義。實際開發中應根據具體場景靈活選用數據結構，并關注Redis的版本演進帶來的持續優化。 “`

注：本文約1200字，采用Markdown格式編寫，包含代碼塊、表格等元素。如需調整具體內容細節或補充更多實現原理，可以進一步擴展特定部分的說明。