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 是一組方法，代碼如下：