Redis是用C語言編寫的。C語言處理字符串一向是個(gè)難點(diǎn)。很容易出現(xiàn)內(nèi)存越界問題。

其它高級(jí)語言很容易實(shí)現(xiàn)的字符串拼接，在C這里卻是百般艱難。因?yàn)樾枰獙?shí)現(xiàn)計(jì)算出字符串所占內(nèi)存的大小。即不能過大（浪費(fèi)內(nèi)存），也不能太小（越界）。甚至在某個(gè)用C語言實(shí)現(xiàn)的項(xiàng)目中出現(xiàn)了這樣的代碼

?

?即，先計(jì)算出字符串的大小。然后申請(qǐng)內(nèi)存，再拼接字符串。

這樣的操作幾乎是無法忍受的。特別是當(dāng)我們的字符串構(gòu)成比較復(fù)雜，或者字符串經(jīng)常需要發(fā)生變更時(shí)。

?

redis的解決方案是使用了一個(gè)結(jié)構(gòu)體，一組操作函數(shù)，將這個(gè)復(fù)雜的操作包裝起來。

?

這樣的字符串操作中，不再出現(xiàn)字符串計(jì)算。不再出現(xiàn)動(dòng)態(tài)內(nèi)存分配。所有的這些操作都被包含在sds的操作函數(shù)中。

Redis其實(shí)是定義了一個(gè)結(jié)構(gòu)體：

并且sds為了兼容C原因的char* . 內(nèi)容依然是以\0為結(jié)尾。這點(diǎn)和nginx的ngx_string不太一樣。

?

作為strlen的替代品，sds也提供了sdslen

原來的strlen的時(shí)間復(fù)雜度是O(n),? 而sdslen的時(shí)間復(fù)雜度是O(1)

?

sds的內(nèi)存擴(kuò)容，當(dāng)內(nèi)存占用小于1M時(shí)，它每次都會(huì)擴(kuò)大為原來的兩倍。這樣平攤下來擴(kuò)容的時(shí)間復(fù)雜度也為O（1）。也是效率非常高的

當(dāng)內(nèi)存占用已超過1M時(shí)，它每次只會(huì)增長(zhǎng)1M，而不再是原來的兩倍。可以略省內(nèi)存。

?

轉(zhuǎn)載于:https://www.cnblogs.com/jackson-zhou/p/8012471.html

總結(jié)

以上是生活随笔為你收集整理的Redis源代码分析之sds, 动态数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。