您好,登錄后才能下訂單哦!
Redis中數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)分析,很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細(xì)講解,有這方面需求的人可以來學(xué)習(xí)下,希望你能有所收獲。
1、概述
Redis是一個開源的使用ANSI C語言編寫的key-value 數(shù)據(jù)庫,我們可能會較為主觀的認(rèn)為 Redis 中的字符串就是采用了C語言中的傳統(tǒng)字符串表示,但其實(shí)不然,Redis沒有直接使用C語言傳統(tǒng)的字符串表示,而是自己構(gòu)建了一種名為簡單動態(tài)字符串(simple dynamic string SDS)的抽象類型,并將SDS用作Redis的默認(rèn)字符串表示:redis>SET msg "hello world"
SDS 定義:
struct sdshdr{ //記錄buf數(shù)組中已使用字節(jié)的數(shù)量 //等于 SDS 保存字符串的長度 int len; //記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量 int free; //字節(jié)數(shù)組,用于保存字符串 char buf[]; }
圖片來源:《Redis設(shè)計與實(shí)現(xiàn)》
我們看上面對于 SDS 數(shù)據(jù)類型的定義:
len 保存了SDS保存字符串的長度
buf[] 數(shù)組用來保存字符串的每個元素
free j記錄了 buf 數(shù)組中未使用的字節(jié)數(shù)量
2、與C語言相比較
一般來說,SDS 除了保存數(shù)據(jù)庫中的字符串值以外,SDS 還可以作為緩沖區(qū)(buffer):包括 AOF 模塊中的AOF緩沖區(qū)以及客戶端狀態(tài)中的輸入緩沖區(qū)。后面在介紹Redis的持久化時會進(jìn)行介紹。
三、鏈表
1、概述
鏈表提供了高效的節(jié)點(diǎn)重排能力,以及順序性的節(jié)點(diǎn)訪問方式,并且可以通過增刪節(jié)點(diǎn)來靈活地調(diào)整鏈表的長度。
鏈表在Redis 中的應(yīng)用非常廣泛,比如列表鍵的底層實(shí)現(xiàn)之一就是鏈表。當(dāng)一個列表鍵包含了數(shù)量較多的元素,又或者列表中包含的元素都是比較長的字符串時,Redis 就會使用鏈表作為列表鍵的底層實(shí)現(xiàn)。
每個鏈表節(jié)點(diǎn)使用一個listNode結(jié)構(gòu)表示(adlist.h/listNode):
typedef struct listNode{ //前置節(jié)點(diǎn) struct listNode *prev; //后置節(jié)點(diǎn) struct listNode *next; //節(jié)點(diǎn)的值 void *value; }listNode
鏈表的數(shù)據(jù)結(jié)構(gòu):
typedef struct list{ //表頭節(jié)點(diǎn) listNode *head; //表尾節(jié)點(diǎn) listNode *tail; //鏈表所包含的節(jié)點(diǎn)數(shù)量 unsigned long len; //節(jié)點(diǎn)值復(fù)制函數(shù) void (*free) (void *ptr); //節(jié)點(diǎn)值釋放函數(shù) void (*free) (void *ptr); //節(jié)點(diǎn)值對比函數(shù) int (*match) (void *ptr,void *key); }list;
組成結(jié)構(gòu)圖
2、Redis鏈表特性
雙端:鏈表具有前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的引用,獲取這兩個節(jié)點(diǎn)時間復(fù)雜度都為O(1)。
無環(huán):表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的 next 指針都指向 NULL,對鏈表的訪問都是以 NULL 結(jié)束?!?/p>
帶鏈表長度計數(shù)器:通過 len 屬性獲取鏈表長度的時間復(fù)雜度為 O(1)。
多態(tài):鏈表節(jié)點(diǎn)使用 void* 指針來保存節(jié)點(diǎn)值,可以保存各種不同類型的值。
四、字典
1、概述
字典又稱為符號表或者關(guān)聯(lián)數(shù)組、或映射(map),是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)。字典中的每一個鍵 key 都是唯一的,通過 key 可以對值來進(jìn)行查找或修改。C 語言中沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn),所以字典依然是 Redis自己構(gòu)建的。
哈希表結(jié)構(gòu)定義:
typedef struct dictht{ //哈希表數(shù)組 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩碼,用于計算索引值 //總是等于 size-1 unsigned long sizemask; //該哈希表已有節(jié)點(diǎn)的數(shù)量 unsigned long used; }dictht
哈希表是由數(shù)組 table 組成,table 中每個元素都是指向 dict.h/dictEntry 結(jié)構(gòu),dictEntry 結(jié)構(gòu)定義如下:
typedef struct dictEntry{ //鍵 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; }v; //指向下一個哈希表節(jié)點(diǎn),形成鏈表 struct dictEntry *next; }dictEntry
key 用來保存鍵,val 屬性用來保存值,值可以是一個指針,也可以是uint64_t整數(shù),也可以是int64_t整數(shù)。
注意這里還有一個指向下一個哈希表節(jié)點(diǎn)的指針,我們知道哈希表最大的問題是存在哈希沖突,如何解決哈希沖突,有開放地址法和鏈地址法。這里采用的便是鏈地址法,通過next這個指針可以將多個哈希值相同的鍵值對連接在一起,用來解決哈希沖突。
五、跳躍表
1、概述
跳躍表(skiplist)是一種有序數(shù)據(jù)結(jié)構(gòu),它通過在每個節(jié)點(diǎn)中維持多個指向其他節(jié)點(diǎn)的指針,從而達(dá)到快速訪問節(jié)點(diǎn)的目的。跳躍表是一種隨機(jī)化的數(shù)據(jù),跳躍表以有序的方式在層次化的鏈表中保存元素,效率和平衡樹媲美 ——查找、刪除、添加等操作都可以在對數(shù)期望時間下完成,并且比起平衡樹來說,跳躍表的實(shí)現(xiàn)要簡單直觀得多。
Redis 只在兩個地方用到了跳躍表,一個是實(shí)現(xiàn)有序集合鍵,另外一個是在集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)。
Redis中跳躍表節(jié)點(diǎn)定義如下:
typedef struct zskiplistNode { //層 struct zskiplistLevel{ //前進(jìn)指針 struct zskiplistNode *forward; //跨度 unsigned int span; }level[]; //后退指針 struct zskiplistNode *backward; //分值 double score; //成員對象 robj *obj; } zskiplistNode
多個跳躍表節(jié)點(diǎn)構(gòu)成一個跳躍表:
typedef struct zskiplist{ //表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn) structz skiplistNode *header, *tail; //表中節(jié)點(diǎn)的數(shù)量 unsigned long length; //表中層數(shù)最大的節(jié)點(diǎn)的層數(shù) int level; }zskiplist;
header和tail指針分別指向跳躍表的表頭和表尾節(jié)點(diǎn);
length屬性記錄節(jié)點(diǎn)的數(shù)量;
level屬性記錄層數(shù)最高的幾點(diǎn)的層數(shù)量;
下圖分別展示了完整的跳躍表和單個節(jié)點(diǎn)的詳細(xì)結(jié)構(gòu)圖:
2、特性
跳表具有如下性質(zhì):
由很多層結(jié)構(gòu)組成
每一層都是一個有序的鏈表
最底層(Level 1)的鏈表包含所有元素
如果一個元素出現(xiàn)在 Level i 的鏈表中,則它在 Level i 之下的鏈表也都會出現(xiàn)。
每個節(jié)點(diǎn)包含兩個指針,一個指向同一鏈表中的下一個元素,一個指向下面一層的元素。
六、整數(shù)集合
1、概述
《Redis 設(shè)計與實(shí)現(xiàn)》 中這樣定義整數(shù)集合:“整數(shù)集合是集合建的底層實(shí)現(xiàn)之一,當(dāng)一個集合中只包含整數(shù),且這個集合中的元素數(shù)量不多時,redis就會使用整數(shù)集合intset作為集合的底層實(shí)現(xiàn)?!?/p>
我們可以這樣理解整數(shù)集合,他其實(shí)就是一個特殊的集合,里面存儲的數(shù)據(jù)只能夠是整數(shù),并且數(shù)據(jù)量不能過大。
typedef struct intset{ //編碼方式 uint32_t encoding; //集合包含的元素數(shù)量 uint32_t length; //保存元素的數(shù)組 int8_t contents[]; }intset;
我們觀察一下一個完成的整數(shù)集合結(jié)構(gòu)圖:
encoding:用于定義整數(shù)集合的編碼方式
length:用于記錄整數(shù)集合中變量的數(shù)量
contents:用于保存元素的數(shù)組,雖然我們在數(shù)據(jù)結(jié)構(gòu)圖中看到,intset將數(shù)組定義為int8_t,但實(shí)際上數(shù)組保存的元素類型取決于encoding
2、特性
整數(shù)集合是集合建的底層實(shí)現(xiàn)之一
整數(shù)集合的底層實(shí)現(xiàn)為數(shù)組,這個數(shù)組以有序,無重復(fù)的范式保存集合元素,在有需要時,程序會根據(jù)新添加的元素類型改變這個數(shù)組的類型
升級操作為整數(shù)集合帶來了操作上的靈活性,并且盡可能地節(jié)約了內(nèi)存2
整數(shù)集合只支持升級操作,不支持降級操作
七、壓縮列表
1、概述
壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個列表鍵只包含少量列表項(xiàng),并且每個列表項(xiàng)要么就是小整數(shù),要么就是長度比較短的字符串,那么Redis 就會使用壓縮列表來做列表鍵的底層實(shí)現(xiàn)。
一個壓縮列表的組成如下:
zlbytes:用于記錄整個壓縮列表占用的內(nèi)存字節(jié)數(shù)
zltail:記錄要列表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)
zllen:記錄了壓縮列表包含的節(jié)點(diǎn)數(shù)量
entryX:要說列表包含的各個節(jié)點(diǎn)
zlend:用于標(biāo)記壓縮列表的末端
2、特性
壓縮列表是一種為了節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)
壓縮列表被用作列表鍵和哈希鍵的底層實(shí)現(xiàn)之一
壓縮列表可以包含多個節(jié)點(diǎn),每個節(jié)點(diǎn)可以保存一個字節(jié)數(shù)組或者整數(shù)值
添加新節(jié)點(diǎn)到壓縮列表,可能會引發(fā)連鎖更新操作。
看完上述內(nèi)容是否對您有幫助呢?如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章,請關(guān)注億速云行業(yè)資訊頻道,感謝您對億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。