整數(shù)集合相信有的同學(xué)沒(méi)有聽(tīng)說(shuō)過(guò)，因?yàn)閞edis對(duì)外提供的只有封裝的五大對(duì)象！前面我們分別從redis內(nèi)部結(jié)構(gòu)分析了redis的List、Hash、Zset三種數(shù)據(jù)結(jié)構(gòu)了。今天我們?cè)賮?lái)分析set數(shù)據(jù)結(jié)構(gòu)內(nèi)部是如何存儲(chǔ)的。

基本結(jié)構(gòu)

在src/t_set.c中我們發(fā)現(xiàn)這樣一段代碼

由此我們可知在set中是由兩種數(shù)據(jù)結(jié)構(gòu)構(gòu)成的： hashtable+intset 。關(guān)于redis內(nèi)部其他的結(jié)構(gòu)我專(zhuān)門(mén)在【redis專(zhuān)欄中有介紹】。hashtable不是我們今天的主角，我們今天先分析intset俗稱(chēng)整數(shù)集合。

從上圖中我們可以看出，我構(gòu)造了兩個(gè)set集合分別為【commonset】、【cs】。兩個(gè)集合前者存儲(chǔ)字符串、后者專(zhuān)門(mén)存儲(chǔ)數(shù)字。

我們?cè)谕ㄟ^(guò)object encoding key 來(lái)查看下兩個(gè)集合的底層數(shù)據(jù)結(jié)構(gòu)，發(fā)現(xiàn)一個(gè)是hashtable 一個(gè)是intset 。這也驗(yàn)證了我們上面對(duì)set基本結(jié)構(gòu)的描述。

在redis中對(duì)外提供五大類(lèi)型實(shí)際上都是redis的一個(gè)抽象對(duì)象叫做redisobject。在內(nèi)部映射了我們r(jià)edis內(nèi)部的數(shù)據(jù)結(jié)構(gòu)

針對(duì)commonset和cs兩個(gè)集合在內(nèi)部數(shù)據(jù)結(jié)構(gòu)大概可以這么理解

何時(shí)使用intset

你可以單純的認(rèn)為只要是數(shù)字就會(huì)使用intset結(jié)構(gòu)來(lái)存儲(chǔ)，我恐怕要給你當(dāng)頭一棒了。實(shí)際上并不是這樣

需要同時(shí)滿(mǎn)足以下兩個(gè)條件：

intset

圖中表示的很清楚了，在intset中的encoding有三種取值分別代表contents保存數(shù)據(jù)類(lèi)型。這里有人可能會(huì)有疑問(wèn)了contents的類(lèi)型不就是int8_t嗎？為什么還需要encoding呢？這里通過(guò)源碼跟蹤內(nèi)部的確跟int8_t沒(méi)啥關(guān)系。而且數(shù)據(jù)的默認(rèn)類(lèi)型就是int16_t 。關(guān)于length這里無(wú)需太多解釋?zhuān)涀∫稽c(diǎn)表示contents元素的個(gè)數(shù)并非表示contents數(shù)組的長(zhǎng)度！

了解intset的同學(xué)都知道在encoding三種取值范圍中涉及了升級(jí)的操作！在講升級(jí)之前我們先來(lái)了解下C、C++中int的取值范圍是如何定義的

int8_t的取值范圍是【-128,127】 。 類(lèi)似于java中byte占1個(gè)字節(jié)也就是8位。他的取值范圍是

[-2^{7} sim 2^{7}-1 \即 \ -128 sim 127 ]

添加元素

sadd juejin -123 sadd juejin -6 sadd juejin 12 sadd juejin 56 sadd juejin 321

juejin這個(gè)key內(nèi)部就是intset 。

上面我們添加了5個(gè)元素且這五個(gè)元素的長(zhǎng)度都在16之內(nèi)！所以當(dāng)前的intset的encoding=INTSET_ENC_INT16。-123在contents中占前16位。

所以當(dāng)前五個(gè)元素占contents的長(zhǎng)度是16*5=80 ；

注意set在存儲(chǔ)int類(lèi)型數(shù)據(jù)時(shí)，內(nèi)部是按照從小到大的順序存儲(chǔ)的。

類(lèi)型變動(dòng)

