Redis中數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)分析

redis中數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)分析，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

創(chuàng)新互聯(lián)建站主要從事網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)特克斯,10余年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):18982081108

1、概述

Redis是一個(gè)開(kāi)源的使用ANSI C語(yǔ)言編寫的key-value 數(shù)據(jù)庫(kù)，我們可能會(huì)較為主觀的認(rèn)為 Redis 中的字符串就是采用了C語(yǔ)言中的傳統(tǒng)字符串表示，但其實(shí)不然，Redis沒(méi)有直接使用C語(yǔ)言傳統(tǒng)的字符串表示，而是自己構(gòu)建了一種名為簡(jiǎn)單動(dòng)態(tài)字符串（simple dynamic string SDS）的抽象類型，并將SDS用作Redis的默認(rèn)字符串表示：redis>SET msg "hello world"

SDS 定義：

struct sdshdr{       //記錄buf數(shù)組中已使用字節(jié)的數(shù)量       //等于 SDS 保存字符串的長(zhǎng)度       int len;       //記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量       int free;       //字節(jié)數(shù)組，用于保存字符串       char buf[];  }

圖片來(lái)源：《Redis設(shè)計(jì)與實(shí)現(xiàn)》

我們看上面對(duì)于 SDS 數(shù)據(jù)類型的定義：

•  len 保存了SDS保存字符串的長(zhǎng)度

•  buf[] 數(shù)組用來(lái)保存字符串的每個(gè)元素

•  free j記錄了 buf 數(shù)組中未使用的字節(jié)數(shù)量

2、與C語(yǔ)言相比較　

一般來(lái)說(shuō)，SDS 除了保存數(shù)據(jù)庫(kù)中的字符串值以外，SDS 還可以作為緩沖區(qū)（buffer）：包括 AOF 模塊中的AOF緩沖區(qū)以及客戶端狀態(tài)中的輸入緩沖區(qū)。后面在介紹Redis的持久化時(shí)會(huì)進(jìn)行介紹。

三、鏈表

1、概述

鏈表提供了高效的節(jié)點(diǎn)重排能力，以及順序性的節(jié)點(diǎn)訪問(wèn)方式，并且可以通過(guò)增刪節(jié)點(diǎn)來(lái)靈活地調(diào)整鏈表的長(zhǎng)度。

鏈表在Redis 中的應(yīng)用非常廣泛，比如列表鍵的底層實(shí)現(xiàn)之一就是鏈表。當(dāng)一個(gè)列表鍵包含了數(shù)量較多的元素，又或者列表中包含的元素都是比較長(zhǎng)的字符串時(shí)，Redis 就會(huì)使用鏈表作為列表鍵的底層實(shí)現(xiàn)。

每個(gè)鏈表節(jié)點(diǎn)使用一個(gè)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)值對(duì)比函數(shù)       int (*match) (void *ptr,void *key);  }list;

組成結(jié)構(gòu)圖

2、Redis鏈表特性

•  雙端：鏈表具有前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的引用，獲取這兩個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度都為O(1)。

•  無(wú)環(huán)：表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的 next 指針都指向 NULL,對(duì)鏈表的訪問(wèn)都是以 NULL 結(jié)束。　

•  帶鏈表長(zhǎng)度計(jì)數(shù)器：通過(guò) len 屬性獲取鏈表長(zhǎng)度的時(shí)間復(fù)雜度為 O(1)。

•  多態(tài)：鏈表節(jié)點(diǎn)使用 void* 指針來(lái)保存節(jié)點(diǎn)值，可以保存各種不同類型的值。

四、字典

1、概述

