一、SDS 簡單動態(tài)字符串

Redis 在存儲 可能發(fā)生改變、非字面量 的字符串時饶氏，都會使用 SDS芹橡，比如：redis 的 key 和 value 等毒坛。

1. 結(jié)構(gòu)體定義

struct sdshdr{
    // 字符串真是長度
    int len;
    // buf 中空閑的長度
    int free;
    // 存儲字符串的 char 數(shù)組
    char buf[];
}

• len，字符串真實長度林说。
• free煎殷，buf 中空閑的長度（與 預(yù)分配 和 惰性釋放 有關(guān)）
• buf，用于存儲字符串的 char 數(shù)組腿箩。

2. SDS 和 C 字符串的區(qū)別

• SDS 獲取字符串長度的時間復(fù)雜度是 O(1)豪直，C 獲取字符串長度的時間復(fù)雜度是 0(n)
• 通過 SDS 的 API 操作字符串（末尾追加、截取等）完全避免了 內(nèi)存的溢出和泄露珠移，而 C 字符串則需要手動維護(hù)內(nèi)存弓乙，存在溢出和泄露風(fēng)險。
• SDS 減少了 內(nèi)存分配的次數(shù)
  • 內(nèi)存預(yù)分配：SDS 通過 alloc = (len <= 1024) ? 2 * len : len + 1024 的方式钧惧，預(yù)留了一部分內(nèi)存空間暇韧，相比 C 字符串，在 增加字符串長度 的場景上浓瞪，有效的減少了內(nèi)存分配的次數(shù)懈玻。
  • 惰性釋放：SDS 在釋放空間時，并不立即釋放空間乾颁，而是 在 free 字段中記錄了【空閑】空間的長度涂乌，等待未來使用。C 字符串則每次都需要手動釋放钮孵。且 SDS 的 API 也支持像 C 字符串那樣的 立即釋放骂倘。
• 相比 C 字符串，SDS 是 二進(jìn)制安全的（不會像 C 字符串一樣巴席，以為空格是結(jié)尾）

二历涝、鏈表

redis 通過鏈表，實現(xiàn)了 隊列 相關(guān)的操作漾唉。

1. 結(jié)構(gòu)體

• 鏈表節(jié)點：listNode（雙向）

typedef struct listNode {
    // 前置節(jié)點
    struct listNode *prev;
    // 后置節(jié)點
    struct listNode *next;
    // 節(jié)點值
    void *value;
} listNode;

• 鏈表：list

typedef stuct list {
    // 頭結(jié)點
    listNode *head;
    // 尾節(jié)點
    listNode *tail;
    // 鏈表長度
    unsigned long len;
    // 節(jié)點復(fù)制函數(shù)
    void *(*dup)(void *ptr);
    // 節(jié)點釋放函數(shù)
    void (*free)(void *ptr);
    // 節(jié)點值對比函數(shù)
    int (*match)(void *ptr, void *key);
} list;

2. 特點

• 雙向：獲取某個節(jié)點的前置荧库、后置節(jié)點的時間負(fù)責(zé)度是 0(1)
• 無環(huán)：head.prev 和 tail.next 是 null
• 帶頭、尾指針：獲取鏈表的 表頭節(jié)點 和 表尾節(jié)點 的時間復(fù)雜度是 O(1)

3. 部分API

三赵刑、字典

詳見：
redis 源碼分析（一）HashTable 上篇
redis 源碼分析（二）HashTable 下篇

四分衫、跳躍表

redis 的有序結(jié)合，當(dāng)有序集合的 元素數(shù)量比較多 或者 元素的值是比較長的字符串 時般此，redis 使用跳躍表來實現(xiàn) 有序集合蚪战。

1. 結(jié)構(gòu)體

• 節(jié)點：zskiplistNode

typedef struct zskiplistNode {
    // 前一個節(jié)點的指針
    struct zskiplistNode *backword;
    // 當(dāng)前節(jié)點的分值
    double score;
    // 當(dāng)前節(jié)點的值對象
    robj *obj;
    struct zskiplistLevel {
        // 下一個節(jié)點的指針
        zskiplistNode *forword;
        // 到下一個節(jié)點的跨度
        unsigned int span;
    } level[];
    
} zskiplistNode;

• 跳躍表：zskiplist

typedef struct zskiplist {
    // 跳躍表頭節(jié)點
    struct zskiplistNode *head;
    // 跳躍表尾節(jié)點
    struct zskiplistNode *tail;
    // 跳躍表的長度
    unsigned long length;
    // 跳躍表中層數(shù)最大的節(jié)點的層數(shù)
    int level;
} zskiplist;

2. 有序集合的 查找

• 普通的雙向鏈表節(jié)點：DoubleLinkedListNode

