本文首發(fā)于公眾號：Hunter后端
原文鏈接：Redis數(shù)據(jù)結(jié)構(gòu)二之SDS和雙向鏈表

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

以下是本篇筆記目錄：

1. SDS
   1. 常數(shù)復(fù)雜度獲取字符串長度
   2. 杜絕緩沖區(qū)溢出
   3. 減少修改字符串帶來的內(nèi)存重分配次數(shù)
   4. 二進(jìn)制安全
   5. 兼容C字符串函數(shù)
2. 雙向鏈表

1、 SDS

SDS，simple dynamic string，即簡單動態(tài)字符串

SDS 在 Redis 2.9 版本中數(shù)據(jù)結(jié)構(gòu)如下：

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

在這個結(jié)構(gòu)中，len 表示 buf 數(shù)組中已使用字節(jié)的數(shù)量，free 表示 buf 數(shù)組中未使用字節(jié)的數(shù)量，buf 則表示是一個 char 類型的數(shù)組。

Redis 沒有復(fù)用 C字符串，有以下幾個方面的考慮和優(yōu)點。

1. 常數(shù)復(fù)雜度獲取字符串長度

C字符串并不記錄自身的長度信息，如果要獲取C字符串的長度，必須遍歷整個字符串然后計數(shù)。

SDS 結(jié)構(gòu)中有 len 屬性記錄 SDS 本身的長度，可以直接獲取。

2. 杜絕緩沖區(qū)溢出

因為 C字符串并不記錄自身的長度信息，在執(zhí)行某些操作，比如拼接字符串的時候，并不會自動查詢是否擁有足夠內(nèi)存，那么這個操作可能就會造成緩沖區(qū)溢出的問題

而 SDS 執(zhí)行相應(yīng)的字符串修改時，其 API 會先檢查 SDS 的空間是否需求，不滿足則會進(jìn)行擴(kuò)展，這個空間分配策略也就是下面要講的

3. 減少修改字符串帶來的內(nèi)存重分配次數(shù)

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

空間預(yù)分配

當(dāng) SDS API 對一個 SDS 進(jìn)行修改并需要對 SDS 進(jìn)行空間擴(kuò)展時，程序不僅會為 SDS 分配修改所需要的空間，還會為其分配額外的未使用空間

如果修改之后，SDS 的長度，也就是結(jié)構(gòu)中的 len 屬性小于 1MB，那么程序會額外分配同樣大小的未使用空間，這個時候，len 屬性和 free 屬性將相同

如果修改之后，SDS 的長度，也就是結(jié)構(gòu)中的 len 屬性大于等于 1MB，那么程序會額外分配 1MB 的未使用空間

惰性空間釋放

當(dāng)需要對SDS保存的字符串進(jìn)行縮短時，程序并不會重新分配內(nèi)存來回收多出來的字節(jié)，而是會使用 free 屬性將這些字節(jié)記錄下來，以備后面使用

4. 二進(jìn)制安全

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

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

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

5. 兼容C字符串函數(shù)

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

以下是 SDS 與 C字符串區(qū)別的總結(jié)：

在之后的的 Redis 版本對 SDS 的結(jié)構(gòu)有過更新，將 free 屬性換成了 alloc，這個屬性表示的意思是分配的空間長度。和之前的 free 屬性比較，其關(guān)系是 alloc = free + len

2、 雙向鏈表

C 語言沒有鏈表這個結(jié)構(gòu)，所以 Redis 自己設(shè)計了一個鏈表數(shù)據(jù)結(jié)構(gòu)。

在 Redis 中，鏈表節(jié)點的結(jié)構(gòu)擁有指向前置節(jié)點和后置節(jié)點的屬性。

鏈表結(jié)構(gòu)則包含鏈表表頭節(jié)點、表尾節(jié)點、節(jié)點長度等屬性，便于快速獲取鏈表相關(guān)信息。

雙向鏈表是列表對象的底層實現(xiàn)之一，什么情況下使用雙向鏈表作為列表對象的底層實現(xiàn)我們之后再介紹。

以下是鏈表節(jié)點的結(jié)構(gòu)：

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

}listNode;

在鏈表節(jié)點中，擁有前置節(jié)點和后置節(jié)點的指針構(gòu)成雙向的鏈表。

以下是鏈表的結(jié)構(gòu)：

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

在鏈表結(jié)構(gòu)中，有表頭節(jié)點和表尾節(jié)點可快速定位到鏈表的頭部和尾部，以及用有 len 屬性表示鏈表包含的節(jié)點數(shù)量。

如果想獲取更多后端相關(guān)文章，可掃碼關(guān)注閱讀：
文章來源地址http://www.zghlxwxcb.cn/news/detail-482376.html

到了這里，關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)二之SDS和雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！