字典又稱為符號(hào)表或者關(guān)聯(lián)數(shù)組、或映射（map），是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)。字典中的每一個(gè)鍵 key 都是唯一的，通過(guò) key 可以對(duì)值來(lái)進(jìn)行查找或修改。C 語(yǔ)言中沒(méi)有內(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;       //哈希表大小掩碼，用于計(jì)算索引值       //總是等于 size-1       unsigned long sizemask;       //該哈希表已有節(jié)點(diǎn)的數(shù)量       unsigned long used;  }dictht

哈希表是由數(shù)組 table 組成，table 中每個(gè)元素都是指向 dict.h/dictEntry 結(jié)構(gòu)，dictEntry 結(jié)構(gòu)定義如下：

typedef struct dictEntry{       //鍵       void *key;       //值       union{            void *val;            uint64_tu64;            int64_ts64;       }v;       //指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表       struct dictEntry *next; }dictEntry

key 用來(lái)保存鍵，val 屬性用來(lái)保存值，值可以是一個(gè)指針，也可以是uint64_t整數(shù)，也可以是int64_t整數(shù)。

注意這里還有一個(gè)指向下一個(gè)哈希表節(jié)點(diǎn)的指針，我們知道哈希表最大的問(wèn)題是存在哈希沖突，如何解決哈希沖突，有開(kāi)放地址法和鏈地址法。這里采用的便是鏈地址法，通過(guò)next這個(gè)指針可以將多個(gè)哈希值相同的鍵值對(duì)連接在一起，用來(lái)解決哈希沖突。

五、跳躍表

1、概述

跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過(guò)在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的。跳躍表是一種隨機(jī)化的數(shù)據(jù),跳躍表以有序的方式在層次化的鏈表中保存元素，效率和平衡樹(shù)媲美 ——查找、刪除、添加等操作都可以在對(duì)數(shù)期望時(shí)間下完成，并且比起平衡樹(shù)來(lái)說(shuō)，跳躍表的實(shí)現(xiàn)要簡(jiǎn)單直觀得多。

Redis 只在兩個(gè)地方用到了跳躍表，一個(gè)是實(shí)現(xiàn)有序集合鍵，另外一個(gè)是在集群節(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;       //成員對(duì)象       robj *obj;  } zskiplistNode

多個(gè)跳躍表節(jié)點(diǎn)構(gòu)成一個(gè)跳躍表：

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指針?lè)謩e指向跳躍表的表頭和表尾節(jié)點(diǎn)；

•  length屬性記錄節(jié)點(diǎn)的數(shù)量；

•  level屬性記錄層數(shù)最高的幾點(diǎn)的層數(shù)量；

•  下圖分別展示了完整的跳躍表和單個(gè)節(jié)點(diǎn)的詳細(xì)結(jié)構(gòu)圖：

2、特性

跳表具有如下性質(zhì)：

•  由很多層結(jié)構(gòu)組成

•  每一層都是一個(gè)有序的鏈表

•  最底層(Level 1)的鏈表包含所有元素

•  如果一個(gè)元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會(huì)出現(xiàn)。

•  每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。

六、整數(shù)集合

1、概述

《Redis 設(shè)計(jì)與實(shí)現(xiàn)》 中這樣定義整數(shù)集合：“整數(shù)集合是集合建的底層實(shí)現(xiàn)之一，當(dāng)一個(gè)集合中只包含整數(shù)，且這個(gè)集合中的元素?cái)?shù)量不多時(shí)，redis就會(huì)使用整數(shù)集合intset作為集合的底層實(shí)現(xiàn)。”

我們可以這樣理解整數(shù)集合，他其實(shí)就是一個(gè)特殊的集合，里面存儲(chǔ)的數(shù)據(jù)只能夠是整數(shù)，并且數(shù)據(jù)量不能過(guò)大。

typedef struct intset{       //編碼方式       uint32_t encoding;       //集合包含的元素?cái)?shù)量       uint32_t length;       //保存元素的數(shù)組       int8_t contents[];  }intset;

我們觀察一下一個(gè)完成的整數(shù)集合結(jié)構(gòu)圖： 

• encoding：用于定義整數(shù)集合的編碼方式

• length：用于記錄整數(shù)集合中變量的數(shù)量

• contents：用于保存元素的數(shù)組，雖然我們?cè)跀?shù)據(jù)結(jié)構(gòu)圖中看到，intset將數(shù)組定義為int8_t，但實(shí)際上數(shù)組保存的元素類型取決于encoding

2、特性

•  整數(shù)集合是集合建的底層實(shí)現(xiàn)之一

•  整數(shù)集合的底層實(shí)現(xiàn)為數(shù)組，這個(gè)數(shù)組以有序，無(wú)重復(fù)的范式保存集合元素，在有需要時(shí)，程序會(huì)根據(jù)新添加的元素類型改變這個(gè)數(shù)組的類型

•  升級(jí)操作為整數(shù)集合帶來(lái)了操作上的靈活性，并且盡可能地節(jié)約了內(nèi)存2

  整數(shù)集合只支持升級(jí)操作，不支持降級(jí)操作

七、壓縮列表

1、概述

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

一個(gè)壓縮列表的組成如下：

•  zlbytes:用于記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)

•  zltail：記錄要列表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)

•  zllen：記錄了壓縮列表包含的節(jié)點(diǎn)數(shù)量

•  entryX：要說(shuō)列表包含的各個(gè)節(jié)點(diǎn)

•  zlend：用于標(biāo)記壓縮列表的末端

2、特性

•  壓縮列表是一種為了節(jié)約內(nèi)存而開(kāi)發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)

•  壓縮列表被用作列表鍵和哈希鍵的底層實(shí)現(xiàn)之一

•  壓縮列表可以包含多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者整數(shù)值

•  添加新節(jié)點(diǎn)到壓縮列表，可能會(huì)引發(fā)連鎖更新操作。 

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。

分享標(biāo)題：Redis中數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)分析
標(biāo)題鏈接：http://muchs.cn/article28/iepjjp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、自適應(yīng)網(wǎng)站、微信公眾號(hào)、云服務(wù)器、App設(shè)計(jì)、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)