一文讀懂Redis常見(jiàn)對(duì)象類型的底層數(shù)據(jù)結(jié)構(gòu)

Redis是一個(gè)基于內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)系統(tǒng)，可以用作數(shù)據(jù)庫(kù)、緩存和消息中間件。Redis支持五種常見(jiàn)對(duì)象類型：字符串(String)、哈希(Hash）、列表(List)、集合(Set)以及有序集合(Zset)，我們?cè)谌粘９ぷ髦幸矔?huì)經(jīng)常使用它們。知其然，更要知其所以然，本文將會(huì)帶你讀懂這五種常見(jiàn)對(duì)象類型的底層數(shù)據(jù)結(jié)構(gòu)。

本文主要內(nèi)容參考自《Redis設(shè)計(jì)與實(shí)現(xiàn)》

對(duì)象類型和編碼

Redis使用對(duì)象來(lái)存儲(chǔ)鍵和值的，在Redis中，每個(gè)對(duì)象都由redisObject結(jié)構(gòu)表示。redisObject結(jié)構(gòu)主要包含三個(gè)屬性：type、encoding和ptr。

typedef?struct?redisObject?{
????// 類型
????unsigned?type:4;
????// 編碼
????unsigned?encoding:4;
????// 底層數(shù)據(jù)結(jié)構(gòu)的指針
????void?*ptr;
} robj;

其中type屬性記錄了對(duì)象的類型，對(duì)于Redis來(lái)說(shuō)，鍵對(duì)象總是字符串類型，值對(duì)象可以是任意支持的類型。因此，當(dāng)我們說(shuō)Redis鍵采用哪種對(duì)象類型的時(shí)候，指的是對(duì)應(yīng)的值采用哪種對(duì)象類型。

*ptr屬性指向了對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)，而這些數(shù)據(jù)結(jié)構(gòu)由encoding屬性決定。

之所以由encoding屬性來(lái)決定對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)，是為了實(shí)現(xiàn)同一對(duì)象類型，支持不同的底層實(shí)現(xiàn)。這樣就能在不同場(chǎng)景下，使用不同的底層數(shù)據(jù)結(jié)構(gòu)，進(jìn)而極大提升Redis的靈活性和效率。

底層數(shù)據(jù)結(jié)構(gòu)后面會(huì)詳細(xì)講解，這里簡(jiǎn)單看一下即可。

字符串對(duì)象

字符串是我們?nèi)粘９ぷ髦杏玫米疃嗟膶?duì)象類型，它對(duì)應(yīng)的編碼可以是int、raw和embstr。字符串對(duì)象相關(guān)命令可參考：Redis命令-Strings。

如果一個(gè)字符串對(duì)象保存的是不超過(guò)long類型的整數(shù)值，此時(shí)編碼類型即為int，其底層數(shù)據(jù)結(jié)構(gòu)直接就是long類型。例如執(zhí)行set number 10086，就會(huì)創(chuàng)建int編碼的字符串對(duì)象作為number鍵的值。

如果字符串對(duì)象保存的是一個(gè)長(zhǎng)度大于39字節(jié)的字符串，此時(shí)編碼類型即為raw，其底層數(shù)據(jù)結(jié)構(gòu)是簡(jiǎn)單動(dòng)態(tài)字符串(SDS)；如果長(zhǎng)度小于等于39個(gè)字節(jié)，編碼類型則為embstr，底層數(shù)據(jù)結(jié)構(gòu)就是embstr編碼SDS。下面，我們?cè)敿?xì)理解下什么是簡(jiǎn)單動(dòng)態(tài)字符串。

簡(jiǎn)單動(dòng)態(tài)字符串SDS定義

在Redis中，使用sdshdr數(shù)據(jù)結(jié)構(gòu)表示SDS：

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

SDS遵循了C字符串以空字符結(jié)尾的慣例，保存空字符的1字節(jié)不會(huì)計(jì)算在len屬性里面。例如，Redis這個(gè)字符串在SDS里面的數(shù)據(jù)可能是如下形式：

