一、回顧

通過對Redis的數據結構學習，簡單回顧一下數據結構在Redis中的實現有哪些？

簡單動态字符串（SDS），它用于Redis字符串鍵值對的底層實現。

鍊表，它是列表鍵的底層實現之一，以及發布、訂閱、慢查詢、監視器等。

字典，它是哈希鍵的底層實現之一，以及Redis數據庫的底層實現。

跳躍表，它是有序集合鍵的底層實現之一。

通過以上的數據結構學習，基本上覆蓋了Redis中所支持的五大數據類型，字符串、列表、哈希、集合、有序集合的底層實現。

那麼今天，要繼續學習的是，Redis中的另外兩個數據結構。

整數集合，它是集合鍵的底層實現之一。

壓縮列表，它是列表鍵和哈希鍵的底層實現之一。

二、整數集合

整數集合是Redis用于保存整數值的集合抽象數據結構。它支持編碼為 int16、int32、int64 的整數值。存儲元素的值必須唯一。

#每個 intset.h/intset結構表示一個整數集合 typedef struct intset { #編碼方式 uint32_t encoding; #集合包含的元素數量 uint32_t length; #保存元素的數組 int8_t contents[]; }intset;

contents 數組是整數集合的底層實現，整數集合的每個元素都是contents數組的一個數組項。各個項從小到大的排序，并且每個項元素值唯一。

length 屬性記錄了整數集合包含元素的數量，即contents的長度。

encoding 屬性的值為 INTSET_ENC_INT16、INTSET_ENC_INT32，INTSET_ENC_INT64

如果encoding 的值為INTSET_ENC_INT16，則 contents 就是一個 int16_t類型的數組，數組内都是 int16_t類型的整數值。範圍（-32768 至 32767）

如果encoding 的值為INTSET_ENC_INT32，則 contents 就是一個 int32_t類型的數組，數組内都是 int32_t類型的整數值。範圍（-2147483648 至 2147483647）

如果encoding 的值為INTSET_ENC_INT64，則 contents 就是一個 int64_t類型的數組，數組内都是 int64_t類型的整數值（-9223372036854775808 至 9223372036854775807）

例如上圖是一個整數集合，集合中的編碼為 int16_t 所以，contents 的數組項的大小需要在編碼為 int16 的範圍之内。

三、整數集合-升級

假設我們有一個整數集合，并且這個整數集合的編碼為 int16_t

此時，我們需要将一個 int32_t 的數據項存儲到該整數集合中。應該發生哪些動作呢？

1）對整數集合進行升級

2）再将新元素添加到整數集合中

3.1 升級整數集合一般需要三個步驟

• 根據新元素的類型，擴展整數集合底層數組的空間大小，并為新元素分配空間
• 将底層數組現有的元素都轉換成新元素相同的類型，再将轉換後的元素存儲到正确的位置上，并從小到大排列
• 将新元素添加到底層數組中

因為每次向整數集合中添加新的元素都有可能發生升級，而每次升級都需要對底層數組中的元素進行類型轉換。所以，整數集合添加新元素需要升級的時間複雜度為O(n) 。

3.2 升級的好處

• 提升整數集合的靈活性

因為，C語言是靜态類型語言，為了避免類型錯誤，不支持兩種不同數據類型的值放在同一個數據結構中。

在整數集合中，就可以将多種類型元素，存儲到同一個整數集合中。因為整數集合底層采用類型升級方案，即便你使用 int16 位、還是 32、64位的編碼方式，都可通過向上升級的方式解決類型不一緻的問題。

• 盡可能的節約内存

因為，整數集合可以同時保存三種不同類型的值。又可以确保升級操作，隻會在有需要的時候進行升級，這可以盡量節省内存。

3.3 重點回顧

• 整數集合是集合鍵的底層實現之一。
• 整數集合的底層實現為數組，這個數組以有序、無重複的方式保存集合元素，在有需要時，會對數組進行類型升級。
• 升級操作為整數集合帶來了操作上的靈活性，并盡可能的節約了内存。
• 整數集合隻支持升級操作，不支持降級操作。

四、壓縮列表

壓縮列表是Redis為了節約内存而開發的，是由一系列特殊編碼的連續内存塊組成的順序型數據結構。和數組數據結構不同的是，大小可變、類型可變。

列表鍵的底層實現之一就有鍊表，那麼，為什麼有了鍊表數據結構，還會有一個壓縮列表呢？因為，節省内存呀！

鍊表中的每個節點都需要維護指針，相當占用内存。如果列表中存儲的元素比較少，字符串也比較短，如果采用了鍊表作為底層實現，是沒有必要的。

壓縮列表最擅長的是，存儲字符串相對較短，元素個數相對較少的數據場景。畢竟，壓縮列表底層存儲的是一塊連續的内存空間，除了所存儲的元素以為，沒有任何多餘的空閑空間。

