redis放棄了很多c語(yǔ)言內(nèi)置的數(shù)據(jù)結(jié)構(gòu)椅野，自己實(shí)現(xiàn)了很多自己的數(shù)據(jù)結(jié)構(gòu)瞒瘸，這些數(shù)據(jù)結(jié)構(gòu)很優(yōu)質(zhì)双戳，提供了很多內(nèi)置的指令都是常數(shù)復(fù)雜度的戏蔑。從中可以體會(huì)到一個(gè)優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)是多么的賞心悅目叹洲。
簡(jiǎn)單動(dòng)態(tài)字符串
C語(yǔ)言中的字符串使用的長(zhǎng)度為N+1的字符數(shù)組來(lái)表達(dá)長(zhǎng)度為N的字符串,
而且字符數(shù)組的最后一個(gè)元素總是ascll碼表中的空字符'\0'
下面來(lái)介紹redis中字符串的實(shí)現(xiàn)
redis的字符串的優(yōu)點(diǎn)有
1.常數(shù)復(fù)雜度獲取字符串長(zhǎng)度
2.緩沖區(qū)不會(huì)溢出
3.字符串修改內(nèi)存分配次數(shù)少
4.保證二進(jìn)制安全
5.兼容部分C字符串函數(shù)
概述reids中字符串的實(shí)現(xiàn)以及數(shù)據(jù)結(jié)構(gòu)柠硕。
????????reids中的字符串確切的來(lái)說(shuō)全稱為"簡(jiǎn)單動(dòng)態(tài)字符串(SDS)"。他除了可以保存數(shù)據(jù)庫(kù)中的字符串之外,還可以被用作緩沖區(qū)：如AOF緩沖區(qū)(持久化指令)等运提。
redis的字符串的數(shù)據(jù)結(jié)構(gòu)定義如下,這也是為什么可以做到字符串長(zhǎng)度為常數(shù)時(shí)間復(fù)雜度的原因
struct sds.h/sdshdr{
int len;//用來(lái)記錄保存的字符串長(zhǎng)度,也就是用來(lái)記錄buf數(shù)組中已使用字節(jié)數(shù)量
int free;//用來(lái)保存數(shù)組中未使用字節(jié)的數(shù)量
char buf[];//保存字符串?dāng)?shù)組
}
如上圖
? free屬性值為0蝗柔，表示sds沒(méi)有可分配的剩余空間
? len屬性為5，表示sds保存一個(gè)長(zhǎng)度為5字節(jié)的字符串
? buf則表示記錄了這個(gè)存放字符串的字符數(shù)組,最后一個(gè)字節(jié)保存了空字符'\0'
? sds也遵循C語(yǔ)言中字符串定義標(biāo)準(zhǔn),以空字符串結(jié)尾,保存的空字符不記錄進(jìn)字符串長(zhǎng)度也就是len屬性中民泵，而且為字符串分配額外的1字節(jié)空間癣丧。為什么遵循以空字符結(jié)尾,好處在于可以重用C語(yǔ)言的部分代碼，而不用去寫單獨(dú)的實(shí)現(xiàn)栈妆。
1.如何實(shí)現(xiàn)了以常數(shù)復(fù)雜度獲取字符串長(zhǎng)度
在c語(yǔ)言中獲取一個(gè)字符串的長(zhǎng)度是遍歷整個(gè)字符數(shù)組,掃到空字符時(shí)為止,整個(gè)操作的時(shí)間復(fù)雜度為O(N)
redis的數(shù)據(jù)結(jié)構(gòu),因?yàn)榇鎯?chǔ)了存儲(chǔ)的字符串長(zhǎng)度的屬性,所以時(shí)間復(fù)雜度為O(1)胁编，
那么在redis中STRLEN命令的復(fù)雜度復(fù)雜度為O(1)
2.如何杜絕緩沖區(qū)溢出
c語(yǔ)言中字符串不記錄自身長(zhǎng)度,由于數(shù)據(jù)的內(nèi)存空間是一定的,當(dāng)在使用<string.h>/strcat函數(shù)時(shí),
可以將源字符串拼接到目的字符串末尾。但是c語(yǔ)言中字符數(shù)組內(nèi)存容納不了如此多的字符串,那么就會(huì)
緩沖區(qū)溢出鳞尔。造成源字符串的內(nèi)容溢出到目的字符串,導(dǎo)致目的字符串內(nèi)容被修改
但是在redis的數(shù)據(jù)結(jié)構(gòu)中,redis的api會(huì)去檢查sds空間是否滿足修改的要求,如果不滿足自動(dòng)進(jìn)行擴(kuò)容
3.如何減少修改字符串帶來(lái)內(nèi)存重分配次數(shù)
c語(yǔ)言字符串并不記錄自身長(zhǎng)度,對(duì)于一個(gè)包含N個(gè)字符的字符串來(lái)說(shuō),總是需要一個(gè)長(zhǎng)度為N+1的字符數(shù)組來(lái)承載他
所以在每次改變字符串長(zhǎng)度的時(shí)候總會(huì)重新分配地址嬉橙。
如果程序是增長(zhǎng)字符串操作,如果數(shù)組空間不夠,就要擴(kuò)容，如果忘記就會(huì)緩沖區(qū)溢出
如果執(zhí)行縮短字符串操作,在執(zhí)行之后,多余的內(nèi)存要釋放,如果忘記釋放,就會(huì)內(nèi)存泄露寥假。
一般程序下修改字符串長(zhǎng)度操作不經(jīng)常出現(xiàn),那么修改一次耗費(fèi)資源是可以接受的市框。
redis的使用場(chǎng)景經(jīng)常是對(duì)速度要求嚴(yán)格，數(shù)據(jù)頻繁修改,如果經(jīng)常重新分配內(nèi)存會(huì)造成性能問(wèn)題糕韧。
在redis中SDS實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略拾给。
1.空間預(yù)分配
2.惰性空間釋放