SDS與C字符串的區(qū)別

C語(yǔ)言使用長(zhǎng)度為N+1的字符數(shù)組來(lái)表示長(zhǎng)度為N的字符串，并且字符串的最后一個(gè)元素是空字符\0。Redis采用SDS相對(duì)于C字符串有如下幾個(gè)優(yōu)勢(shì)：

常數(shù)復(fù)雜度獲取字符串長(zhǎng)度

因?yàn)镃字符串并不記錄自身的長(zhǎng)度信息，所以為了獲取字符串的長(zhǎng)度，必須遍歷整個(gè)字符串，時(shí)間復(fù)雜度是O(N)；而SDS使用len屬性記錄了字符串的長(zhǎng)度，因此獲取SDS字符串長(zhǎng)度的時(shí)間復(fù)雜度是O(1)。

杜絕緩沖區(qū)溢出

C字符串不記錄自身長(zhǎng)度帶來(lái)的另一個(gè)問(wèn)題是很容易造成緩存區(qū)溢出。比如使用字符串拼接函數(shù)(stract)的時(shí)候，很容易覆蓋掉字符數(shù)組原有的數(shù)據(jù)。與C字符串不同，SDS的空間分配策略完全杜絕了發(fā)生緩存區(qū)溢出的可能性。當(dāng)SDS進(jìn)行字符串?dāng)U充時(shí)，首先會(huì)檢查當(dāng)前的字節(jié)數(shù)組的長(zhǎng)度是否足夠，如果不夠的話，會(huì)先進(jìn)行自動(dòng)擴(kuò)容，然后再進(jìn)行字符串操作。

減少修改字符串時(shí)帶來(lái)的內(nèi)存重分配次數(shù)

因?yàn)镃字符串的長(zhǎng)度和底層數(shù)據(jù)是緊密關(guān)聯(lián)的，所以每次增長(zhǎng)或者縮短一個(gè)字符串，程序都要對(duì)這個(gè)數(shù)組進(jìn)行一次內(nèi)存重分配：

因?yàn)閮?nèi)存重分配涉及復(fù)雜的算法，并且可能需要執(zhí)行系統(tǒng)調(diào)用，所以通常是個(gè)比較耗時(shí)的操作。對(duì)于Redis來(lái)說(shuō)，字符串修改是一個(gè)十分頻繁的操作，如果每次都像C字符串那樣進(jìn)行內(nèi)存重分配，對(duì)性能影響太大了，顯然是無(wú)法接受的。

SDS通過(guò)空閑空間解除了字符串長(zhǎng)度和底層數(shù)據(jù)之間的關(guān)聯(lián)。在SDS中，數(shù)組中可以包含未使用的字節(jié)，這些字節(jié)數(shù)量由free屬性記錄。通過(guò)空閑空間，SDS實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略。

二進(jìn)制安全

C字符串中的字符必須符合某種編碼，并且除了字符串末尾之外，其它位置不允許出現(xiàn)空字符，這些限制使得C字符串只能保存文本數(shù)據(jù)。但是對(duì)于Redis來(lái)說(shuō)，不僅僅需要保存文本，還要支持保存二進(jìn)制數(shù)據(jù)。為了實(shí)現(xiàn)這一目標(biāo)，SDS的API全部做到了二進(jìn)制安全(binary-safe)。

raw和embstr編碼的SDS區(qū)別

我們?cè)谇懊嬷v過(guò)，長(zhǎng)度大于39字節(jié)的字符串，編碼類型為raw，底層數(shù)據(jù)結(jié)構(gòu)是簡(jiǎn)單動(dòng)態(tài)字符串(SDS)。這個(gè)很好理解，比如當(dāng)我們執(zhí)行set story "Long, long, long ago there lived a king ..."(長(zhǎng)度大于39)之后，Redis就會(huì)創(chuàng)建一個(gè)raw編碼的String對(duì)象。數(shù)據(jù)結(jié)構(gòu)如下：

