整數(shù)集合

整數(shù)集合是 ?Set 對(duì)象的底層實(shí)現(xiàn)之一。當(dāng)一個(gè) Set 對(duì)象只包含整數(shù)值元素，并且元素?cái)?shù)量不時(shí)，就會(huì)使用整數(shù)集這個(gè)數(shù)據(jù)結(jié)構(gòu)作為底層實(shí)現(xiàn)。

整數(shù)集合結(jié)構(gòu)設(shè)計(jì)

整數(shù)集合本質(zhì)上是一塊連續(xù)內(nèi)存空間，它的結(jié)構(gòu)定義如下：

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

可以看到，保存元素的容器是一個(gè) contents 數(shù)組，雖然 contents 被聲明為 int8_t 類(lèi)型的數(shù)組，但是實(shí)際上 contents 數(shù)組并不保存任何 int8_t 類(lèi)型的元素，contents 數(shù)組的真正類(lèi)型取決于 intset 結(jié)構(gòu)體里的 encoding 屬性的值。比如：

• 如果 encoding 屬性值為 INTSET_ENC_INT16，那么 contents 就是一個(gè) int16_t 類(lèi)型的數(shù)組，數(shù)組中每一個(gè)元素的類(lèi)型都是 int16_t；

• 如果 encoding 屬性值為 INTSET_ENC_INT32，那么 contents 就是一個(gè) int32_t 類(lèi)型的數(shù)組，數(shù)組中每一個(gè)元素的類(lèi)型都是 int32_t；

• 如果 encoding 屬性值為 INTSET_ENC_INT64，那么 contents 就是一個(gè) int64_t 類(lèi)型的數(shù)組，數(shù)組中每一個(gè)元素的類(lèi)型都是 int64_t；

不同類(lèi)型的 contents 數(shù)組，意味著數(shù)組的大小也會(huì)不同。

整數(shù)集合的升級(jí)操作

整數(shù)集合會(huì)有一個(gè)升級(jí)規(guī)則，就是當(dāng)我們將一個(gè)新元素加入到整數(shù)集合里面，如果新元素的類(lèi)型（int32_t）比整數(shù)集合現(xiàn)有所有元素的類(lèi)型（int16_t）都要長(zhǎng)時(shí)，整數(shù)集合需要先進(jìn)行升級(jí)，也就是按新元素的類(lèi)型（int32_t）擴(kuò)展 contents 數(shù)組的空間大小，然后才能將新元素加入到整數(shù)集合里，當(dāng)然升級(jí)的過(guò)程中，也要維持整數(shù)集合的有序性。

整數(shù)集合升級(jí)的過(guò)程不會(huì)重新分配一個(gè)新類(lèi)型的數(shù)組，而是在原本的數(shù)組上擴(kuò)展空間，然后在將每個(gè)元素按間隔類(lèi)型大小分割，如果 encoding 屬性值為 INTSET_ENC_INT16，則每個(gè)元素的間隔就是 16 位。

舉個(gè)例子，假設(shè)有一個(gè)整數(shù)集合里有 3 個(gè)類(lèi)型為 int16_t 的元素。

現(xiàn)在，往這個(gè)整數(shù)集合中加入一個(gè)新元素 65535，這個(gè)新元素需要用 int32_t 類(lèi)型來(lái)保存，所以整數(shù)集合要進(jìn)行升級(jí)操作，首先需要為 contents 數(shù)組擴(kuò)容，在原本空間的大小之上再擴(kuò)容多 80 位（4x32-3x16=80），這樣就能保存下 4 個(gè)類(lèi)型為 int32_t 的元素。

擴(kuò)容完 contents 數(shù)組空間大小后，需要將之前的三個(gè)元素轉(zhuǎn)換為 int32_t 類(lèi)型，并將轉(zhuǎn)換后的元素放置到正確的位上面，并且需要維持底層數(shù)組的有序性不變，整個(gè)轉(zhuǎn)換過(guò)程如下：

整數(shù)集合升級(jí)有什么好處呢？

如果要讓一個(gè)數(shù)組同時(shí)保存 int16_t、int32_t、int64_t 類(lèi)型的元素，最簡(jiǎn)單做法就是直接使用 int64_t 類(lèi)型的數(shù)組。不過(guò)這樣的話，當(dāng)如果元素都是 int16_t 類(lèi)型的，就會(huì)造成內(nèi)存浪費(fèi)的情況。

