Redis資料結構—整數集合與壓縮清單

大家好，我是白澤。今天我們将學習Redis的整數集合與壓縮清單這兩個資料結構，且在本文中我将盡量隻描述這兩種結構中重要的部分，而非面面俱到，因為我學Redis資料結構的初衷是為了我能更好了解後面要講到的Redis對象，而非真的去研究Redis深層的實作，不會過分深入，夠用就好

Redis對象的實作在底層用到了我們目前講解到的這些資料結構：簡單動态字元串SDS、雙端連結清單、字典、以及今天要講解的整數集合與壓縮清單，是以從底層資料結構開始能為我們了解Redis打下堅實的基礎，成為面試殺手

整數集合是Redis用于儲存整數值的集合抽象資料結構，它可以儲存int16_t、int32_t、int64_t的整數值，且保證集合中不出現重複元素

contents[]數組的類型這裡看上去是int8_t，但事實上contents[]的資料類型依靠encoding的屬性決定（encoding可以選擇為INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64表示contents[]中元素的資料類型）

typedef struct intset {
	uint32_t encoding;	//編碼方式
	uint32_t length;	//集合包含的元素的個數
	int8_t contents[];	//儲存元素的數組
} inset;

下面給出的圖檔是一個包含了五個int16_t類型整數值的整數集合，int16_t表示每個整數是由16位共2個位元組表示，是以此時contents[]數組大小為：5 * 16 = 80位

當我們向一個已經存在的整數集合中添加元素時，如果加入的元素的資料類型比contents[]數組元素的資料類型長，則整數集合需要進行更新，舉個例子，我要在上面那個大小5的16位整數集合中插入一個類型為int32_t的整數65535：

更新首先要做的是，根據新元素的長度，擴大空間，目前有5個元素，加入一個後有6個，且int16_t的元素要更新為int32_t類型（需要6 * 32 = 192位的空間），是以需要先動态配置設定記憶體空間如下：

如果因為插入一個32位的整數使得原本16位的contents[]數組轉變為32位，後面又删去了這個32位的整數，這個整數集合将不會降級成16位的contents[]數組

因為壓縮清單好像面試中不太出現，是以略講~

壓縮清單就是一塊連續的記憶體，一種順序型的資料結構，entryX是一個個節點，存放資料，其他屬性用于描述整個壓縮清單的整體情況（占用記憶體、節點個數等）

zlbytes：記錄整個壓縮清單占用的記憶體位元組數

zltail：記錄壓縮清單表尾節點距離壓縮清單的起始位址的偏移量

zllen：記錄了壓縮清單中節點數量

entryX：壓縮清單的各個節點

zlend：特殊值0xFF，用于标記壓縮清單的末端

節點就是一個個的entryX，是壓縮清單的核心，每個節點由三部分組成：

到目前為止，白澤已經帶大家初步學習了Redis底層所有的資料結構：簡單動态字元串SDS、雙端連結清單、字典、跳躍表、整數集合、壓縮清單，下一篇部落格将帶大家學習Redis的對象（Redis的對象底層就是這些資料結構實作的），再後面就正式講解Redis資料庫的知識點了，敬請期待~

繼續閱讀