欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

淺談一下Redis的數(shù)據(jù)結(jié)構(gòu)

 更新時(shí)間:2023年08月12日 11:12:30   作者:bibiwannbe  
這篇文章主要介紹了淺談一下Redis的數(shù)據(jù)結(jié)構(gòu),簡單字符串結(jié)構(gòu)被用于存儲(chǔ)redis的key對(duì)象和String類型的value對(duì)象,其中的free和len字段可以輕松的使得在該字符串被修改時(shí)判斷是否需要擴(kuò)容,需要的朋友可以參考下

一、簡單動(dòng)態(tài)字符串SDS

struct sdshdr {
  int len;
  int free;
  char[] buf;
}

簡單字符串結(jié)構(gòu)被用于存儲(chǔ)redis的key對(duì)象和String類型的value對(duì)象

其中的free和len字段可以輕松的使得在該字符串被修改時(shí)判斷是否需要擴(kuò)容。

為啥呢?因?yàn)閞edis的協(xié)議發(fā)送一個(gè)SET請(qǐng)求時(shí)格式開頭會(huì)帶上需要插入的value的長度,這樣根據(jù)free以及l(fā)en可以判斷此時(shí)redis分配的數(shù)組大小是多少,需不需要擴(kuò)容。對(duì)比于C語言的O(n)復(fù)雜度計(jì)算數(shù)組長度更快。

擴(kuò)容策略:如果字符串大小<1MB, 每次擴(kuò)容為2n+1大小;如果大于1MB,每次擴(kuò)容1MB。

二、鏈表

鏈表結(jié)構(gòu)用于存儲(chǔ)list類型的鍵值(類似index),還有發(fā)布訂閱等功能也用了鏈表結(jié)構(gòu)。

鏈表節(jié)點(diǎn):ListNode

鏈表:list

代碼塊  

typedef struct list{
	ListNode * tail;
	ListNode * head;
	unsigned long len;
	//節(jié)點(diǎn)值復(fù)制方法
	 void *(*dup) (void * ptr);
	//節(jié)點(diǎn)值釋放方法
	 void *(*free) (void * ptr);
	//節(jié)點(diǎn)值對(duì)比方法
	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]: 需要兩個(gè)hashTable的原因是在進(jìn)行rehash的操作時(shí),需要使用另一個(gè)hashTable。

rehashIndx:在不進(jìn)行rehash時(shí)值為-1,在漸進(jìn)rehash過程中,這個(gè)值代表了rehash進(jìn)行到的dictEntry的索引。

在hash時(shí)將會(huì)根據(jù)key取哈希&sizeMark來獲得dictEnrty數(shù)組的下標(biāo)索引,當(dāng)數(shù)組中非空則將dictEntry元素插入到鏈表第一個(gè)位置。

隨著鏈表的長度越來越長,對(duì)于字典的查詢速度也會(huì)越慢,這時(shí)候就需要rehash。

rehash將會(huì)用到另一個(gè)空哈希表ht[1],將里面的table數(shù)組大小增加,再將原來的鍵值重新hash放入新的DictEntry中。rehash完畢后,把ht[1]變?yōu)閔t[0], 再重新開辟一個(gè)空間作為ht[1]。

四、跳躍表

跳躍表用作有序集合鍵的底層實(shí)現(xiàn)以及在集群節(jié)點(diǎn)用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)

后退指針:后退指針用于從表尾遍歷節(jié)點(diǎn)。

object:保存的是一個(gè)指向?qū)ο蟮闹羔槨?/p>

score分值:關(guān)乎節(jié)點(diǎn)的排序,如果分值相同則成員對(duì)象較大的排在后面。

zskiplist:雖然通過多個(gè)節(jié)點(diǎn)就可以組成跳躍表,但是使用zskiplist中的length、level字段就可以在O(1)復(fù)雜度返回跳躍表的長度以及層級(jí)。

五、整數(shù)集合

encoding:可支持存儲(chǔ)INSET_ENC_INT16、INSET_ENC_INT32、INSET_ENC_INT64(int16_t、int32_t、int64_t)三種位數(shù)的整數(shù)。

content: 在這個(gè)數(shù)組中按照大小順序存放整數(shù),并且元素不會(huì)出現(xiàn)重復(fù)項(xiàng)。

集合升級(jí):當(dāng)集合需要插入一個(gè)比原有類型更大的整數(shù)時(shí),需要先給數(shù)組的每個(gè)元素重新分配空間,首先先擴(kuò)大數(shù)組空間到相應(yīng)的大小,再將原來位置上的整數(shù)從后往前重新進(jìn)行類型轉(zhuǎn)換放到相應(yīng)的索引上。每次升級(jí)都需要對(duì)底層元素進(jìn)行轉(zhuǎn)型并移動(dòng),時(shí)間復(fù)雜度為O(N)。升級(jí)使得這個(gè)集合更為節(jié)省內(nèi)存,并且可以使得使用者不必關(guān)注c語言底層創(chuàng)建數(shù)組時(shí)指定類型位數(shù)不足而導(dǎo)致的插入異常問題。

整數(shù)集合不支持降級(jí)。

六、壓縮列表

壓縮列表是列表建和哈希鍵底層實(shí)現(xiàn)之一。一個(gè)列表鍵只包含少量列表項(xiàng),并且每個(gè)列表項(xiàng)要么就是整數(shù)值,要么就是長度比較短的字符串,Redis就會(huì)使用壓縮列表來做列表鍵的底層實(shí)現(xiàn)。

zlbytes:記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù),對(duì)壓縮列表進(jìn)行內(nèi)存重分配、計(jì)算zlend位置時(shí)使用。