長(zhǎng)度小于等于39個(gè)字節(jié)的字符串，編碼類型為embstr，底層數(shù)據(jù)結(jié)構(gòu)則是embstr編碼SDS。embstr編碼是專門用來(lái)保存短字符串的，它和raw編碼最大的不同在于：raw編碼會(huì)調(diào)用兩次內(nèi)存分配分別創(chuàng)建redisObject結(jié)構(gòu)和sdshdr結(jié)構(gòu)，而embstr編碼則是只調(diào)用一次內(nèi)存分配，在一塊連續(xù)的空間上同時(shí)包含redisObject結(jié)構(gòu)和sdshdr結(jié)構(gòu)。

編碼轉(zhuǎn)換

int編碼和embstr編碼的字符串對(duì)象在條件滿足的情況下會(huì)自動(dòng)轉(zhuǎn)換為raw編碼的字符串對(duì)象。

對(duì)于int編碼來(lái)說(shuō)，當(dāng)我們修改這個(gè)字符串為不再是整數(shù)值的時(shí)候，此時(shí)字符串對(duì)象的編碼就會(huì)從int變?yōu)閞aw；對(duì)于embstr編碼來(lái)說(shuō)，只要我們修改了字符串的值，此時(shí)字符串對(duì)象的編碼就會(huì)從embstr變?yōu)閞aw。

embstr編碼的字符串對(duì)象可以認(rèn)為是只讀的，因?yàn)镽edis為其編寫(xiě)任何修改程序。當(dāng)我們要修改embstr編碼字符串時(shí)，都是先將轉(zhuǎn)換為raw編碼，然后再進(jìn)行修改。

列表對(duì)象

列表對(duì)象的編碼可以是linkedlist或者ziplist，對(duì)應(yīng)的底層數(shù)據(jù)結(jié)構(gòu)是鏈表和壓縮列表。列表對(duì)象相關(guān)命令可參考：Redis命令-List。

默認(rèn)情況下，當(dāng)列表對(duì)象保存的所有字符串元素的長(zhǎng)度都小于64字節(jié)，且元素個(gè)數(shù)小于512個(gè)時(shí)，列表對(duì)象采用的是ziplist編碼，否則使用linkedlist編碼。

可以通過(guò)配置文件修改該上限值。

鏈表

鏈表是一種非常常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，提供了高效的節(jié)點(diǎn)重排能力以及順序性的節(jié)點(diǎn)訪問(wèn)方式。在Redis中，每個(gè)鏈表節(jié)點(diǎn)使用listNode結(jié)構(gòu)表示：

typedef?struct?listNode?{
????// 前置節(jié)點(diǎn)
????struct?listNode?*prev;
????// 后置節(jié)點(diǎn)
????struct?listNode?*next;
????// 節(jié)點(diǎn)值
????void?*value;
} listNode

多個(gè)listNode通過(guò)prev和next指針組成雙端鏈表，如下圖所示：

為了操作起來(lái)比較方便，Redis使用了list結(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?*(*dup)(void?*ptr);
????// 節(jié)點(diǎn)釋放函數(shù)
????void?(*free)(void?*ptr);
????// 節(jié)點(diǎn)對(duì)比函數(shù)
????int?(*match)(void?*ptr, void?*key);
} list;

list結(jié)構(gòu)為鏈表提供了表頭指針head、表尾指針tail，以及鏈表長(zhǎng)度計(jì)數(shù)器len，而dup、free和match成員則是實(shí)現(xiàn)多態(tài)鏈表所需類型的特定函數(shù)。

Redis鏈表實(shí)現(xiàn)的特征總結(jié)如下：

壓縮列表

壓縮列表(ziplist)是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。壓縮列表主要目的是為了節(jié)約內(nèi)存，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)。一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。

如上圖所示，壓縮列表記錄了各組成部分的類型、長(zhǎng)度以及用途。

哈希對(duì)象

哈希對(duì)象的編碼可以是ziplist或者h(yuǎn)ashtable。

hash-ziplist

