Redis 數(shù)據(jù)結(jié)構(gòu)之SDS
簡單動態(tài)字符串
為了實現(xiàn)對于字符串的高效操作凤瘦，Redis 自己構(gòu)建的一種名為簡單動態(tài)字符串（SDS）的抽象數(shù)據(jù)結(jié)構(gòu)冤竹。
1拂封、SDS 數(shù)據(jù)結(jié)構(gòu)
struct sdshdr{
// 記錄buf數(shù)組中已使用的字節(jié)數(shù)量茬射，等于sds 保存字符串的長度
int len;
// 記錄buf 中未使用的字節(jié)數(shù)量
int free;
// 字節(jié)數(shù)據(jù)
char buf[];
}
2、SDS 與 C字符串的優(yōu)缺點
-
常數(shù)復(fù)雜度獲取字符串長度烘苹；
SDS 字符串長度的復(fù)雜度為O(1)躲株，而C字符串長度需要遍歷，復(fù)雜度為O(n);
-
避免緩沖區(qū)溢出镣衡；
當(dāng)對SDS進(jìn)行修改時霜定，API會檢查SDS 的空間是否滿足修改所需的要求，如果不滿足的話廊鸥，API會自動將SDS的空間擴(kuò)展至執(zhí)行修改所需的大小望浩，然后才執(zhí)行實際的修改操作；
-
減少修改字符串時帶來的內(nèi)存分配次數(shù)
對于C字符串來說惰说，如果修改字符串的長度磨德，都需要重新執(zhí)行內(nèi)存分配操作；但是對于Redis數(shù)據(jù)庫來說吆视，如果頻繁執(zhí)行內(nèi)存分配/釋放操作典挑，必然會對性能產(chǎn)生一定影響。為了避免C字符串的缺陷啦吧，SDS采用了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略您觉。
-
空間預(yù)分配
它主要解決字符串增長的操作，即通過API對增加SDS的長度時授滓，它不僅會分配實際所需的長度琳水，除此之還會額外分配一塊未使用的內(nèi)存，以便下次直接使用般堆，無需重新分配內(nèi)存在孝，對于分配的額外內(nèi)存有一下兩種策略：
- 如果對SDS修改后，它的長度小于1MB淮摔，那么程序會分配相同大兴骄凇（和len長度一致）的空間來作為未使用的空間（完成之后len=free，此時總大小為2*len）和橙；
- 如果對于SDS修改后大于1MB袍睡，那么程序只會分配1MB的內(nèi)存給未使用的空間（此時SDS總長度為len+1MB）署尤；
通過上述優(yōu)化疗涉，對于N次SDS的修改脐帝，分配內(nèi)存的操作由N次變?yōu)橹炼郚次筋搏。
-
惰性空間釋放
主要解決字符串的縮短操作仆百，即當(dāng)SDS的API縮短字符串時，縮小的空間不會立刻釋放奔脐，而是暫時作為未使用區(qū)俄周，以便后續(xù)增長時再次使用吁讨。同時，SDS提供了相應(yīng)的API峦朗，以便我們在真正使用內(nèi)存時建丧，通過API真正的釋放SDS的未使用空間。
基于SDS上面的兩個特性波势，我們可以得出如下結(jié)論：SDS在分配/釋放空間方面的優(yōu)化也提升了Redis的速度翎朱，但與此同時，如果有頻繁操作比較大的字符串時尺铣，會對Redis的內(nèi)存空間有一定浪費拴曲，同時在分配/釋放內(nèi)存的性能上也會有所損失。
-
-
二進(jìn)制安全
對于C字符串來說凛忿，字符串中不能包含空字符澈灼，否則最先被程序讀入的空字符串被誤認(rèn)為是字符串結(jié)尾，這使得C字符串只能保存文本數(shù)據(jù)店溢，而不能保存圖片叁熔、音視頻等二進(jìn)制文件。對于SDS來說床牧，所有SDS都會以處理二進(jìn)制的方式來處理SDS保存在buf數(shù)組中的內(nèi)容荣回，程序不會對里面的內(nèi)容做任何限制。
-
兼容部分C字符串函數(shù)
SDS末尾設(shè)置空字符的操作使得它可以和部分C字符串函數(shù)兼容叠赦。