整數(shù)集合升級(jí)就能避免這種情況，如果一直向整數(shù)集合添加 int16_t 類(lèi)型的元素，那么整數(shù)集合的底層實(shí)現(xiàn)就一直是用 int16_t 類(lèi)型的數(shù)組，只有在我們要將 int32_t 類(lèi)型或 int64_t 類(lèi)型的元素添加到集合時(shí)，才會(huì)對(duì)數(shù)組進(jìn)行升級(jí)操作。

因此，整數(shù)集合升級(jí)的好處是節(jié)省內(nèi)存資源。

整數(shù)集合支持降級(jí)操作嗎？

不支持降級(jí)操作，一旦對(duì)數(shù)組進(jìn)行了升級(jí)，就會(huì)一直保持升級(jí)后的狀態(tài)。比如前面的升級(jí)操作的例子，如果刪除了 65535 元素，整數(shù)集合的數(shù)組還是 int32_t 類(lèi)型的，并不會(huì)因此降級(jí)為 int16_t 類(lèi)型。

跳表

Redis 只有在 Zset 對(duì)象的底層實(shí)現(xiàn)用到了跳表，跳表的優(yōu)勢(shì)是能支持平均 O(logN) 復(fù)雜度的節(jié)點(diǎn)查找。

Zset 對(duì)象是唯一一個(gè)同時(shí)使用了兩個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的 Redis 對(duì)象，這兩個(gè)數(shù)據(jù)結(jié)構(gòu)一個(gè)是跳表，一個(gè)是哈希表。這樣的好處是既能進(jìn)行高效的范圍查詢，也能進(jìn)行高效單點(diǎn)查詢。

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

Zset 對(duì)象能支持范圍查詢（如 ZRANGEBYSCORE 操作），這是因?yàn)樗臄?shù)據(jù)結(jié)構(gòu)設(shè)計(jì)采用了跳表，而又能以常數(shù)復(fù)雜度獲取元素權(quán)重（如 ZSCORE 操作），這是因?yàn)樗瑫r(shí)采用了哈希表進(jìn)行索引。

跳表結(jié)構(gòu)設(shè)計(jì)

鏈表在查找元素的時(shí)候，因?yàn)樾枰鹨徊檎?，所以查詢效率非常低，時(shí)間復(fù)雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎(chǔ)上改進(jìn)過(guò)來(lái)的，實(shí)現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。

那跳表長(zhǎng)什么樣呢？我這里舉個(gè)例子，下圖展示了一個(gè)層級(jí)為 3 的跳表。

圖中頭節(jié)點(diǎn)有 L0~L2 三個(gè)頭指針，分別指向了不同層級(jí)的節(jié)點(diǎn)，然后每個(gè)層級(jí)的節(jié)點(diǎn)都通過(guò)指針連接起來(lái)：

• L0 層級(jí)共有 5 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn)1、2、3、4、5；

• L1 層級(jí)共有 3 個(gè)節(jié)點(diǎn)，分別是節(jié)點(diǎn) 2、3、5；

• L2 層級(jí)只有 1 個(gè)節(jié)點(diǎn)，也就是節(jié)點(diǎn) 3 。

如果我們要在鏈表中查找節(jié)點(diǎn) 4 這個(gè)元素，只能從頭開(kāi)始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點(diǎn) 4，因?yàn)榭梢栽陬^節(jié)點(diǎn)直接從 L2 層級(jí)跳到節(jié)點(diǎn) 3，然后再往前遍歷找到節(jié)點(diǎn) 4。

可以看到，這個(gè)查找過(guò)程就是在多個(gè)層級(jí)上跳來(lái)跳去，最后定位到元素。當(dāng)數(shù)據(jù)量很大時(shí)，跳表的查找復(fù)雜度就是 O(logN)。

那跳表節(jié)點(diǎn)是怎么實(shí)現(xiàn)多層級(jí)的呢？這就需要看「跳表節(jié)點(diǎn)」的數(shù)據(jù)結(jié)構(gòu)了，如下：