typedef struct DoubleLinkedListNode {
    // 后一個節(jié)點的指針
    struct DoubleLinkedListNode *next;
    // 前一個節(jié)點的指針
    struct DoubleLinkedListNode *prev;
    // 當(dāng)前節(jié)點的分值
    double score;
    // 當(dāng)前節(jié)點的值對象
    robj *obj;
} DoubleLinkedListNode;

• 普通的雙向鏈表節(jié)點牵现，查找的邏輯就是遍歷，時間復(fù)雜度是 O(n)
  
  10萬元素跳躍表.png

如上圖邀桑，假設(shè)一個跳躍表存儲了 a1 到 a100001 這 10 萬個元素瞎疼，他們的分?jǐn)?shù)分別是 1.0 到 100001.0

• 上述跳躍表有 五層：
  • 第一層跨度為1，即：1->2->3...
  • 第二層跨度為10壁畸，即：1->11->21...
  • 第三層跨度為100贼急，即：1->101->201...
  • 第四層跨度為1000，即：1->1001->2001...
  • 第五層跨度為10000捏萍，即：1->10001->20001...
• 查找 65536 的過程：
  1. 第五層 查找 （8次） ：1->10001->20001->30001->40001->50001->60001太抓，看到 70001 時發(fā)現(xiàn)：比 65536 大，去 第四層 繼續(xù)查找令杈。
  2. 第四層 查找 （6次）：61001->62001->63001->64001->65001走敌，看到 66001 時發(fā)現(xiàn)：比 65536 大，去 第三層 繼續(xù)查找这揣。
  3. 第三層 查找 （6次）：65101->65201->65301->65401->65501悔常，看到 65601 時發(fā)現(xiàn)：比 65536 大，去 第二層 繼續(xù)查找给赞。
  4. 第二層 查找 （4次）：65511->65521->65531机打，看到 65541 時發(fā)現(xiàn)：比 65536 大，去 第一層 繼續(xù)查找片迅。
  5. 第一層 查找 （4次）：65532->65533->65534残邀，看到 65535 時發(fā)現(xiàn)目標(biāo)，得到結(jié)果柑蛇。
• 結(jié)論：
  • 跳躍表的節(jié)點芥挣，將普通雙向鏈表的節(jié)點的 next 指針，從1個升級到了多個耻台，以層的方式管理空免。
  • 不同層級的指針，跨度不一樣：第一層就是普通雙向鏈表節(jié)點的 next 指針盆耽。以后的各層蹋砚，跨度不斷增大，以達(dá)到 跳過一些節(jié)點摄杂，進(jìn)行查找的目的坝咐。
  • 指針的層數(shù)越高，對查找的性能優(yōu)化越明顯析恢，即：時間復(fù)雜度從 O(n) 減少到了 O(logN)

3. 其他有序集合操作

其他有序集合操作墨坚，像 范圍查找（正向、逆向）映挂、是否存在 等泽篮，其實都是基于 查找 的結(jié)果盗尸，利用 前置、后置指針 進(jìn)行的遍歷咪辱。

五振劳、整數(shù)集合

當(dāng)集合中的元素都是整數(shù)時椎组，Redis 會使用 整數(shù)集合 作為集合的底層實現(xiàn)

1. 結(jié)構(gòu)體

typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    // 集合長度
    uint32_t length;
    // 集合元素
    int8_t contents[];
} intset;

其中油狂，encoding 指明了 contents 中的數(shù)據(jù)類型：

• INTSET_ENC_INT16，范圍：[-2^15=-32768, 2^15-1=32767]
• INTSET_ENC_INT32寸癌，范圍：[-2^31=-2147483648, 2^31-1=2147483647]
• INTSET_ENC_INT64专筷，范圍：[-2^63, 2^63-1]

2. 編碼升級

當(dāng)一個編碼為更小范圍，如 INTSET_ENC_INT16 蒸苇，的整數(shù)集合磷蛹，要添加一個更大范圍，如 INTSET_ENC_INT32溪烤，的元素時味咳，整體集合的編碼方式需要升級。具體思路是：

• 根據(jù)新元素的類型和集合的元素數(shù)量檬嘀，擴展集合空間槽驶。
• 將集合中的其他元素升級，并保證之前的有序順序鸳兽。
• 將新元素添加到集合中（因為范圍更大掂铐，所以位置一定是：第一個或者最后一個）

3. 升級的好處

• 集合更加靈活。屏蔽了不同范圍整數(shù)的存儲實現(xiàn)揍异。
• 更加節(jié)省空間全陨。在有需要的時候再進(jìn)行升級，避免了一開始就使用 INTSET_ENC_INT64 來存儲集合元素衷掷。

4. 不存在降級

升級后的整數(shù)集合辱姨，并不會因為，唯一一個更大范圍的元素被刪除戚嗅，就進(jìn)行降級雨涛。