ziplist底層使用的是壓縮列表實(shí)現(xiàn)，上文已經(jīng)詳細(xì)介紹了壓縮列表的實(shí)現(xiàn)原理。每當(dāng)有新的鍵值對(duì)要加入哈希對(duì)象時(shí)，先把保存了鍵的節(jié)點(diǎn)推入壓縮列表表尾，然后再將保存了值的節(jié)點(diǎn)推入壓縮列表表尾。比如，我們執(zhí)行如下三條HSET命令：

HSET profile?name "tom"
HSET profile?age 25
HSET profile?career "Programmer"

如果此時(shí)使用ziplist編碼，那么該Hash對(duì)象在內(nèi)存中的結(jié)構(gòu)如下：

hash-hashtable

hashtable編碼的哈希對(duì)象使用字典作為底層實(shí)現(xiàn)。字典是一種用于保存鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，Redis的字典使用哈希表作為底層實(shí)現(xiàn)，一個(gè)哈希表里面可以有多個(gè)哈希表節(jié)點(diǎn)，每個(gè)哈希表節(jié)點(diǎn)保存的就是一個(gè)鍵值對(duì)。

哈希表

Redis使用的哈希表由dictht結(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

table屬性是一個(gè)數(shù)組，數(shù)組中的每個(gè)元素都是一個(gè)指向dictEntry結(jié)構(gòu)的指針，每個(gè)dictEntry結(jié)構(gòu)保存著一個(gè)鍵值對(duì)。size屬性記錄了哈希表的大小，即table數(shù)組的大小。used屬性記錄了哈希表目前已有節(jié)點(diǎn)數(shù)量。sizemask總是等于size-1，這個(gè)值主要用于數(shù)組索引。比如下圖展示了一個(gè)大小為4的空哈希表。

哈希表節(jié)點(diǎn)

哈希表節(jié)點(diǎn)使用dictEntry結(jié)構(gòu)表示，每個(gè)dictEntry結(jié)構(gòu)都保存著一個(gè)鍵值對(duì)：

typedef?struct?dictEntry?{
???// 鍵
???void?*key;

???// 值
???union?{
???????void?*val;
???????unit64_t?u64;
???????nit64_t?s64;
???} v;

???// 指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表
???struct?dictEntry?*next;
} dictEntry;

key屬性保存著鍵值對(duì)中的鍵，而v屬性則保存了鍵值對(duì)中的值。值可以是一個(gè)指針，一個(gè)uint64_t整數(shù)或者是int64_t整數(shù)。next屬性指向了另一個(gè)dictEntry節(jié)點(diǎn)，在數(shù)組桶位相同的情況下，將多個(gè)dictEntry節(jié)點(diǎn)串聯(lián)成一個(gè)鏈表，以此來(lái)解決鍵沖突問(wèn)題。(鏈地址法)

字典

Redis字典由dict結(jié)構(gòu)表示：

typedef?struct?dict?{

???// 類型特定函數(shù)
???dictType *type;

???// 私有數(shù)據(jù)
???void?*privdata;

???// 哈希表
???dictht ht[2];

???//rehash索引
???// 當(dāng)rehash不在進(jìn)行時(shí)，值為-1
???int?rehashidx;
}

ht是大小為2，且每個(gè)元素都指向dictht哈希表。一般情況下，字典只會(huì)使用ht[0]哈希表，ht[1]哈希表只會(huì)在對(duì)ht[0]哈希表進(jìn)行rehash時(shí)使用。rehashidx記錄了rehash的進(jìn)度，如果目前沒(méi)有進(jìn)行rehash，值為-1。

rehash

為了使hash表的負(fù)載因子(ht[0]).used/ht[0]).size)維持在一個(gè)合理范圍，當(dāng)哈希表保存的元素過(guò)多或者過(guò)少時(shí)，程序需要對(duì)hash表進(jìn)行相應(yīng)的擴(kuò)展和收縮。rehash（重新散列）操作就是用來(lái)完成hash表的擴(kuò)展和收縮的。rehash的步驟如下：

哈希表的擴(kuò)展和收縮時(shí)機(jī)：

漸進(jìn)式rehash