typedef?struct?zskiplistNode?{
????//Zset?對(duì)象的元素值
????sds?ele;
????//元素權(quán)重值
????double?score;
????//后向指針
????struct?zskiplistNode?*backward;

????//節(jié)點(diǎn)的level數(shù)組，保存每層上的前向指針和跨度
????struct?zskiplistLevel?{
????????struct?zskiplistNode?*forward;
????????unsigned?long?span;
????}?level[];
}?zskiplistNode;

Zset 對(duì)象要同時(shí)保存元素和元素的權(quán)重，對(duì)應(yīng)到跳表節(jié)點(diǎn)結(jié)構(gòu)里就是 sds 類(lèi)型的 ele 變量和 double 類(lèi)型的 score 變量。每個(gè)跳表節(jié)點(diǎn)都有一個(gè)后向指針，指向前一個(gè)節(jié)點(diǎn)，目的是為了方便從跳表的尾節(jié)點(diǎn)開(kāi)始訪問(wèn)節(jié)點(diǎn)，這樣倒序查找時(shí)很方便。

跳表是一個(gè)帶有層級(jí)關(guān)系的鏈表，而且每一層級(jí)可以包含多個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)通過(guò)指針連接起來(lái)，實(shí)現(xiàn)這一特性就是靠跳表節(jié)點(diǎn)結(jié)構(gòu)體中的zskiplistLevel 結(jié)構(gòu)體類(lèi)型的 level 數(shù)組。

level 數(shù)組中的每一個(gè)元素代表跳表的一層，也就是由 zskiplistLevel 結(jié)構(gòu)體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了「指向下一個(gè)跳表節(jié)點(diǎn)的指針」和「跨度」，跨度時(shí)用來(lái)記錄兩個(gè)節(jié)點(diǎn)之間的距離。

比如，下面這張圖，展示了各個(gè)節(jié)點(diǎn)的跨度。

第一眼看到跨度的時(shí)候，以為是遍歷操作有關(guān)，實(shí)際上并沒(méi)有任何關(guān)系，遍歷操作只需要用前向指針就可以完成了。

跨度實(shí)際上是為了計(jì)算這個(gè)節(jié)點(diǎn)在跳表中的排位。具體怎么做的呢？因?yàn)樘碇械墓?jié)點(diǎn)都是按序排列的，那么計(jì)算某個(gè)節(jié)點(diǎn)排位的時(shí)候，從頭節(jié)點(diǎn)點(diǎn)到該結(jié)點(diǎn)的查詢路徑上，將沿途訪問(wèn)過(guò)的所有層的跨度累加起來(lái)，得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳表中的排位。

舉個(gè)例子，查找圖中節(jié)點(diǎn) 3 在跳表中的排位，從頭節(jié)點(diǎn)開(kāi)始查找節(jié)點(diǎn) 3，查找的過(guò)程只經(jīng)過(guò)了一個(gè)層（L3），并且層的跨度是 3，所以節(jié)點(diǎn) 3 在跳表中的排位是 3。

另外，圖中的頭節(jié)點(diǎn)其實(shí)也是 zskiplistNode 跳表節(jié)點(diǎn)，只不過(guò)頭節(jié)點(diǎn)的后向指針、權(quán)重、元素值都會(huì)被用到，所以圖中省略了這部分。

問(wèn)題來(lái)了，由誰(shuí)定義哪個(gè)跳表節(jié)點(diǎn)是頭節(jié)點(diǎn)呢？這就介紹「跳表」結(jié)構(gòu)體了，如下所示：

typedef?struct?zskiplist?{
????struct?zskiplistNode?*header,?*tail;
????unsigned?long?length;
????int?level;
}?zskiplist;

跳表結(jié)構(gòu)里包含了：

• 跳表的頭尾節(jié)點(diǎn)，便于在O(1)時(shí)間復(fù)雜度內(nèi)訪問(wèn)跳表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)；

• 跳表的長(zhǎng)度，便于在O(1)時(shí)間復(fù)雜度獲取跳表節(jié)點(diǎn)的數(shù)量；

• 跳表的最大層數(shù)，便于在O(1)時(shí)間復(fù)雜度獲取跳表中層高最大的那個(gè)節(jié)點(diǎn)的層數(shù)量；

跳表節(jié)點(diǎn)查詢過(guò)程

