Redis 的底層數據結構（整數集合）

• 2019 年 10 月 20 日
• 筆記

當一個集合中只包含整數，並且元素的個數不是很多的話，redis 會用整數集合作為底層存儲，它的一個優點就是可以節省很多內存，雖然字典結構的效率很高，但是它的實現結構相對複雜並且會分配較多的內存空間。

而我們的整數集合（intset）可以做到使用較少的內存空間卻達到和字典一樣效率的實現，但也是前提的，集合中只能包含整型數據並且數量不能太多。整數集合最多能存多少個元素在 redis 中也是有體現的。

OBJ_SET_MAX_INTSET_ENTRIES 512

也就是超過 512 個元素，或者向集合中添加了字符串或其他數據結構，redis 會將整數集合向字典結構進行轉換。

一、基本的數據結構

intset 的結構定義很簡單，有以下成員構成：

typedef struct intset {      uint32_t encoding;      uint32_t length;      int8_t contents [];  } intset;

encoding 記錄當前 intset 使用編碼，有三個取值：

#define INTSET_ENC_INT16 (sizeof(int16_t))  #define INTSET_ENC_INT32 (sizeof(int32_t))  #define INTSET_ENC_INT64 (sizeof(int64_t))

length 記錄整數集合中目前存儲了多少個元素，contents 記錄我們實際的數據集合，雖然我們看到結構體中給數組元素的類型定死成 int8_t，但實際上這個 int8_t 定義的毫無意義，因為這裡的處理方式非常規的數組操作，content 字段雖然被定義成指向一個 int8_t 類型數據的指針，但實際上 redis 無論是讀取數組元素還是新增元素進去都依賴 encoding 和 length 兩個字段直接操作的內存。

基本數據結構還是非常的簡單的，下面我們來看看它的一些核心方法。

二、核心 API 實現

1、初始化一個 intset

intset *intsetNew(void) {      intset *is = zmalloc(sizeof(intset));      is->encoding = intrev32ifbe(INTSET_ENC_INT16);      is->length = 0;      return is;  }

可見，默認的 inset 配置是使用 INTSET_ENC_INT16 作為數據存儲大小，並且不會為 content 數組初始化。常規的數組需要先預先確定數組長度，然後分配內存，繼而通過 contents[x] 可以訪問數組中任一元素。

但是，inset 這裡是非常規式操作數組，encoding 字段定義了數組中每個元素實際類型，lenth 字段定義了數組中實際的元素個數，那麼 contents[x] 是失效的，這種方式只會按照 int8_t 進行內存偏移，這種方式是拿不到正確的數據的，所以 redis 中通過 memcpy 按照 encoding 字段的值暴力直接偏移地址操作內存讀取數據。

所以，這也是為什麼 intset 初始化時不初始化 content 數組的原因所在，因為沒有必要。而每當新增一個元素的時候都會去動態擴容原數組的長度以盛放下新插入進來的元素，擴容不會擴容很多，剛好一個新元素所佔用的內存即可。具體的細節，我們接着看。