前面講過(guò)，擴(kuò)展或者收縮需要將ht[0]里面的元素全部rehash到ht[1]中，如果ht[0]元素很多，顯然一次性rehash成本會(huì)很大，從影響到Redis性能。為了解決上述問(wèn)題，Redis使用了漸進(jìn)式rehash技術(shù)，具體來(lái)說(shuō)就是分多次，漸進(jìn)式地將ht[0]里面的元素慢慢地rehash到ht[1]中。下面是漸進(jìn)式rehash的詳細(xì)步驟：

漸進(jìn)式rehash一次遷移一個(gè)桶上所有的數(shù)據(jù)，設(shè)計(jì)上采用分而治之的思想，將原本集中式的操作分散到每個(gè)添加、刪除、查找和更新操作上，從而避免集中式rehash帶來(lái)的龐大計(jì)算。

因?yàn)樵跐u進(jìn)式rehash時(shí)，字典會(huì)同時(shí)使用ht[0]和ht[1]兩張表，所以此時(shí)對(duì)字典的刪除、查找和更新操作都可能會(huì)在兩個(gè)哈希表進(jìn)行。比如，如果要查找某個(gè)鍵時(shí)，先在ht[0]中查找，如果沒(méi)找到，則繼續(xù)到ht[1]中查找。

hash對(duì)象中的hashtable

HSET profile?name "tom"
HSET profile?age 25
HSET profile?career "Programmer"

還是上述三條命令，保存數(shù)據(jù)到Redis的哈希對(duì)象中，如果采用hashtable編碼保存的話，那么該Hash對(duì)象在內(nèi)存中的結(jié)構(gòu)如下：

當(dāng)哈希對(duì)象保存的所有鍵值對(duì)的鍵和值的字符串長(zhǎng)度都小于64個(gè)字節(jié)，并且數(shù)量小于512個(gè)時(shí)，使用ziplist編碼，否則使用hashtable編碼。

可以通過(guò)配置文件修改該上限值。

集合對(duì)象

集合對(duì)象的編碼可以是intset或者h(yuǎn)ashtable。當(dāng)集合對(duì)象保存的元素都是整數(shù)，并且個(gè)數(shù)不超過(guò)512個(gè)時(shí)，使用intset編碼，否則使用hashtable編碼。

set-intset

intset編碼的集合對(duì)象底層使用整數(shù)集合實(shí)現(xiàn)。

整數(shù)集合(intset)是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)，它可以保存類型為int16_t、int32_t或者int64_t的整數(shù)值，并且保證集合中的數(shù)據(jù)不會(huì)重復(fù)。Redis使用intset結(jié)構(gòu)表示一個(gè)整數(shù)集合。

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

contents數(shù)組是整數(shù)集合的底層實(shí)現(xiàn)：整數(shù)集合的每個(gè)元素都是contents數(shù)組的一個(gè)數(shù)組項(xiàng)，各個(gè)項(xiàng)在數(shù)組中按值大小從小到大有序排列，并且數(shù)組中不包含重復(fù)項(xiàng)。雖然contents屬性聲明為int8_t類型的數(shù)組，但實(shí)際上，contents數(shù)組不保存任何int8_t類型的值，數(shù)組中真正保存的值類型取決于encoding。如果encoding屬性值為INTSET_ENC_INT16，那么contents數(shù)組就是int16_t類型的數(shù)組，以此類推。

當(dāng)新插入元素的類型比整數(shù)集合現(xiàn)有類型元素的類型大時(shí)，整數(shù)集合必須先升級(jí)，然后才能將新元素添加進(jìn)來(lái)。這個(gè)過(guò)程分以下三步進(jìn)行。

還有一點(diǎn)需要注意的是，整數(shù)集合不支持降級(jí)，一旦對(duì)數(shù)組進(jìn)行了升級(jí)，編碼就會(huì)一直保持升級(jí)后的狀態(tài)。

舉個(gè)栗子，當(dāng)我們執(zhí)行SADD numbers 1 3 5向集合對(duì)象插入數(shù)據(jù)時(shí)，該集合對(duì)象在內(nèi)存的結(jié)構(gòu)如下：