查找一個(gè)跳表節(jié)點(diǎn)的過(guò)程時(shí)，跳表會(huì)從頭節(jié)點(diǎn)的最高層開(kāi)始，逐一遍歷每一層。在遍歷某一層的跳表節(jié)點(diǎn)時(shí)，會(huì)用跳表節(jié)點(diǎn)中的 SDS 類(lèi)型的元素和元素的權(quán)重來(lái)進(jìn)行判斷，共有兩個(gè)判斷條件：

• 如果當(dāng)前節(jié)點(diǎn)的權(quán)重「小于」要查找的權(quán)重時(shí)，跳表就會(huì)訪問(wèn)該層上的下一個(gè)節(jié)點(diǎn)。

• 如果當(dāng)前節(jié)點(diǎn)的權(quán)重「等于」要查找的權(quán)重時(shí)，并且當(dāng)前節(jié)點(diǎn)的 SDS 類(lèi)型數(shù)據(jù)「小于」要查找的數(shù)據(jù)時(shí)，跳表就會(huì)訪問(wèn)該層上的下一個(gè)節(jié)點(diǎn)。

如果上面兩個(gè)條件都不滿足，或者下一個(gè)節(jié)點(diǎn)為空時(shí)，跳表就會(huì)使用目前遍歷到的節(jié)點(diǎn)的 level 數(shù)組里的下一層指針，然后沿著下一層指針繼續(xù)查找，這就相當(dāng)于跳到了下一層接著查找。

舉個(gè)例子，下圖有個(gè) 3 層級(jí)的跳表。

如果要查找「元素：abcd，權(quán)重：4」的節(jié)點(diǎn)，查找的過(guò)程是這樣的：

• 先從頭節(jié)點(diǎn)的最高層開(kāi)始，L2 指向了「元素：abc，權(quán)重：3」節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的權(quán)重比要查找節(jié)點(diǎn)的小，所以要訪問(wèn)該層上的下一個(gè)節(jié)點(diǎn)；

• 但是該層上的下一個(gè)節(jié)點(diǎn)是空節(jié)點(diǎn)，于是就會(huì)跳到「元素：abc，權(quán)重：3」節(jié)點(diǎn)的下一層去找，也就是 leve[1];

• 「元素：abc，權(quán)重：3」節(jié)點(diǎn)的 ?leve[1] 的下一個(gè)指針指向了「元素：abcde，權(quán)重：4」的節(jié)點(diǎn)，然后將其和要查找的節(jié)點(diǎn)比較。雖然「元素：abcde，權(quán)重：4」的節(jié)點(diǎn)的權(quán)重和要查找的權(quán)重相同，但是當(dāng)前節(jié)點(diǎn)的 SDS 類(lèi)型數(shù)據(jù)「大于」要查找的數(shù)據(jù)，所以會(huì)繼續(xù)跳到「元素：abc，權(quán)重：3」節(jié)點(diǎn)的下一層去找，也就是 leve[0]；

• 「元素：abc，權(quán)重：3」節(jié)點(diǎn)的 leve[0] 的下一個(gè)指針指向了「元素：abcd，權(quán)重：4」的節(jié)點(diǎn)，該節(jié)點(diǎn)正是要查找的節(jié)點(diǎn)，查詢結(jié)束。

跳表節(jié)點(diǎn)層數(shù)設(shè)置

跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量的比例會(huì)影響跳表的查詢性能。

舉個(gè)例子，下圖的跳表，第二層的節(jié)點(diǎn)數(shù)量只有 1 個(gè)，而第一層的節(jié)點(diǎn)數(shù)量有 6 個(gè)。

這時(shí)，如果想要查詢節(jié)點(diǎn) 6，那基本就跟鏈表的查詢復(fù)雜度一樣，就需要在第一層的節(jié)點(diǎn)中依次順序查找，復(fù)雜度就是 O(N) 了。所以，為了降低查詢復(fù)雜度，我們就需要維持相鄰層結(jié)點(diǎn)數(shù)間的關(guān)系。

跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量最理想的比例是 2:1，查找復(fù)雜度可以降低到 O(logN)。

下圖的跳表就是，相鄰兩層的節(jié)點(diǎn)數(shù)量的比例是 2 : 1。