2、添加新元素

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {      //計算得到新插入的元素的編碼      uint8_t valenc = _intsetValueEncoding(value);      uint32_t pos;      if (success) *success = 1;      //如果大於 intset 目前存儲元素的編碼大小      if (valenc > intrev32ifbe(is->encoding)) {          //觸發 intset 升級          return intsetUpgradeAndAdd(is,value);      } else {          //二分搜索當前元素，如果元素已經存在會直接返回          //如果沒找到元素，pos 的值就是該元素的位置索引          if (intsetSearch(is,value,&pos)) {              if (success) *success = 0;              return is;          }          //resize 集合，擴容一個元素的內存空間          is = intsetResize(is,intrev32ifbe(is->length)+1);          //移動 pos 後面的元素，以插入我們的新元素          if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);      }      //賦值      _intsetSet(is,pos,value);      is->length = intrev32ifbe(intrev32ifbe(is->length)+1);      return is;  }

由此，我們應該知道為什麼 intset 內的數據是有序且無重複的了，二分查找 O(logN)，但是 intset 插入一個元素卻不是 O(logN)，因為有些情況會觸發升級操作，或者極端情況下，會移動所有元素，時間複雜度達到 O(N)。

3、升級

我們先看示意圖的變化，然後再分析源碼，假設原 intset 使用 16 位的編碼存儲數據，先來了一個 32 位的數據，觸發了我們的編碼升級。

原 intset 結構如下：

新 intset 結構會擴容成這樣：

雖然數據佔用的內存已經分配好了，但是還需要做的是遷移每個元素佔用的比特位。
做法是這樣的，假設我們的新元素是 int_32 類型的數值 65536，那麼首先我們會將這個 65536 放到[128-159]比特位區間，然後將 78 放到[96-127]比特位區間，並向前以此類推，最後我們會得到升級完成之後 intset。

下面我們看 redis 中代碼的實現：

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {      //intset目前的編碼      uint8_t curenc = intrev32ifbe(is->encoding);      //intset即將擴展到的編碼      uint8_t newenc = _intsetValueEncoding(value);      int length = intrev32ifbe(is->length);      int prepend = value < 0 ? 1 : 0;        //根據新的元素內存大小重新分配 intset 內存大小      is->encoding = intrev32ifbe(newenc);      is = intsetResize(is,intrev32ifbe(is->length)+1);      //這個地方我先標記一下 @1，下面詳細分析      //總體上你可以理解，就是我們上圖畫的那樣，從原集合的最後一個元素      //開始擴大它佔用的比特位      while(length--)          _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));        //將新元素放進 intset 中      if (prepend)          _intsetSet(is,0,value);      else          _intsetSet(is,intrev32ifbe(is->length),value);      is->length = intrev32ifbe(intrev32ifbe(is->length)+1);      return is;  }

別的不再解釋，我重點解釋一下我做標記的 @1，這個循環其實是這個方法的核心點，它完成了將舊元素擴充比特位這麼一個操作。

首先明確的一點是，升級操作只有兩種情況會觸發，一種是新插入一個較大的數值，另一種是新插入一個負很大的值，這兩種情況都會導致類型不夠存儲，需要擴大數據位。

_intsetGetEncoded 這個方法可以根據給定了 length，也就是元素在數組中的下標取出舊數組中對應的元素，很顯然，這裡是從後往前倒着來的。

因為我們的 intsetResize 方法已經完成了擴容內存的操作，也就是說新元素的內存已經分配完畢，那麼 _intsetSet 方法就會將 _intsetGetEncoded 取出的元素重新的向數組中賦值。循環結束時，就是所有元素重新歸位的時候，最後再將新元素賦值進入數組最後的位置。

但其實細心的同學會發現，_intsetSet 方法在傳下標索引的時候實際傳的是 length+prepend，這其實就是我們說，如果 value 是小於零的，length+prepend 最終會導致所有的舊元素往後挪了一個偏移量，然後新的元素會被賦值的索引為零的位置。也就是說，如果新插入的數值是負數，它會被頭插進數組的第一個位置。

核心的幾個 API 我們都已經介紹了，其他的一些 API 你可以自行參閱源碼，相信對你不難。

總結一下，整數集合(intset)使用了非常簡潔的數據結構，可以更少的佔用內存存儲一些整數，但終究是基於數組的，也就避免不了不能存儲大量數據的缺點。總體來說，插入一個元素，最好情況 O(logN)，最壞的情況是 O(N)，攤還時間複雜度為 O(N)，查找一個元素，根據索引下標時間複雜度在 O(1)。當 intset 中的元素超過 512 個，或者向其中添加了字符串，redis 會將 intset 轉換成字典。

同樣的，如果覺得我寫的對你有點幫助的話，順手點一波關注吧，也歡迎加作者微信深入探討，我們下一講，壓縮列表，盡請關注。