所以當列表鍵和哈希鍵隻包含少量鍵值對，并且每個鍵值對都是小整數或長度較短的字符串時，就可以采用壓縮列表來作為底層實現。

4.1 壓縮列表結構

#壓縮列表數據結構 struct ziplist { #整個壓縮列表占用的字節數 int32zlbytes; #最後一個元素距離壓縮列表起始位置的偏移量，用戶快速定位最後一個節點 int32 zlbail_offset; #元素個數 int16 zllength; #元素内容列表、依次緊湊存儲 T[] entries; #标志壓縮列表的結束，值為OxFF int8 zlend; }

一個壓縮列表可以包含任意多個節點，每個節點保存一個字節數組或一個整數值。

zlbytes 屬性記錄着整個壓縮列表，占用的内存字節數，對壓縮列表進行重分配，或計算zlend的位置時使用。

zltail 屬性記錄壓縮列表，表尾節點距離壓縮列表的起始地址有多少字節，确定表尾節點地址。

zllen 屬性記錄壓縮列表，包含節點的數量，當這個屬性值小于UINT16_MAX(65535)時可信，否則需要遍曆整個壓縮列表獲得最新的長度。

entryX 屬性是壓縮列表，包含的各個節點，節點的長度由節點保存的内容決定。

zlend 屬性特殊值0xff(十進制255) 用于标記壓縮列表的末端。

4.2 壓縮列表-節點

每個壓縮列表節點都包含以下三個部分：

struct entry { # 前一個entry的字節長度 int prevlen; # 元素類型編碼 int encoding; #元素内容 optional byte[] content; }

1、previous_entry_length

previous_entry_length 屬性以字節為單位，記錄了壓縮列表中前一個節點的長度。

previous_entry_length 的屬性值的長度可以是 1 字節 也可以是 5 字節。

如果前一個節點的長度小于 254 則 length 的屬性值是 1 個字節。

如果前一個節點的長度大于 254 則 length 的屬性值是 5 個字節。

2、encoding

encoding 屬性記錄了節點的 content 屬性所保存數據的類型長度。

一個字節、兩個字節或五個字節的最高位是 00、01、10 的字節數組編碼。它意味着content 屬性保存着字節數組。數組的長度由編碼除去最高兩位之後的其他位記錄。

一字節長，值的最高位是 11 開頭的是整數編碼，此編碼表示節點 content 屬性保存着整數值。整數值的類型和長度由編碼除去最高兩位之後的其他位記錄。

3、content

content 屬性保存着節點的值，類型和長度由 encoding 和 length 決定，可以是一個字節數組或整數。

4.3 區分節點 數組、整數

壓縮列表中，所包含的多個節點，可以是一個長度受限的字符串數組（非結尾的字符串數組）也可以是一個整數。那怎麼區分這個節點存儲的是數組還是整數呢？

字符數組可以是以下三種長度的其中一種

• 長度小于等于 63 字節的字符數組
• 長度小于等于 16383 字節的字符數組
• 長度小于等于 4294967295 字節的字符數組

整數值則是以下六種長度的其中一種

• 4 位長，介于 0 至 12 之間的無符号整數
• 1 字節長，有符合整數
• 3 字節長，有符合整數
• int16_t 類型整數
• int32_t 類型整數
• int64_t 類型整數

4.4 倒序遍曆

因為每個壓縮列表的節點中都存儲着一個 previous_entry_length 屬性。所以程序可以通過指針進行運算，根據當前節點的起始位置來計算出前一個節點的起始地址。

當前節點的地址-previous_entry_length=前一個節點起始地址

所以壓縮列表的為了支持雙向遍曆，通過 ztail_offset 這個字段來找到最後一個節點的地址，在通過上面的公式找到前一個節點地址，以此方法來進行倒序遍曆。

4.5、級聯更新

每個節點都有一個 previous_entry_length 屬性，它以字節為單位，并且是變長的，以253為臨界點，大于253用 5 個字節表示，小于或等于 則用 1 個字節表示。如果由 253 變成了 254 則會發生級聯更新。

如果每個節點都恰好存儲了253個字節内容，那麼修改第一個節點内容仍舊會導緻後續的節點發生級聯更新，

删除中間節點也會發生級聯更新

4.6 重點回顧

• 壓縮類别是為了節省内存而開發的順序型數據結構
• 列表鍵和哈希鍵的底層實現之一就是壓縮列表
• 一個壓縮列表中包含了多個節點，每個節點可以保存一個字節數組或者整數值
• 添加新節點到壓縮列表，或從中删除節點會引發級聯更新，但是概率比較小

五、參考文獻

《Redis 設計與實現》

《Redis 深度曆險》