那怎樣才能維持相鄰兩層的節(jié)點(diǎn)數(shù)量的比例為 2 : 1 ?呢？

如果采用新增節(jié)點(diǎn)或者刪除節(jié)點(diǎn)時(shí)，來(lái)調(diào)整跳表節(jié)點(diǎn)以維持比例的方法的話，會(huì)帶來(lái)額外的開(kāi)銷(xiāo)。

Redis 則采用一種巧妙的方法是，跳表在創(chuàng)建節(jié)點(diǎn)的時(shí)候，隨機(jī)生成每個(gè)節(jié)點(diǎn)的層數(shù)，并沒(méi)有嚴(yán)格維持相鄰兩層的節(jié)點(diǎn)數(shù)量比例為 2 : 1 的情況。

具體的做法是，跳表在創(chuàng)建節(jié)點(diǎn)時(shí)候，會(huì)生成范圍為[0-1]的一個(gè)隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于 0.25（相當(dāng)于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個(gè)隨機(jī)數(shù)，直到隨機(jī)數(shù)的結(jié)果大于 0.25 結(jié)束，最終確定該節(jié)點(diǎn)的層數(shù)。

這樣的做法，相當(dāng)于每增加一層的概率不超過(guò) 25%，層數(shù)越高，概率越低，層高最大限制是 64。

quicklist

在 Redis 3.0 之前，List 對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)是雙向鏈表或者壓縮列表。然后在 ?Redis 3.2 的時(shí)候，List 對(duì)象的底層改由 quicklist 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。

其實(shí) quicklist 就是「雙向鏈表 + 壓縮列表」組合，因?yàn)橐粋€(gè) quicklist 就是一個(gè)鏈表，而鏈表中的每個(gè)元素又是一個(gè)壓縮列表。

在前面講壓縮列表的時(shí)候，我也提到了壓縮列表的不足，雖然壓縮列表是通過(guò)緊湊型的內(nèi)存布局節(jié)省了內(nèi)存開(kāi)銷(xiāo)，但是因?yàn)樗慕Y(jié)構(gòu)設(shè)計(jì)，如果保存的元素?cái)?shù)量增加，或者元素變大了，壓縮列表會(huì)有「連鎖更新」的風(fēng)險(xiǎn)，一旦發(fā)生，會(huì)造成性能下降。

quicklist 解決辦法，通過(guò)控制每個(gè)鏈表節(jié)點(diǎn)中的壓縮列表的大小或者元素個(gè)數(shù)，來(lái)規(guī)避連鎖更新的問(wèn)題。因?yàn)閴嚎s列表元素越少或越小，連鎖更新帶來(lái)的影響就越小，從而提供了更好的訪問(wèn)性能。

quicklist 結(jié)構(gòu)設(shè)計(jì)

quicklist 的結(jié)構(gòu)體跟鏈表的結(jié)構(gòu)體類(lèi)似，都包含了表頭和表尾，區(qū)別在于 quicklist 的節(jié)點(diǎn)是 quicklistNode。

typedef?struct?quicklist?{
????//quicklist的鏈表頭
????quicklistNode?*head;??????//quicklist的鏈表頭
????//quicklist的鏈表頭
????quicklistNode?*tail;?
????//所有壓縮列表中的總元素個(gè)數(shù)
????unsigned?long?count;
????//quicklistNodes的個(gè)數(shù)
????unsigned?long?len;???????
????...
}?quicklist;

接下來(lái)看看，quicklistNode 的結(jié)構(gòu)定義：

typedef?struct?quicklistNode?{
????//前一個(gè)quicklistNode
????struct?quicklistNode?*prev;?????//前一個(gè)quicklistNode
????//下一個(gè)quicklistNode
????struct?quicklistNode?*next;?????//后一個(gè)quicklistNode
????//quicklistNode指向的壓縮列表
????unsigned?char?*zl;??????????????
????//壓縮列表的的字節(jié)大小
????unsigned?int?sz;????????????????
????//壓縮列表的元素個(gè)數(shù)
????unsigned?int?count?:?16;????????//ziplist中的元素個(gè)數(shù)?
????....
}?quicklistNode;

