国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

深入理解Redis 數(shù)據(jù)結(jié)構(gòu)—簡單動態(tài)字符串sds

番茄西紅柿 / 3003人閱讀

摘要:本文主要介紹的數(shù)據(jù)結(jié)構(gòu)簡單動態(tài)字符串簡稱。遵守字符串以空字符串結(jié)尾的慣例,保存的空字符串一個字節(jié)空間不計算在的屬性里面。添加空字符串到字符串末尾等操作,都是由函數(shù)自動完成的,所以這個空字符對于使用者來說完全是透明的。

Redis是用ANSI C語言編寫的,它是一個高性能的key-value數(shù)據(jù)庫,它可以作用在數(shù)據(jù)庫、緩存和消息中間件。其中 Redis 鍵值對中的鍵都是 string 類型,而鍵值對中的值也是有 string 類型,在 Redis 中 string 類型運用還是很廣泛的。本文主要介紹 string 的數(shù)據(jù)結(jié)構(gòu)—— 簡單動態(tài)字符串(Simple Dynamic String) 簡稱sds。

sds 實現(xiàn)

sds 的數(shù)據(jù)結(jié)構(gòu):

struct sdshdr {     //buf 已占用的長度     int len;     // buf 剩余的可用的長度     int free;        // 保存字符串數(shù)據(jù)的地方     char buf[]; }

結(jié)構(gòu) sdshdr 保存了 len、free 和 buf 三個屬性,分別記錄字符的已使用的長度,未使用的長度,以及實際保存字符串的數(shù)組。
以下是一個新建的,保存 hello world 字符串的 sdshdr 結(jié)構(gòu):

struct sdshdr {    len = 5;    free = 0;    buf = "hello/0"; }
  • free 屬性值為0,表示這個sds沒有分配未使用的空間。
  • len 屬性值為5,表示這個sds保存了一個五字節(jié)長的字符串。
  • buf 屬性是一個 char 類型的數(shù)組,數(shù)組的前五個字節(jié)分別保存了 h、e、l、l、o 五個字符,而最后一個字節(jié)保存了空字符/0。

sds 遵守 C 字符串以空字符串結(jié)尾的慣例,保存的空字符串一個字節(jié)空間不計算在 sds 的 len 屬性里面。添加空字符串到字符串末尾等操作,都是由 sds 函數(shù)自動完成的,所以這個空字符對于使用者來說完全是透明的。

通過 len 屬性,可以實現(xiàn)時間復雜度 O(1) 的長度計算。另外通過對 buf 分配一些額外的空間,并使用 free 記錄未使用空間的長度,sdshdr 可以減少內(nèi)存的重新分配。這是 sds 相對 c 字符串的一個優(yōu)勢。

為何 Redis 不用 C 語言表示字符串

Redis 是使用 C 語言開發(fā)的,而在使用最多的字符串上,Redis 沒有使用 C 語言傳統(tǒng)的字符串表示,而且使用自己構(gòu)建的簡單動態(tài)字符串(sds)
在 C 語言中,字符串可以用一個 /0 結(jié)尾的 char 數(shù)組表示。比如 hello world 在 C 語言中就可以表示為"hello world/0"。數(shù)組一般初始化以后長度就已經(jīng)固定了,不能支持字符串追加append長度計算操作:

