淺談一下Redis的數(shù)據(jù)結(jié)構(gòu)
一、簡單動態(tài)字符串SDS
struct sdshdr { int len; int free; char[] buf; }
簡單字符串結(jié)構(gòu)被用于存儲redis的key對象和String類型的value對象
其中的free和len字段可以輕松的使得在該字符串被修改時判斷是否需要擴容。
為啥呢?因為redis的協(xié)議發(fā)送一個SET請求時格式開頭會帶上需要插入的value的長度,這樣根據(jù)free以及l(fā)en可以判斷此時redis分配的數(shù)組大小是多少,需不需要擴容。對比于C語言的O(n)復(fù)雜度計算數(shù)組長度更快。
擴容策略:如果字符串大小<1MB, 每次擴容為2n+1大?。蝗绻笥?MB,每次擴容1MB。
二、鏈表
鏈表結(jié)構(gòu)用于存儲list類型的鍵值(類似index),還有發(fā)布訂閱等功能也用了鏈表結(jié)構(gòu)。
鏈表節(jié)點:ListNode
鏈表:list
代碼塊
typedef struct list{ ListNode * tail; ListNode * head; unsigned long len; //節(jié)點值復(fù)制方法 void *(*dup) (void * ptr); //節(jié)點值釋放方法 void *(*free) (void * ptr); //節(jié)點值對比方法 int (*match)(void * ptr, void * key); }
list+ListNode的鏈表結(jié)構(gòu)
三、字典
哈希表的結(jié)構(gòu):
字典的結(jié)構(gòu):
typedef struct dict{ dictType *type; void *privdata; dictht *ht[2]; int rehashIndx; }
ht[2]: 需要兩個hashTable的原因是在進行rehash的操作時,需要使用另一個hashTable。
rehashIndx:在不進行rehash時值為-1,在漸進rehash過程中,這個值代表了rehash進行到的dictEntry的索引。
在hash時將會根據(jù)key取哈希&sizeMark來獲得dictEnrty數(shù)組的下標(biāo)索引,當(dāng)數(shù)組中非空則將dictEntry元素插入到鏈表第一個位置。
隨著鏈表的長度越來越長,對于字典的查詢速度也會越慢,這時候就需要rehash。
rehash將會用到另一個空哈希表ht[1],將里面的table數(shù)組大小增加,再將原來的鍵值重新hash放入新的DictEntry中。rehash完畢后,把ht[1]變?yōu)閔t[0], 再重新開辟一個空間作為ht[1]。
四、跳躍表
跳躍表用作有序集合鍵的底層實現(xiàn)以及在集群節(jié)點用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)
后退指針:后退指針用于從表尾遍歷節(jié)點。
object:保存的是一個指向?qū)ο蟮闹羔槨?/p>
score分值:關(guān)乎節(jié)點的排序,如果分值相同則成員對象較大的排在后面。
zskiplist:雖然通過多個節(jié)點就可以組成跳躍表,但是使用zskiplist中的length、level字段就可以在O(1)復(fù)雜度返回跳躍表的長度以及層級。
五、整數(shù)集合
encoding:可支持存儲INSET_ENC_INT16、INSET_ENC_INT32、INSET_ENC_INT64(int16_t、int32_t、int64_t)三種位數(shù)的整數(shù)。
content: 在這個數(shù)組中按照大小順序存放整數(shù),并且元素不會出現(xiàn)重復(fù)項。
集合升級:當(dāng)集合需要插入一個比原有類型更大的整數(shù)時,需要先給數(shù)組的每個元素重新分配空間,首先先擴大數(shù)組空間到相應(yīng)的大小,再將原來位置上的整數(shù)從后往前重新進行類型轉(zhuǎn)換放到相應(yīng)的索引上。每次升級都需要對底層元素進行轉(zhuǎn)型并移動,時間復(fù)雜度為O(N)。升級使得這個集合更為節(jié)省內(nèi)存,并且可以使得使用者不必關(guān)注c語言底層創(chuàng)建數(shù)組時指定類型位數(shù)不足而導(dǎo)致的插入異常問題。
整數(shù)集合不支持降級。
六、壓縮列表
壓縮列表是列表建和哈希鍵底層實現(xiàn)之一。一個列表鍵只包含少量列表項,并且每個列表項要么就是整數(shù)值,要么就是長度比較短的字符串,Redis就會使用壓縮列表來做列表鍵的底層實現(xiàn)。
zlbytes:記錄整個壓縮列表占用的內(nèi)存字節(jié)數(shù),對壓縮列表進行內(nèi)存重分配、計算zlend位置時使用。
zltail:記錄壓縮列表表尾節(jié)點距離壓縮列表起始地址有多少字節(jié);通過這個偏移量,程序無序遍歷整個壓縮列表就可以確定表尾節(jié)點地址。
zzllen:壓縮列表節(jié)點數(shù)量;當(dāng)這個值等于UINT16_MAX時,節(jié)點的真實數(shù)量需要遍歷整個壓縮列表才能計算得出。
entryX:列表節(jié)點,壓縮列表包含的各個節(jié)點,節(jié)點長度由節(jié)點保存的內(nèi)容決定
?zlend:特殊值0xFF記錄標(biāo)記壓縮列表的末端。
壓縮列表節(jié)點
previous_entry_length:記錄前一個壓縮列表節(jié)點的長度,可通過這個屬性減去指針起始地址往前回溯節(jié)點,該屬性的長度為1字節(jié)或5字節(jié),當(dāng)前一節(jié)長度小于254字節(jié),則前一節(jié)長度使用這個字段直接保存,如果前一節(jié)長度>=254字節(jié),則前一字節(jié)設(shè)置為0xFE,之后四個字節(jié)用十進制保存長度。
encoding:記錄了節(jié)點content屬性保存的數(shù)據(jù)類型及長度。
content:保存節(jié)點值,可以是字節(jié)數(shù)組或者整數(shù)("hello world"、10086)
連鎖更新機制:由于在進行節(jié)點插入時,一旦節(jié)點長度>=254字節(jié),則修改后續(xù)節(jié)點的previos_entry_length屬性,從1字節(jié)擴至5字節(jié),可能再次引起后續(xù)節(jié)點的連鎖修改。
就需要對壓縮列表的執(zhí)行空間重新分配,對每個節(jié)點進行重新分配需要的復(fù)雜度為O(N),則最壞需要進行N次分配,則連鎖更新最壞復(fù)雜度為O(N2)。
到此這篇關(guān)于淺談一下Redis的數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Redis的數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Redis migrate數(shù)據(jù)遷移工具的使用教程
這篇文章主要給大家介紹了關(guān)于Redis migrate數(shù)據(jù)遷移工具的使用教程,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者使用Redis具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08