可以看到，quicklistNode 結(jié)構(gòu)體里包含了前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)指針，這樣每個(gè) quicklistNode 形成了一個(gè)雙向鏈表。但是鏈表節(jié)點(diǎn)的元素不再是單純保存元素值，而是保存了一個(gè)壓縮列表，所以 quicklistNode 結(jié)構(gòu)體里有個(gè)指向壓縮列表的指針 *zl。

我畫(huà)了一張圖，方便你理解 quicklist 數(shù)據(jù)結(jié)構(gòu)。

在向 quicklist 添加一個(gè)元素的時(shí)候，不會(huì)像普通的鏈表那樣，直接新建一個(gè)鏈表節(jié)點(diǎn)。而是會(huì)檢查插入位置的壓縮列表是否能容納該元素，如果能容納就直接保存到 quicklistNode 結(jié)構(gòu)里的壓縮列表，如果不能容納，才會(huì)新建一個(gè)新的 quicklistNode 結(jié)構(gòu)。

quicklist 會(huì)控制 quicklistNode 結(jié)構(gòu)里的壓縮列表的大小或者元素個(gè)數(shù)，來(lái)規(guī)避潛在的連鎖更新的風(fēng)險(xiǎn)，但是這并沒(méi)有完全解決連鎖更新的問(wèn)題。

listpack

quicklist 雖然通過(guò)控制 quicklistNode 結(jié)構(gòu)里的壓縮列表的大小或者元素個(gè)數(shù)，來(lái)減少連鎖更新帶來(lái)的性能影響，但是并沒(méi)有完全解決連鎖更新的問(wèn)題。

因?yàn)?quicklistNode 還是用了壓縮列表來(lái)保存元素，壓縮列表連鎖更新的問(wèn)題，來(lái)源于它的結(jié)構(gòu)設(shè)計(jì)，所以要想徹底解決這個(gè)問(wèn)題，需要設(shè)計(jì)一個(gè)新的數(shù)據(jù)結(jié)構(gòu)。

于是，Redis 在 5.0 新設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)叫 listpack，目的是替代壓縮列表，它最大特點(diǎn)是 listpack 中每個(gè)節(jié)點(diǎn)不再包含前一個(gè)節(jié)點(diǎn)的長(zhǎng)度了，壓縮列表每個(gè)節(jié)點(diǎn)正因?yàn)樾枰４媲耙粋€(gè)節(jié)點(diǎn)的長(zhǎng)度字段，就會(huì)有連鎖更新的隱患。

listpack 結(jié)構(gòu)設(shè)計(jì)

listpack 采用了壓縮列表的很多優(yōu)秀的設(shè)計(jì)，比如還是用一塊連續(xù)的內(nèi)存空間來(lái)緊湊地保存數(shù)據(jù)，并且為了節(jié)省內(nèi)存的開(kāi)銷(xiāo)，listpack 節(jié)點(diǎn)會(huì)采用不同的編碼方式保存不同大小的數(shù)據(jù)。

我們先看看 listpack 結(jié)構(gòu)：

listpack 頭包含兩個(gè)屬性，分別記錄了 listpack 總字節(jié)數(shù)和元素?cái)?shù)量，然后 listpack 末尾也有個(gè)結(jié)尾標(biāo)識(shí)。圖中的 listpack entry 就是 listpack 的節(jié)點(diǎn)了。

每個(gè) listpack 節(jié)點(diǎn)結(jié)構(gòu)如下：

主要包含三個(gè)方面內(nèi)容：

• encoding，定義該元素的編碼類(lèi)型，會(huì)對(duì)不同長(zhǎng)度的整數(shù)和字符串進(jìn)行編碼；

• data，實(shí)際存放的數(shù)據(jù)；

• len，encoding+data的總長(zhǎng)度；

可以看到，listpack 沒(méi)有壓縮列表中記錄前一個(gè)節(jié)點(diǎn)長(zhǎng)度的字段了，listpack 只記錄當(dāng)前節(jié)點(diǎn)的長(zhǎng)度，當(dāng)我們向 listpack 加入一個(gè)新元素的時(shí)候，不會(huì)影響其他節(jié)點(diǎn)的長(zhǎng)度字段的變化，從而避免了壓縮列表的連鎖更新問(wèn)題。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-700282.html

到了這里，關(guān)于redis 數(shù)據(jù)結(jié)構(gòu)（二）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！