Redis設計與實作讀書筆記（第一章）

一：内部資料結構與對象

1.sds的定義：

Struct sdshdr{

//記錄buf數組中已使用的位元組的數量 儲存字元串的長度

Int len;

//數組中未使用的位元組的數量

Int free;

//位元組數字，用于儲存字元串

Char buf[]；

}

SDS遵循C字元串以空字元結尾。

2.SDS與C字元串的差別

C語言的使用長度是N+1的字元數組來表示長度為N的字元串。

C字元串不能記錄自身的長度，是以擷取C字元串的長度需要編目整個字元串，這個操作的複雜度為O（N）.

和 C 字元串不同， 因為 SDS 在 len 屬性中記錄了 SDS 本身的長度， 是以擷取一個 SDS 長度的複雜度僅為 O(1) 。

舉個例子， 對于圖 2-5 所示的 SDS 來說， 程式隻要通路 SDS 的 len 屬性， 就可以立即知道 SDS 的長度為 5 位元組。

除了擷取字元串長度的複雜度高之外， C 字元串不記錄自身長度帶來的另一個問題是容易造成緩沖區溢出（buffer overflow）。

與 C 字元串不同， SDS 的空間配置設定政策完全杜絕了發生緩沖區溢出的可能性： 當 SDS API 需要對 SDS 進行修改時， API 會先檢查 SDS 的空間是否滿足修改所需的要求， 如果不滿足的話， API 會自動将 SDS 的空間擴充至執行修改所需的大小， 然後才執行實際的修改操作， 是以使用 SDS 既不需要手動修改 SDS 的空間大小， 也不會出現前面所說的緩沖區溢出問題。

總結：

表 2-1 C 字元串和 SDS 之間的差別

SDS	C字元串
擷取字元串長度的複雜度為  。	擷取字元串長度的複雜度為  。
API 是安全的，不會造成緩沖區溢出。	API 是不安全的，可能會造成緩沖區溢出。
修改字元串長度 N 次最多需要執行 N 次記憶體重配置設定。	修改字元串長度 N 次必然需要執行 N 次記憶體重配置設定。
可以儲存文本或者二進制資料。	隻能儲存文本資料。
可以使用一部分 <string.h> 庫中的函數。	可以使用所有 <string.h> 庫中的函數。

3.SDS API

函數	作用	時間複雜度
sdsnew	建立一個包含給定 C 字元串的 SDS 。	O(N) ， N 為給定 C 字元串的長度。
sdsempty	建立一個不包含任何内容的空 SDS 。	O(1)
sdsfree	釋放給定的 SDS 。	O(1)
sdslen	傳回 SDS 的已使用空間位元組數。	這個值可以通過讀取 SDS 的 len 屬性來直接獲得， 複雜度為 O(1)。
sdsavail	傳回 SDS 的未使用空間位元組數。	這個值可以通過讀取 SDS 的 free 屬性來直接獲得， 複雜度為 O(1)。
sdsdup	建立一個給定 SDS 的副本（copy）。	O(N) ， N 為給定 SDS 的長度。
sdsclear	清空 SDS 儲存的字元串内容。	因為惰性空間釋放政策，複雜度為  。
sdscat	将給定 C 字元串拼接到 SDS 字元串的末尾。	O(N)， N 為被拼接 C 字元串的長度。
sdscatsds	将給定 SDS 字元串拼接到另一個 SDS 字元串的末尾。	O(N) ， N 為被拼接 SDS 字元串的長度。
sdscpy	将給定的 C 字元串複制到 SDS 裡面， 覆寫 SDS 原有的字元串。	O(N)， N 為被複制 C 字元串的長度。
sdsgrowzero	用空字元将 SDS 擴充至給定長度。	O(N) ， N 為擴充新增的位元組數。
sdsrange	保留 SDS 給定區間内的資料， 不在區間内的資料會被覆寫或清除。	O(N)， N 為被保留資料的位元組數。
sdstrim	接受一個 SDS 和一個 C 字元串作為參數， 從 SDS 左右兩端分别移除所有在 C 字元串中出現過的字元。	O(M*N) ， M 為 SDS 的長度， N 為給定 C 字元串的長度。
sdscmp	對比兩個 SDS 字元串是否相同。	O(N) ， N 為兩個 SDS 中較短的那個 SDS 的長度。

線上閱讀位址：

http://redisbook.com/preview/sds/different_between_sds_and_c_string.html#id2