zltail:記錄壓縮列表表尾節(jié)點(diǎn)距離壓縮列表起始地址有多少字節(jié);通過這個(gè)偏移量,程序無序遍歷整個(gè)壓縮列表就可以確定表尾節(jié)點(diǎn)地址。

zzllen:壓縮列表節(jié)點(diǎn)數(shù)量;當(dāng)這個(gè)值等于UINT16_MAX時(shí),節(jié)點(diǎn)的真實(shí)數(shù)量需要遍歷整個(gè)壓縮列表才能計(jì)算得出。

entryX:列表節(jié)點(diǎn),壓縮列表包含的各個(gè)節(jié)點(diǎn),節(jié)點(diǎn)長度由節(jié)點(diǎn)保存的內(nèi)容決定

?zlend:特殊值0xFF記錄標(biāo)記壓縮列表的末端。

壓縮列表節(jié)點(diǎn)

previous_entry_length:記錄前一個(gè)壓縮列表節(jié)點(diǎn)的長度,可通過這個(gè)屬性減去指針起始地址往前回溯節(jié)點(diǎn),該屬性的長度為1字節(jié)或5字節(jié),當(dāng)前一節(jié)長度小于254字節(jié),則前一節(jié)長度使用這個(gè)字段直接保存,如果前一節(jié)長度>=254字節(jié),則前一字節(jié)設(shè)置為0xFE,之后四個(gè)字節(jié)用十進(jìn)制保存長度。

encoding:記錄了節(jié)點(diǎn)content屬性保存的數(shù)據(jù)類型及長度。

content:保存節(jié)點(diǎn)值,可以是字節(jié)數(shù)組或者整數(shù)("hello world"、10086)

連鎖更新機(jī)制:由于在進(jìn)行節(jié)點(diǎn)插入時(shí),一旦節(jié)點(diǎn)長度>=254字節(jié),則修改后續(xù)節(jié)點(diǎn)的previos_entry_length屬性,從1字節(jié)擴(kuò)至5字節(jié),可能再次引起后續(xù)節(jié)點(diǎn)的連鎖修改。

就需要對(duì)壓縮列表的執(zhí)行空間重新分配,對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行重新分配需要的復(fù)雜度為O(N),則最壞需要進(jìn)行N次分配,則連鎖更新最壞復(fù)雜度為O(N2)。

到此這篇關(guān)于淺談一下Redis的數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Redis的數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 淺談Redis的keys命令到底有多慢

    淺談Redis的keys命令到底有多慢

    本文主要介紹了淺談Redis的keys命令到底有多慢,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-10-10
  • Redis分布式鎖實(shí)例分析講解

    Redis分布式鎖實(shí)例分析講解

    分布式鎖是控制分布式系統(tǒng)不同進(jìn)程共同訪問共享資源的一種鎖的實(shí)現(xiàn)。如果不同的系統(tǒng)或同一個(gè)系統(tǒng)的不同主機(jī)之間共享了某個(gè)臨界資源,往往需要互斥來防止彼此干擾,以保證一致性
    2022-12-12
  • Redis migrate數(shù)據(jù)遷移工具的使用教程

    Redis migrate數(shù)據(jù)遷移工具的使用教程

    這篇文章主要給大家介紹了關(guān)于Redis migrate數(shù)據(jù)遷移工具的使用教程,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者使用Redis具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-08-08
  • Django使用redis配置緩存的方法

    Django使用redis配置緩存的方法

    Redis是一個(gè)內(nèi)存數(shù)據(jù)庫由于其性能極高,因此經(jīng)常作為中間件、緩存使用,緩存某些內(nèi)容是為了保存昂貴計(jì)算的結(jié)果,這樣就不必在下次執(zhí)行計(jì)算,接下來通過本文給大家分享redis配置緩存的方法,感興趣的朋友一起看看吧
    2021-06-06
  • 解決redis啟動(dòng)的警告日志問題

    解決redis啟動(dòng)的警告日志問題

    這篇文章主要介紹了解決redis啟動(dòng)的警告日志問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-01-01
  • redis通過位圖法記錄在線用戶的狀態(tài)詳解

    redis通過位圖法記錄在線用戶的狀態(tài)詳解

    這篇文章主要給大家介紹了關(guān)于redis如何通過位圖法記錄在線用戶的狀態(tài)的相關(guān)資料,文中先對(duì)位圖進(jìn)行了一個(gè)簡單的介紹,而后通過示例代碼將實(shí)現(xiàn)的方法介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2018-11-11
  • k8s部署redis集群搭建過程示例詳解

    k8s部署redis集群搭建過程示例詳解

    這篇文章主要為大家介紹了k8s部署redis集群搭建過程示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-02-02
  • Redis數(shù)據(jù)庫安全詳解

    Redis數(shù)據(jù)庫安全詳解

    這篇文章主要為大家介紹了Redis數(shù)據(jù)庫安全詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-11-11
  • 基于Redis的限流器的實(shí)現(xiàn)(示例講解)

    基于Redis的限流器的實(shí)現(xiàn)(示例講解)

    下面小編就為大家分享一篇基于Redis的限流器的實(shí)現(xiàn)(示例講解),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2017-12-12
  • Redis 緩存擊穿問題及解決方案

    Redis 緩存擊穿問題及解決方案

    緩存擊穿是指在高并發(fā)環(huán)境下,大量請(qǐng)求同時(shí)訪問緩存中不存在的數(shù)據(jù),導(dǎo)致這些請(qǐng)求穿透到數(shù)據(jù)庫,本文主要介紹了Redis緩存擊穿問題及解決方案
    2023-12-12

最新評(píng)論