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

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

redis中的數(shù)據(jù)結(jié)構(gòu)

Redis支持五種數(shù)據(jù)類型：string（字符串）、hash（散列）、list

（列表）、set（無序集）和zset（有序集）o

String

HashTables

LinkedLists

Sets

SortedSets

在spike項(xiàng)目中,我使用了redis的Set和Hash結(jié)構(gòu):

String:一個(gè)key對(duì)應(yīng)一個(gè)string,是Redis最基本的數(shù)據(jù)類型。

（bytes的abase框架只實(shí)現(xiàn)了redis的字符串?dāng)?shù)據(jù)結(jié)構(gòu)，所以如果

我們要存儲(chǔ)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，只能將其轉(zhuǎn)成json格式的字符串進(jìn)行

存儲(chǔ)）

list:一個(gè)鍵對(duì)應(yīng)一個(gè)字符串列表。底層使用雙向鏈表實(shí)現(xiàn)。它支

持雙向鏈表支持的許多操作。

?Hash:

?Set:比如一個(gè)Set的實(shí)例：A-{,a','b',P},A是集合的key,a,'b'和'c是集合的member。無序、無重復(fù)元素。

?SortedSet:在set的基礎(chǔ)上加上一f^score,sets面的數(shù)據(jù)是有序的。

redis數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)

string

使用一種叫簡(jiǎn)單動(dòng)態(tài)字符串（SDS）的數(shù)據(jù)類型來實(shí)現(xiàn)。

*保存字符串對(duì)象的結(jié)構(gòu)

v

structsdshdr{

intlen;//buf中已占用空間的長度

intfree;//buf中剩余可用空間的長度

charbuf[];//數(shù)據(jù)空間

SDS相對(duì)于C字符串的優(yōu)勢(shì):

SDS保存字符串的長度，而C字符串不保存長度，需要遍歷整個(gè)數(shù)

組（直到找到''0'）才能得到字符串的長度。

修改SDS時(shí)，檢查給定的SDS空間是否足夠。如果沒有，則首

先擴(kuò)展SDS空間以防止緩沖區(qū)溢出。C字符串不檢查字符串空間

是否足夠，調(diào)用某些函數(shù)（如strcat字符串拼接函數(shù)）時(shí)容易造成緩

沖區(qū)溢出。

SDS預(yù)分配空間的機(jī)制可以減少為字符串重新分配空間的次數(shù)。

list

使用雙向鏈表來實(shí)現(xiàn)。

hash

hash結(jié)構(gòu)里其實(shí)是一個(gè)字典，有許多的鍵值對(duì)（類似于python的

diet類型）。

redis的哈希表是一個(gè)dictht結(jié)構(gòu)體：

typedefstructdictht{

dictEntry**table

unsignedlongsize;〃的希表大

unsignedlongsizemask;//居希表大〃播行，用于計(jì)算索引值

unsignedlongused;〃該哈希表已有節(jié)點(diǎn)的數(shù)量

dietdictht

哈希表節(jié)點(diǎn)的結(jié)構(gòu)體如下:

typeofstructdictEntry

void"key;//鍵

union{//不同鍵對(duì)應(yīng)的值的類型可能不同,使用unton來處理這個(gè)問題

void*val;

uint64__tu64;

int64_ts64;

}

structdictEntry*next;

解決哈希沖突的方法之一是zipper方法。

為了將哈希表的負(fù)載因子保持在合理的范圍內(nèi)，需要對(duì)哈希表的大小

進(jìn)行擴(kuò)展或收縮，這稱為rehasho字典中一共有兩個(gè)哈希表diettht

結(jié)構(gòu)，ht[O]用于存儲(chǔ)鍵值對(duì),ht[l]用于rehash時(shí)臨時(shí)存儲(chǔ)數(shù)據(jù)。

通常，它指向的哈希表是空的，需要擴(kuò)展或收縮。Ht[0]的哈希表

為其分配了空間。

比如擴(kuò)展哈希表就是為ht[l]分配一個(gè)ht⑼的兩倍大的空間，然后通

過rehash將ht[O]的所有數(shù)據(jù)遷移到ht[l],最后釋放ht[O]]，使

ht[l]變?yōu)閔t[O],并為ht[l]分配一個(gè)空的哈希表。類似于縮小哈

希表。

漸進(jìn)式rehash:redis并沒有專門找時(shí)間一次執(zhí)行rehash,而是

逐步進(jìn)行。在rehash期間，它不會(huì)影響對(duì)ht[O]的外部訪問。修

改字典時(shí)需要將對(duì)應(yīng)的數(shù)據(jù)同步到ht[l]o，當(dāng)所有數(shù)據(jù)傳輸完成后,

rehash結(jié)束。

set

set可以用intset或者字典實(shí)現(xiàn)。

intset

只有當(dāng)數(shù)據(jù)全是整數(shù)值，而且數(shù)量少于512個(gè)時(shí)，才使用intset,