set-hashtable

hashtable編碼的集合對(duì)象使用字典作為底層實(shí)現(xiàn)，字典的每個(gè)鍵都是一個(gè)字符串對(duì)象，每個(gè)字符串對(duì)象對(duì)應(yīng)一個(gè)集合元素，字典的值都是NULL。當(dāng)我們執(zhí)行SADD fruits "apple" "banana" "cherry"向集合對(duì)象插入數(shù)據(jù)時(shí)，該集合對(duì)象在內(nèi)存的結(jié)構(gòu)如下：

有序集合對(duì)象

有序集合的編碼可以是ziplist或者skiplist。當(dāng)有序集合保存的元素個(gè)數(shù)小于128個(gè)，且所有元素成員長(zhǎng)度都小于64字節(jié)時(shí)，使用ziplist編碼，否則，使用skiplist編碼。

zset-ziplist

ziplist編碼的有序集合使用壓縮列表作為底層實(shí)現(xiàn)，每個(gè)集合元素使用兩個(gè)緊挨著一起的兩個(gè)壓縮列表節(jié)點(diǎn)表示，第一個(gè)節(jié)點(diǎn)保存元素的成員(member)，第二個(gè)節(jié)點(diǎn)保存元素的分值(score)。

壓縮列表內(nèi)的集合元素按照分值從小到大排列。如果我們執(zhí)行ZADD price 8.5 apple 5.0 banana 6.0 cherry命令，向有序集合插入元素，該有序集合在內(nèi)存中的結(jié)構(gòu)如下：

zset-skiplist

skiplist編碼的有序集合對(duì)象使用zset結(jié)構(gòu)作為底層實(shí)現(xiàn)，一個(gè)zset結(jié)構(gòu)同時(shí)包含一個(gè)字典和一個(gè)跳躍表。

typedef?struct?zset?{
???zskiplist *zs1;
???dict *dict;
}

繼續(xù)介紹之前，我們先了解一下什么是跳躍表。

跳躍表

跳躍表(skiplist)是一種有序的數(shù)據(jù)結(jié)構(gòu)，它通過(guò)在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的。Redis的跳躍表由zskiplistNode和zskiplist兩個(gè)結(jié)構(gòu)定義，zskiplistNode結(jié)構(gòu)表示跳躍表節(jié)點(diǎn)，zskiplist保存跳躍表節(jié)點(diǎn)相關(guān)信息，比如節(jié)點(diǎn)的數(shù)量，以及指向表頭和表尾節(jié)點(diǎn)的指針等。

跳躍表節(jié)點(diǎn) zskiplistNode

跳躍表節(jié)點(diǎn)zskiplistNode結(jié)構(gòu)定義如下：

typedef?struct?zskiplistNode?{
???// 后退指針
???struct?zskiplistNode?*backward;
???// 分值
???double?score;
???// 成員對(duì)象
???robj *obj;
???// 層
???struct?zskiplistLevel?{
???????// 前進(jìn)指針
???????struct?zskiplistNode?*forward;
???????// 跨度
???????unsigned?int?span;
???} level[];
} zskiplistNode;

下圖是一個(gè)層高為5，包含4個(gè)跳躍表節(jié)點(diǎn)(1個(gè)表頭節(jié)點(diǎn)和3個(gè)數(shù)據(jù)節(jié)點(diǎn))組成的跳躍表：

每次創(chuàng)建一個(gè)新的跳躍表節(jié)點(diǎn)的時(shí)候，會(huì)根據(jù)冪次定律(越大的數(shù)出現(xiàn)的概率越低)隨機(jī)生成一個(gè)1-32之間的值作為當(dāng)前節(jié)點(diǎn)的"層高"。每層元素都包含2個(gè)數(shù)據(jù)，前進(jìn)指針和跨度。

1. 前進(jìn)指針

每層都有一個(gè)指向表尾方向的前進(jìn)指針，用于從表頭向表尾方向訪問(wèn)節(jié)點(diǎn)。

