Redis資料結構——SDS簡單動态字元串

1，C語言中定義的字元串是以空字元結尾的字元數組，而Redis中自己建構了一種名為簡單動态字元串（simple dynamic string，SDS）的抽象類型。

2，sds的結構如下：

struct sdshdr{
//記錄buf數組中已使用位元組的數量
//等于SDS所儲存的字元串長度
int len;

//記錄buf數組中未使用位元組的數量
int free;

//位元組數組，用于儲存字元串
char buf[];
}
           

3，SDS與C字元串的差別

1）常數複雜度擷取字元串長度，程式計算C字元串的長度的方法是周遊整個字元串，直到遇到空字元為止。這個操作的複雜度為O（N），而SDS在len屬性中記錄了SDS的長度，是以O（1）複雜度就可以擷取。其實程式重複執行strlen函數也不會影響系統性能。

2）杜絕緩沖區溢出

因為C字元串不記錄自身的長度，使用strcat函數的時候，不會先檢測記憶體夠不夠，這就有可能造成緩沖區溢出。

SDS的空間配置設定政策杜絕了發生緩沖區溢出的可能性。當SDS的API需要對SDS進行修改時，API會先檢查SDS的空間是否滿足修改所需的要求，如果不滿足要求的話，API會自動将SDS的空間擴充至執行修改所需的大小。

3）SDS可以減少修改字元串時帶來的記憶體重配置設定次數

因為C字元串底層實作總是一個N+1個字元長度的數組，因為C字元串的長度和底層數組的長度之間存在着這種關聯性，是以每次增長或縮短C字元串，程式總會對儲存C字元串的數組進行一次記憶體重配置設定操作：

如果程式執行的是增長字元串的操作，比如拼接操作，那麼在執行這個操作之前，程式需要先通過記憶體重配置設定來擴充底層數組空間大小——如果忘了這一步就會産生緩沖區溢出；

如果執行的是縮短字元串的操作，比如截斷操作，那麼在執行這個操作之後，程式需要通過記憶體重配置設定來釋放字元串不再使用的那部分空間——如果忘了這一步就會産生記憶體洩漏。

SDS的額外配置設定的未使用空間數量由以下公式決定：

如果對SDS進行修改後，SDS的長度小于1MB，那麼程式配置設定和len屬性同樣大小的未使用空間。如果修改後SDS的長度大于1MB，程式會配置設定1MB的未使用空間。

SDS的惰性空間釋放并不是真正的釋放空間，而是将要釋放的空間加到free裡面。

4）SDS是二進制安全的，SDS的API都會以處理二進制的方式來處理SDS存放在buf數組裡的資料，資料在寫入時什麼樣，它被讀出時就是什麼樣。**Redis不是用buf這個數組來儲存字元，而是用它來儲存一系列二進制資料。**使用SDS來儲存特殊資料格式就沒有任何問題，因為SDS使用len屬性的值而不是空字元來判斷字元串是否結束。

5）SDS可以使用一部分C字元串函數