intset是一個(gè)由整數(shù)組成的有序集合，可以進(jìn)行二分查找。

typ?

encoding

"2

ptr

zset

zset中的每個(gè)元素都包含數(shù)據(jù)本身和相應(yīng)的分?jǐn)?shù)。

經(jīng)典例子：一個(gè)zset的key是"math",代表數(shù)學(xué)課的成績，然后

這個(gè)key里面可以插入很多數(shù)據(jù)。輸入數(shù)據(jù)時(shí)，每次都需要輸入姓名

和對(duì)應(yīng)的等級(jí)。那么名稱就是數(shù)據(jù)本身，分?jǐn)?shù)就是它的分?jǐn)?shù)。

zset本身的數(shù)據(jù)是不允許重復(fù)的，但是score是允許重復(fù)的。

zset的底層實(shí)現(xiàn)原理：

數(shù)據(jù)少的時(shí)候使用Ziplist:ziplist占用連續(xù)內(nèi)存，每個(gè)元素以

(data+score)的形式連續(xù)存儲(chǔ)，按照score從小到大排序。為了節(jié)省

ziplist中的內(nèi)存，每個(gè)元素占用的空間可以不同。對(duì)于大數(shù)據(jù)(long

long),使用更多的字節(jié)來存儲(chǔ)，對(duì)于小數(shù)據(jù)(short),使用更少

的字節(jié)來存儲(chǔ)。因此，在搜索時(shí)，需要按W頁序遍歷。ziplist節(jié)省內(nèi)

存，但搜索效率低。

當(dāng)數(shù)據(jù)很多時(shí)，使用字典+跳過表：

使用字典根據(jù)數(shù)據(jù)查找分?jǐn)?shù)，使用跳表根據(jù)分?jǐn)?shù)查找數(shù)據(jù)(查找效率

高)。

理論上，搜索、插入、刪除和迭代輸出有序序列的操作也可以由紅黑

樹完成，時(shí)間復(fù)雜度與跳表相同。

redis使用跳過表而不是紅黑樹的原因：

按區(qū)間查找數(shù)據(jù)的操作，紅黑樹的效率不如跳表的高。跳過鏈表可

以以O(shè)(logn)時(shí)間復(fù)雜度定位區(qū)間的起始點(diǎn)，然后在原鏈表中按順序

向后查詢。

與紅黑樹相比，跳表還具有代碼實(shí)現(xiàn)更容易、可讀性更好、不易出錯(cuò)、

更靈活的優(yōu)點(diǎn)。

插入和刪除時(shí)，跳過表只需要調(diào)整幾個(gè)節(jié)點(diǎn)，而紅黑樹需要顏色重繪

和旋轉(zhuǎn)，成本高。

跳表插入刪除過程

跳過列表是基于一個(gè)有序的單鏈表構(gòu)造的。通過建立索引，提高了

搜索效率，空間換來了時(shí)間。查找方法是從最上面的鏈表開始逐層

往下杳找，最后在最下面的鏈表中找到對(duì)應(yīng)的節(jié)點(diǎn)：

插入：逐層查找位置，然后插入到最底層的鏈表中。請(qǐng)注意，需要保

持索引和原始鏈表之間的大小平衡。如果底層節(jié)點(diǎn)大量增加，索引也

會(huì)相應(yīng)增加，避免兩個(gè)索引之間節(jié)點(diǎn)過多的情況，降低搜索效率。同

樣，當(dāng)?shù)讓庸?jié)點(diǎn)大大減少時(shí)，索引也相應(yīng)減少。

刪除如果該節(jié)點(diǎn)也出現(xiàn)在索引中，那么除了刪除原鏈表中的節(jié)點(diǎn)外,

索引中的節(jié)點(diǎn)也應(yīng)該被刪除。

跳表查找的時(shí)間復(fù)雜度為O(log(n))。索引占用的空間復(fù)雜度為0(n)。

時(shí)間復(fù)雜度：時(shí)間復(fù)雜度;索引的層數(shù)*索引每層遍歷的元素個(gè)數(shù)。

先看索引層數(shù)，假設(shè)每繪制兩個(gè)節(jié)點(diǎn)作為上一級(jí)索引的節(jié)點(diǎn)，最高一

級(jí)索引有個(gè)節(jié)點(diǎn)，那么索引層數(shù)為

3Iog2(n)o

然后看每一層遍歷了多少元素。首先最高層最多可以遍歷3個(gè)節(jié)點(diǎn),

然后可以往下走。同樣，第二層也最多可以遍歷三個(gè)節(jié)點(diǎn)，然后就可

以往下走。取平均值后，可以認(rèn)為每層遍歷2個(gè)節(jié)點(diǎn)。

因此，時(shí)間復(fù)雜度類似地,如果對(duì)每個(gè)節(jié)