redis數(shù)據(jù)庫底層沒有直接使用c的字符串表示户誓，而是自己使用名為簡(jiǎn)單動(dòng)態(tài)字符串(simple dynamic string,SDS)
SDS定義
struct sdshdr{
int len; //記錄buf數(shù)組中以使用字節(jié)的數(shù)量痴奏，等于SDS所保存字符串的長(zhǎng)度
int free; //記錄buf數(shù)組中未使用字節(jié)的數(shù)量
char buf[]; //字節(jié)數(shù)組涉馅，用于保存字符串
}
示例
image.png
- free屬性值為0满葛，表示sds沒有分配任何為使用空間
- len屬性為5邪铲，表示這個(gè)sds保存了一個(gè)5個(gè)字節(jié)長(zhǎng)的字符串
- buf屬性表示一個(gè)char類型的數(shù)組疲憋，前五個(gè)字節(jié)保存"Redis"望拖，而最后一個(gè)字節(jié)保存空字符'\0'
注：SDS遵循空字符結(jié)尾的好處是：SDS可以直接重用一部分c字符串函數(shù)庫的函數(shù)渺尘，比如直接打印字符串printf
SDS與C字符串的區(qū)別
1. 獲取字符串長(zhǎng)度時(shí)間復(fù)雜度不同(提高獲取字符串長(zhǎng)度性能)
- 普通C字符串獲取長(zhǎng)度需要遍歷整個(gè)字符串，因此復(fù)雜度為O(N)说敏。
- SDS的len屬性直接保存字符串的長(zhǎng)度鸥跟，復(fù)雜度為O(1)
2. SDS杜絕緩沖區(qū)溢出
- C:比如說，拼接字符串函數(shù)char *strcat(char *dest,const char *sec)，當(dāng)dest不足夠存放src所有內(nèi)容時(shí)医咨，就會(huì)產(chǎn)生緩沖區(qū)溢出
- SDS:SDS有自己的空間分配策略枫匾，當(dāng)SDS的API對(duì)字符串操作時(shí)，API會(huì)先檢查SDS的空間是否滿足操作拟淮，不滿足的話API會(huì)自動(dòng)將SDS的空間擴(kuò)展至所需大小干茉，然后才執(zhí)行操作
3. 減少修改字符串帶來的內(nèi)存重分配次數(shù)
- 當(dāng)C需要修改字符串長(zhǎng)度時(shí)，我們需要再次對(duì)使用內(nèi)存重新分配很泊，由于內(nèi)存重新分配設(shè)計(jì)復(fù)雜的算法角虫，并且可能執(zhí)行系統(tǒng)調(diào)用，所以通常是比較耗時(shí)的操作
- SDS的空間預(yù)分配跟惰性空間釋放會(huì)對(duì)字符串的內(nèi)存分配次數(shù)進(jìn)行優(yōu)化
1.空間預(yù)分配
- 如果對(duì)SDS修改后委造，SDS的長(zhǎng)度(len)<1MB上遥，則程序?qū)⒎峙浜蚻en屬性同樣大小的free空間
- 如果對(duì)SDS修改后，SDS的長(zhǎng)度(len)>1MB争涌，則程序?qū)⒎峙?MB的free空間
2.惰性空間釋放
- 惰性空間釋放用于優(yōu)化SDS縮短的操作粉楚，當(dāng)SDS縮短時(shí)，程序不會(huì)立即進(jìn)行內(nèi)存重新分配亮垫，而是用free保存多余出來的字節(jié)模软，方便未來使用
4.二進(jìn)制安全
- C字符串中的字符除了末尾外，不能包含空字符饮潦，否則會(huì)被識(shí)別成字符串結(jié)尾
- SDS可以用來保存二進(jìn)制數(shù)據(jù)燃异，所以SDS的API都是二進(jìn)制安全(binary-safe)的，所有的SDS API 會(huì)以處理二進(jìn)制方式來處理buf的數(shù)據(jù)继蜡。因此數(shù)據(jù)寫入是什么樣的回俐，讀取出來就是什么樣的。
5.兼容部分C字符串函數(shù)
- 雖然SDS的API是二進(jìn)制安全的稀并，但其也遵循C字符串以空字符結(jié)尾的慣例：這些API總會(huì)將SDS保存的末尾設(shè)置為空字符仅颇，并且總會(huì)在為buf數(shù)組分配空間時(shí)多分配一個(gè)字節(jié)來容納這個(gè)空字符，為了讓保存文本數(shù)據(jù)的SDS可以重用<string.h>定義的函數(shù)
總結(jié)
| C字符串 | SDS |
|---|---|
| 獲取字符串長(zhǎng)度復(fù)雜度為O(N) | 獲取字符串長(zhǎng)度復(fù)雜度為O(1) |
| API是不安全的碘举，可能造成緩沖區(qū)溢出 | API是安全的忘瓦，不會(huì)成緩沖區(qū)溢出 |
| 修改字符串長(zhǎng)度N次必然需要執(zhí)行N次內(nèi)存重新分配 | 修改字符串長(zhǎng)度N次最多需要執(zhí)行N次內(nèi)存重新分配 |
| 只能保存文本數(shù)據(jù) | 可以保存文本數(shù)據(jù)和二進(jìn)制數(shù)據(jù) |
| 可以使用所有<string.h>庫中的函數(shù) | 可以使用部分<string.h>庫中的函數(shù) |