2. 跨度

層的跨度用于記錄兩個(gè)節(jié)點(diǎn)之間的距離。

3. 后退指針(BW)

節(jié)點(diǎn)的后退指針用于從表尾向表頭方向訪問(wèn)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只有一個(gè)后退指針，所以每次只能后退一個(gè)節(jié)點(diǎn)。

4. 分值和成員

節(jié)點(diǎn)的分值(score)是一個(gè)double類型的浮點(diǎn)數(shù)，跳躍表中所有節(jié)點(diǎn)都按分值從小到大排列。節(jié)點(diǎn)的成員(obj)是一個(gè)指針，指向一個(gè)字符串對(duì)象。在跳躍表中，各個(gè)節(jié)點(diǎn)保存的成員對(duì)象必須是唯一的，但是多個(gè)節(jié)點(diǎn)的分值確實(shí)可以相同。

需要注意的是，表頭節(jié)點(diǎn)不存儲(chǔ)真實(shí)數(shù)據(jù)，并且層高固定為32，從表頭節(jié)點(diǎn)第一個(gè)不為NULL最高層開(kāi)始，就能實(shí)現(xiàn)快速查找。

跳躍表 zskiplist

實(shí)際上，僅靠多個(gè)跳躍表節(jié)點(diǎn)就可以組成一個(gè)跳躍表，但是Redis使用了zskiplist結(jié)構(gòu)來(lái)持有這些節(jié)點(diǎn)，這樣就能夠更方便地對(duì)整個(gè)跳躍表進(jìn)行操作。比如快速訪問(wèn)表頭和表尾節(jié)點(diǎn)，獲得跳躍表節(jié)點(diǎn)數(shù)量等等。zskiplist結(jié)構(gòu)定義如下：

typedef?struct?zskiplist?{

???// 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
???struct?skiplistNode?*header, *tail;
???// 節(jié)點(diǎn)數(shù)量
???unsigned?long?length;
???// 最大層數(shù)
???int?level;
} zskiplist;

下圖是一個(gè)完整的跳躍表結(jié)構(gòu)示例：

有序集合對(duì)象的skiplist實(shí)現(xiàn)

前面講過(guò)，skiplist編碼的有序集合對(duì)象使用zset結(jié)構(gòu)作為底層實(shí)現(xiàn)，一個(gè)zset結(jié)構(gòu)同時(shí)包含一個(gè)字典和一個(gè)跳躍表。

typedef?struct?zset?{
???zskiplist *zs1;
???dict *dict;
}

zset結(jié)構(gòu)中的zs1跳躍表按分值從小到大保存了所有集合元素，每個(gè)跳躍表節(jié)點(diǎn)都保存了一個(gè)集合元素。通過(guò)跳躍表，可以對(duì)有序集合進(jìn)行基于score的快速范圍查找。zset結(jié)構(gòu)中的dict字典為有序集合創(chuàng)建了從成員到分值的映射，字典的鍵保存了成員，字典的值保存了分值。通過(guò)字典，可以用O(1)復(fù)雜度查找給定成員的分值。

假如還是執(zhí)行ZADD price 8.5 apple 5.0 banana 6.0 cherry命令向zset保存數(shù)據(jù)，如果采用skiplist編碼方式的話，該有序集合在內(nèi)存中的結(jié)構(gòu)如下：

總結(jié)

總的來(lái)說(shuō)，Redis底層數(shù)據(jù)結(jié)構(gòu)主要包括簡(jiǎn)單動(dòng)態(tài)字符串(SDS)、鏈表、字典、跳躍表、整數(shù)集合和壓縮列表六種類型，并且基于這些基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了字符串對(duì)象、列表對(duì)象、哈希對(duì)象、集合對(duì)象以及有序集合對(duì)象五種常見(jiàn)的對(duì)象類型。每一種對(duì)象類型都至少采用了2種數(shù)據(jù)編碼，不同的編碼使用的底層數(shù)據(jù)結(jié)構(gòu)也不同。

原文鏈接：cnblogs.com/chentianming/p/13838347.html