  • 每次計算字符串長度都要遍歷一遍數(shù)組,所以時間復雜度是O(N)
  • 對字符串每次進行追加操作,需要對字符串進行一次內(nèi)存分配

sds 優(yōu)化追加字符操作

Redis 作為數(shù)據(jù)庫,對于查詢速度要求嚴格,數(shù)據(jù)修改也比較頻繁,如果每次修改字符串都需要執(zhí)行一次內(nèi)存分配的話,都會占用大量的時間。所以 Redis 選擇了 sds 而不是 C 字符串,sds 可以減少追加字符的內(nèi)存分配。通過舉例來說明,執(zhí)行以下操作時,sds 內(nèi)部的變化:

redis> set msg "hello world"OKredis> append msg " again"(integer)18redis> get msg"hello world again"

首先 set 命令創(chuàng)建并保存hello world 到一個 sdshdr 中,這個 sdshdr 的值如下:

struct sdshdr {     len = 11;     free = 0;     buf = "hello world/0";}

當執(zhí)行 append 命令時,相對應的 sdshdr 被更新,字符串 " again" 會被追加到原來的 "hello world" 之后:

struct sdshdr {     len = 17;     free = 17;     buf = "hello world again/0                ";}

當調(diào)用 set 命令創(chuàng)建 sdshdr 時,Redis 沒有給 sdshdr 分配多余的空間,free 屬性為0。而在執(zhí)行 append 操作之后,Redis 為 buf 分配了多于所需空間一倍的大小。

在執(zhí)行 append 命令之后,保存 "hello world again" 共需要17 + 1 個字節(jié),但是程序為 sdshdr 分配了 17 + 17 + 1 = 35 個字節(jié),而后續(xù)如果在對 sdshdr 進行追加操作,只要追加的長度不超過 free 屬性值,那么就不需要對 buf 進行內(nèi)存重分配。

比如執(zhí)行以后命令并不會引起 buf 的內(nèi)存重分配,因為新追加的字符串長度小于17:

redis> append msg  " again"(integer) 23

對應的 sdshdr 結(jié)構(gòu)如下:

struct sdshdr {     len = 23;     free = 11;     buf = "hello world again again/0               ";}

redis 內(nèi)存分配可以查看源碼 sds.s/sdsMakeRoomFor,sdsMakeRoomFor 函數(shù)描述了內(nèi)存分配的策略,下面的該函數(shù)的偽代碼:

// sdshdr:追加前的字符// addlen:追加字符串sds sdsMakeRoomFor(sdshdr, addlen) {       // 多余空間大于追加空間,無序再分配內(nèi)存,直接返回    if (free >= addlen) return s;    // 計算新字符的長度    newlen = (len+addlen);    // 如果新字符的長度小于 SDS_MAX_PREALLOC,就分配兩倍新字符空間  //  如果新字符的長度大于 SDS_MAX_PREALLOC,就分配新字符空間 + SDS_MAX_PREALLOC 空間    if (newlen < SDS_MAX_PREALLOC)        newlen *= 2;    else        newlen += SDS_MAX_PREALLOC;    // 分配內(nèi)存    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);    // 更新 free 屬性    newsh.free = newlen - len;    return newsh;}

而對于字符的縮短操作,Redis 保存縮短后的字符串,此時并不會進行內(nèi)存重分配,而是使用 free 屬性記錄縮短的字符長度。

總結(jié)

Redis 的 string 類型為何使用sds而不是 C 字符串,因為sds有兩點優(yōu)勢:

  • 計算字符長度,C 字符串復雜度O(n),而 sds 復雜度為 O(1)
  • 字符追加操作,C 字符串每次都需要對內(nèi)存進行重分配,而 sds 每次會進行動態(tài)擴容,當添加字符小于空閑字符時,不會對內(nèi)容進行分配,減少系統(tǒng)等待時間

參考

Redis 設計與實現(xiàn)

如果覺得文章對你有幫助的話,請點個推薦吧!

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/125679.html

相關文章

  • Redis專題(2):Redis數(shù)據(jù)結(jié)構(gòu)底層探秘

    摘要:用指令來看一個值的數(shù)據(jù)結(jié)構(gòu)。對象只有同時滿足下面兩個條件時,才會使用壓縮列表哈希中元素數(shù)量小于個哈希中所有鍵值對的鍵和值字符串長度都小于字節(jié)。采用了鏈地址法的方法解決了哈希沖突的問題。數(shù)據(jù)類型的底層可以是整數(shù)集或者是散列表也叫哈希表。 前言 上篇文章 Redis閑談(1):構(gòu)建知識圖譜介紹了redis的基本概念、優(yōu)缺點以及它的內(nèi)存淘汰機制,相信大家對redis有了初步的認識。互聯(lián)網(wǎng)的很...

    evin2016 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<