SDS （Simple Dynamic String）是 Redis 最基礎的數據結構。直譯過來就是”簡單的動態字元串“。Redis 自己實現了一個動態的字元串，而不是直接使用了 C 語言中的字元串。 sds 的數據結構： struct sdshdr { // buf 中已占用空間的長度 int l ...

SDS （Simple Dynamic String）是 Redis 最基礎的數據結構。直譯過來就是”簡單的動態字元串“。Redis 自己實現了一個動態的字元串，而不是直接使用了 C 語言中的字元串。

sds 的數據結構：

struct sdshdr {   
// buf 中已占用空間的長度 int len; 
// buf 中剩餘可用空間的長度 int free; 
// 數據空間 
char buf[];
    
}

所以一個 SDS 的就如下圖：

sds

所以我們看到，sds 包含3個參數。buf 的長度 len，buf 的剩餘長度，以及buf。

為什麼這麼設計呢？

可以直接獲取字元串長度。
C 語言中，獲取字元串的長度需要用指針遍歷字元串，時間複雜度為 O(n)，而 SDS 的長度，直接從len 獲取複雜度為 O(1)。
杜絕緩衝區溢出。
由於C 語言不記錄字元串長度，如果增加一個字元傳的長度，如果沒有註意就可能溢出，覆蓋了緊挨著這個字元的數據。對於SDS 而言增加字元串長度需要驗證 free的長度，如果free 不夠就會擴容整個 buf，防止溢出。
減少修改字元串長度時造成的記憶體再次分配。
redis 作為高性能的記憶體資料庫，需要較高的相應速度。字元串也很大概率的頻繁修改。 SDS 通過未使用空間這個參數，將字元串的長度和底層buf的長度之間的額關係解除了。buf的長度也不是字元串的長度。基於這個分設計 SDS 實現了空間的預分配和惰性釋放。
1. 預分配
  如果對 SDS 修改後，如果 len 小於 1MB 那 len = 2 * len + 1byte。這個 1 是用於保存空位元組。
  如果 SDS 修改後 len 大於 1MB 那麼 len = 1MB + len + 1byte。
2. 惰性釋放
  如果縮短 SDS 的字元串長度，redis並不是馬上減少 SDS 所占記憶體。只是增加 free 的長度。同時向外提供 API 。真正需要釋放的時候，才去重新縮小 SDS 所占的記憶體
二進位安全。
C 語言中的字元串是以 ”\0“ 作為字元串的結束標記。而 SDS 是使用 len 的長度來標記字元串的結束。所以SDS 可以存儲字元串之外的任意二進位流。因為有可能有的二進位流在流中就包含了”\0“造成字元串提前結束。也就是說 SDS 不依賴 “\0” 作為結束的依據。
相容C語言
SDS 按照慣例使用 ”\0“ 作為結尾的管理。部分普通C 語言的字元串 API 也可以使用。

鏈表

C語言中並沒有鏈表這個數據結構所以 Redis 自己實現了一個。Redis 中的鏈表是：

typedef struct listNode { 
// 前置節點 struct listNode *prev; 
// 後置節點 struct listNode *next; 
// 節點的值 void *value;} listNode;

非常典型的雙向鏈表的數據結構。

同時為雙向鏈表提供瞭如下操作的函數：

/* * 雙端鏈表迭代器 */typedef struct listIter { 
// 當前迭代到的節點 listNode *next; 
// 迭代的方向 int direction;} listIter;

/* * 雙端鏈表結構 

*/typedef struct list { 
// 表頭節點 listNode *head; 
// 表尾節點 listNode *tail; 
// 節點值複製函數 void *(*dup)(void *ptr); 
// 節點值釋放函數 void (*free)(void *ptr); 
// 節點值對比函數 int (*match)(void *ptr, void *key); 
// 鏈表所包含的節點數量 unsigned long len;} list;

鏈表的結構比較簡單，數據結構如下：

list

總結一下性質：

雙向鏈表，某個節點尋找上一個或者下一個節點時間複雜度 O(1)。
list 記錄了 head 和 tail，尋找 head 和 tail 的時間複雜度為 O(1)。
獲取鏈表的長度 len 時間複雜度 O(1)。

字典

字典數據結構極其類似 java 中的 Hashmap。

Redis的字典由三個基礎的數據結構組成。最底層的單位是哈希表節點。結構如下：

typedef struct dictEntry {
    
    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個哈希表節點，形成鏈表
    struct dictEntry *next;

} dictEntry;

實際上哈希表節點就是一個單項列表的節點。保存了一下下一個節點的指針。 key 就是節點的鍵，v是這個節點的值。這個 v 既可以是一個指針，也可以是一個 uint64_t或者 int64_t 整數。*next 指向下一個節點。

通過一個哈希表的數組把各個節點鏈接起來：
typedef struct dictht {

    // 哈希表數組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩碼，用於計算索引值
    // 總是等於 size - 1
    unsigned long sizemask;

    // 該哈希表已有節點的數量
    unsigned long used;

} dictht;

dictht

通過圖示我們觀察：

實際上，如果對java 的基本數據結構瞭解的同學就會發現，這個數據結構和 java 中的 HashMap 是很類似的，就是數組加鏈表的結構。

字典的數據結構：

typedef struct dict {

    // 類型特定函數
    dictType *type;

    // 私有數據
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 當 rehash 不在進行時，值為 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在運行的安全迭代器的數量
    int iterators; /* number of iterators currently running */

} dict;

其中的dictType 是一組方法，代碼如下：

redis續集

鏈表

字典

dict的數據結構定義

dict的創建（dictCreate）

dict的查找（dictFind）

dict的插入（dictAdd和dictReplace）

dict的刪除（dictDelete）

sds的數據結構定義

Redis dict結構舉例

sds的創建和銷毀

sds的連接（追加）操作

淺談sds與string的關係

什麼是ziplist

ziplist的數據結構定義

ziplist的介面

ziplist的插入邏輯解析

hash與ziplist