上面的問(wèn)題不知道你有沒(méi)有考慮過(guò)，或者說(shuō)有沒(méi)有遇到過(guò)！intset默認(rèn)是int16位，正如我們上面添加的五個(gè)元素。加入此時(shí)我們添加第6個(gè)元素是65535(32位)。那么此時(shí)16位的長(zhǎng)度就不夠存儲(chǔ)了這個(gè)時(shí)候intset會(huì)怎么做！

另外當(dāng)我們添加第6個(gè)元素后又將65535刪除了之后，結(jié)構(gòu)和添加之前是否一樣！下面我們帶著這兩個(gè)問(wèn)題來(lái)一探究竟?。?！

升級(jí)

首先我們針對(duì)第一問(wèn)題來(lái)看看。原來(lái)五個(gè)元素都是16位就可以滿(mǎn)足了，這個(gè)時(shí)候添加的65535是32位長(zhǎng)度的。那么是不是可以直接追加32位分配給65535呢？

答案是肯定不行，首先直接追加無(wú)法保證數(shù)組元素的大小順序！其次如果前五個(gè)分別是16位，第6個(gè)是32位那么在intset結(jié)構(gòu)中沒(méi)有多余的字段來(lái)進(jìn)行標(biāo)記。也就是說(shuō)在解析的時(shí)候就無(wú)法判斷應(yīng)該解析16位還是32位了.

redis為了方便解析所以在有高長(zhǎng)度加入時(shí)會(huì)將整個(gè)contents進(jìn)行升級(jí)。意思就是將整個(gè)contents先進(jìn)行擴(kuò)容，然后在重新填充數(shù)據(jù)

加入65535

首先根據(jù)length可以確定擴(kuò)容后元素個(gè)數(shù)為6 ， 每個(gè)占位32，所以contents長(zhǎng)度為32*6=192 。 此時(shí)前80位內(nèi)容保持不變

舊數(shù)據(jù)移位

開(kāi)辟了足夠的空間后，我們就可以對(duì)舊數(shù)據(jù)進(jìn)行移位了這里我們從原數(shù)組的末尾開(kāi)始移動(dòng)，在移動(dòng)之前需要明確在新數(shù)組中的排序位置。

此時(shí)我們首先將321進(jìn)行比對(duì)確定在新數(shù)組中他的排名是第五名，那么他將占用新contents中128~159區(qū)間。

最終前5 個(gè)元素就會(huì)被移動(dòng)好 。

最后將新加入的元素填充進(jìn)去。當(dāng)發(fā)生升級(jí)時(shí)肯定是因?yàn)樾略氐拈L(zhǎng)度大于原有長(zhǎng)度了。那么他的值一定會(huì)是在新數(shù)組的兩端。負(fù)數(shù)在最左側(cè)，正數(shù)在最右側(cè)

降級(jí)

接下來(lái)就是第二個(gè)問(wèn)題當(dāng)新加入的65535又被刪除了redis該怎么辦，這個(gè)時(shí)候元素長(zhǎng)度實(shí)際16位就可以滿(mǎn)足了，但是此時(shí)encoding卻是32位的。按照我的看法應(yīng)該在實(shí)現(xiàn)降級(jí)！

但是遺憾的是redis并沒(méi)有，那么請(qǐng)思考為什么沒(méi)有？如果讓你實(shí)現(xiàn)你將如何實(shí)現(xiàn)

為什么不實(shí)現(xiàn)降級(jí)

當(dāng)加入元素超過(guò)當(dāng)前長(zhǎng)度我們很容易就知道此時(shí)需要進(jìn)行升級(jí)操作，但是當(dāng)我們刪除一個(gè)數(shù)據(jù)時(shí)我們?nèi)绾闻袛嗍欠裥枰导?jí)卻很困難，我們需要重新遍歷一遍剩下的元素是否小于當(dāng)前長(zhǎng)度，實(shí)現(xiàn)復(fù)雜度O(N) 。這就是為什么不進(jìn)行降級(jí)原因之一

你可能會(huì)說(shuō)重新遍歷一遍很快的反正在內(nèi)存中，那么你有沒(méi)有想過(guò)如果降級(jí)之后又遇到升級(jí)情況，這樣來(lái)回的升級(jí)降級(jí)就降低了我們程序的性能了。我們知道升級(jí)是必須的所以這里降級(jí)redis采取的是忽略的策略

小結(jié)

相關(guān)教程推薦：Redis教程