本文首發於公眾號：Hunter後端
原文鏈接：Redis數據結構二之SDS和雙向鏈表

這一篇筆記介紹一下 SDS（simple dynamic string）和雙向鏈表。

以下是本篇筆記目錄：

1. SDS

   1. 常數複雜度獲取字符串長度
   2. 杜絕緩衝區溢出
   3. 減少修改字符串帶來的內存重分配次數
   4. 二進制安全
   5. 兼容C字符串函數
2. 雙向鏈表

1、 SDS

SDS，simple dynamic string，即簡單動態字符串

SDS 在 Redis 2.9 版本中數據結構如下：

struct sdshdr {
    int len;
    int free;
    char buf[];
};

在這個結構中，len 表示 buf 數組中已使用字節的數量，free 表示 buf 數組中未使用字節的數量，buf 則表示是一個 char 類型的數組。

Redis 沒有複用 C字符串，有以下幾個方面的考慮和優點。

1. 常數複雜度獲取字符串長度

C字符串並不記錄自身的長度信息，如果要獲取C字符串的長度，必須遍歷整個字符串然後計數。

SDS 結構中有 len 屬性記錄 SDS 本身的長度，可以直接獲取。

2. 杜絕緩衝區溢出

因為 C字符串並不記錄自身的長度信息，在執行某些操作，比如拼接字符串的時候，並不會自動查詢是否擁有足夠內存，那麼這個操作可能就會造成緩衝區溢出的問題

而 SDS 執行相應的字符串修改時，其 API 會先檢查 SDS 的空間是否需求，不滿足則會進行擴展，這個空間分配策略也就是下面要講的

3. 減少修改字符串帶來的內存重分配次數

C字符串每次進行字符串修改時，程序都需要手動進行內存重分配的操作，而 SDS 通過空間預分配和惰性空間釋放兩種策略對此進行了優化

空間預分配

當 SDS API 對一個 SDS 進行修改並需要對 SDS 進行空間擴展時，程序不僅會為 SDS 分配修改所需要的空間，還會為其分配額外的未使用空間

如果修改之後，SDS 的長度，也就是結構中的 len 屬性小於 1MB，那麼程序會額外分配同樣大小的未使用空間，這個時候，len 屬性和 free 屬性將相同

如果修改之後，SDS 的長度，也就是結構中的 len 屬性大於等於 1MB，那麼程序會額外分配 1MB 的未使用空間

惰性空間釋放

當需要對SDS保存的字符串進行縮短時，程序並不會重新分配內存來回收多出來的字節，而是會使用 free 屬性將這些字節記錄下來，以備後面使用

4. 二進制安全

C字符串保存的字符結尾都是以空字符結尾，所以字符串中間不能包含空字符，否則程序讀入空字符的時候就會被認為是字符串結尾，因此C字符串只能保存文本數據，不能保存圖片、音頻等這樣的二進制數據

而 SDS 的 API 都是以處理二進制的方式來處理 SDS 中存放在 buf 裏的數據，程序不會對數據做任何限制、過濾，所以 SDS 的 API 都是二進制安全的

SDS 使用 len 屬性值而不是空字符串來判斷字符串是否結束

5. 兼容C字符串函數

雖然SDS的API都是二進制安全的，但是仍然遵循C字符串以空字符結尾的慣例，而且在為 buf 數組分配空間的時候總是會多分配一個字節來容納這個空字符，所以保存文本數據的 SDS 可以重用一部分C中的函數

以下是 SDS 與 C字符串區別的總結：

在之後的的 Redis 版本對 SDS 的結構有過更新，將 free 屬性換成了 alloc，這個屬性表示的意思是分配的空間長度。和之前的 free 屬性比較，其關係是 alloc = free + len

2、 雙向鏈表

C 語言沒有鏈表這個結構，所以 Redis 自己設計了一個鏈表數據結構。

在 Redis 中，鏈表節點的結構擁有指向前置節點和後置節點的屬性。

鏈表結構則包含鏈表表頭節點、表尾節點、節點長度等屬性，便於快速獲取鏈表相關信息。

雙向鏈表是列表對象的底層實現之一，什麼情況下使用雙向鏈表作為列表對象的底層實現我們之後再介紹。

以下是鏈表節點的結構：

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

}listNode;

在鏈表節點中，擁有前置節點和後置節點的指針構成雙向的鏈表。

以下是鏈表的結構：

typedef struct list{
    // 表頭節點
    listNode *head;
    
    // 表尾節點
    listNode *tail;
    
    // 鏈表包含的節點數量
    unsigned long len;
    
    ...
}list;

在鏈表結構中，有表頭節點和表尾節點可快速定位到鏈表的頭部和尾部，以及用有 len 屬性表示鏈表包含的節點數量。

如果想獲取更多相關文章，可掃碼關注閲讀：