redis 系列8 數據結構之整數集合

一.概述

　　整數集合(intset)是集合鍵的底層實現之一, 當一個集合只包含整數值元素，並且這個集合元素數量不多時, Redis就會使用整數集合作為集合鍵的底層實現。下麵創建一個只包含5個元素的集合鍵，並且集合中所有元素都是整數值，那麼這個集合鍵的底層實現就會是整數集合。 接著添加非整數值，集合鍵的底層實現就會是hashtable。

127.0.0.1:6379> sadd numbers 1 3 5 7 9 
(integer) 5
127.0.0.1:6379> object encoding numbers
"intset"
127.0.0.1:6379> sadd numbers 'one'
(integer) 1
127.0.0.1:6379> object encoding numbers
"hashtable"

二. 整數集合實現

　　整數集合是Redis用於保存整數值的集合抽象數據結構，它可以保存類型為int16_t, int32_t, int64_t的整數值，並且保證集合中不會出現重覆元素。數據集合定義如下：

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

　　(1) contents數組是整數集合的底層實現,整數集合的每個元素都是contents數組的一個數組項(item),各個項在數組中按值從小到大有序排列,並且數組中不包含重覆項。如下麵腳本：

127.0.0.1:6379> sadd record 5 3 4 5 6 0
(integer) 5
127.0.0.1:6379> smembers record
1) "0"
2) "3"
3) "4"
4) "5"
5) "6"

　　(2) length屬性記錄了整數集合包含的元素數量,也即是contents數組的長度。雖然contents屬性聲明為int8_t類型的數組,但實現上contents數組並不保存任何int8_t類型的值，contents數組的真正類型取決於encoding屬性的值。

　　a. 如果encoding 屬性的值為intset_enc_int16，那麼contents就是一個int16_t類型的數組，數組裡的每個項都是一個int16_t類型的整數值(範圍在 -32768 ~ 32767)。如下圖encoding屬性的值有5個整數型，根據這些整數值得出encoding為int16_t類型。

　　b. 如果encoding屬性的值為intset_enc_int32, 那麼數組裡每個項就是一個int32_t類型的整數值(範圍在 -2147483648 ~ 2147483647)。還有encoding屬性的值為intset_enc_int64類型的，數組裡每個項取取值範圍更大。

　　需要註意的是：假設contents數組保存的值為2147483647, 1,2,3 四個整數值。 但只有第一個整數值需要用int32_t類型來保存，而其它三個值可以用int16_t類型來保存。不過根據整數集合的升級規則，當一個底層的int16_t數組的整數集合添加一個int64_t類型的整數值時，整數集合中所有元素都會被轉換成int64_t類型。 所以contents數組保存的整數值都是int64_t類型的。

三. 升級

 　　當我們要將一個新元素添加到整數集合裡面，並且新元素的類型比整數集合現有所有元素的類型都要長時，整數集合需要先進行升級,然後才能將新元素添加到整數集合中。假設：集合中包含三個int16_t類型的元素，值分別是1,2,3 。因為每個元素都占用16位空間，所以整數集合底層數組的大小 為3 * 16 =48位。現將int32_t的數值65535添加進去，這裡程式需要對整數集合進行升級。

　　升級整數集合併添加新元素共分三步進行：

　　　　(1) 根據新元素的類型，擴展整數集合底層數組的空間大小 ，併為新元素分配空間。分配空間後，現在整數集合4個元素的底層數組大小為4 *32 =128位, 此時前三位還是48位空間，如下圖所示：

　　　　(2) 將底層數組現有的所有元素都轉換成與新元素相同的類型(需要從int16_t 轉成int32_t所需的空間) ，轉換後元素位置有序不變,如下圖所示：

　　　　(3) 將新元素添加到底層數組裡面,如下圖所示：

四. 升級的好處

　　4.1 提升靈活性

　　　　為了避免類型錯誤，通常不會將兩種不同類型的值放在同一個數據結構裡面，通過升級處理可以隨意地將int16_t, int32_t, , int64_t 類型的整數添加到集合中，而不必擔心出現類型錯誤。

       4.2 節約記憶體

　　　　要讓一個數組可以同時保存int16_t,int32_t, , int64_t三種類型的值，最簡單的做法就是直接使用int64_t類型的數組作為整數集合的底層實現，不過這樣浪費記憶體空間。

五.   降級

　　整數集合不支持降級操作，一旦對數組進行了升級，編碼就會一直保持升級後的狀態。即使集合里只有一個需要使用int64_t類型的元素被刪除了，整數集合的編碼仍然會維持intset_enc_int64, 底層數組也仍然會是int64_t類型,如下圖所示：

六. 整數集合API