Redis數(shù)據(jù)結(jié)構(gòu)intset

整數(shù)集（intset）是集合鍵的底層實現(xiàn)之一，當(dāng)一個集合只包含整數(shù)值元素，并且這個集合的元素數(shù)量不多時，Redis 就會使用整數(shù)集合作為集合鍵的底層實現(xiàn)。

整數(shù)集合可以保存類型為 int16_t，int32_t，int64_t 的整數(shù)值，并且保證集合中不會出現(xiàn)重復(fù)元素。

1、整數(shù)集合

以下是整數(shù)集合的結(jié)構(gòu)：

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

其中，encoding 屬性的值為 INTSET_ENC_INT16，INTSET_ENC_INT32，INTSET_ENC_INT64，分別表示 contents 數(shù)組里存儲的整數(shù)類型是 int16_t，int32_t，int64_t。

當(dāng) encoding 的值為 INTSET_ENC_INT16，contents 數(shù)組里每個項都是 int16_t 類型的整數(shù)值，范圍在 -215 ～ 2 15 - 1 之間，也就是 -32768 ～ 32767

當(dāng) encoding 的值為 INTSET_ENC_INT32，contents 數(shù)組里每個項都是 int32_t 類型的整數(shù)值，范圍在 -231 ～ 2 31 - 1 之間

當(dāng) encoding 的值為 INTSET_ENC_INT64，contents 數(shù)組里每個項都是 int64_t 類型的整數(shù)值，范圍在 -263 ～ 2 63 - 1 之間

length 屬性記錄的是整數(shù)集合中包含的元素數(shù)量，也就是 contents 數(shù)組的長度。

contents 數(shù)組中的數(shù)值按值的大小從小到大有序排列，并且不包含重復(fù)項。

contents 數(shù)組中包含的元素類型都是一樣的，比如當(dāng)前數(shù)組中元素的類型是 int16_t，如果要向其中插入的整數(shù)值的類型是 int32_t，那么 contents 數(shù)組就要將 contents 數(shù)組的元素類型先升級再插入，這個就涉及升級的操作。

2、升級

當(dāng)我們要添加到整數(shù)集合中的元素的類型比現(xiàn)有所有元素類型都要長時，整數(shù)集合需要進(jìn)行升級（upgrade）操作，然后才能將新元素插入整數(shù)集合中。

升級并添加新元素共分為三步進(jìn)行：

• 根據(jù)新元素類型，擴(kuò)展整數(shù)集合底層數(shù)組的空間大小，并為新元素分配空間
• 將底層數(shù)組所有元素轉(zhuǎn)換成與新元素相同的類型，并將類型轉(zhuǎn)換后的元素放在正確的位上，且維持其有序性不變
• 將新元素添加到底層數(shù)組里面

對于整數(shù)的三種類型，int16_t，int32_t，int64_t，每種類型的數(shù)據(jù)占用的位數(shù)分別是 16，32，64

假設(shè)當(dāng)前 contents 數(shù)組有三個元素：1，2，3。類型是 int16_t，對應(yīng)的元素和位數(shù)展示如下：

接下來需要添加一個整數(shù)，65535，類型是 int32_t，那么就需要先分配額外的空間，新分配的空間長度等于元素總數(shù) 新類型的位數(shù) - 原有空間長度 = 4 32 - 48 = 80：

然后分別將元素 3，2，1 移動到對應(yīng)的空間內(nèi)，再將新元素 65535 放在對應(yīng)的空間上：

然后將整數(shù)集合 encoding 屬性的值從 INTSET_ENC_INT16 改為 INTSET_ENC_INT32，length 屬性的值從 3 改為 4。

3、升級的好處

為整數(shù)集合使用升級策略有兩個好處，一個是提升整數(shù)集合的靈活性，一個是盡可能的節(jié)約內(nèi)存

因為 C語言是靜態(tài)類型語言，通常不會將兩種不同類型的值放在一個數(shù)據(jù)結(jié)構(gòu)里，但是整數(shù)集合可以通過自動升級底層數(shù)組來適應(yīng)新元素，所以我們可以隨意將 int16_t，int32_t，int64_t 類型的整數(shù)添加到集合中，而不必?fù)?dān)心出現(xiàn)類型錯誤

另外，要讓數(shù)組可以同時保存 int16_t，int32_t，int64_t 這三種類型的整數(shù)，最簡單的方式是直接使用 int64_t 類型的數(shù)組去保存數(shù)據(jù)，但這樣的話如果元素都是 int16_t，int32_t 類型的值，那么會出現(xiàn)浪費內(nèi)存的情況。

因此現(xiàn)在升級策略可以盡量節(jié)約內(nèi)存。

4、降級

整數(shù)集合不支持降低操作，一旦對數(shù)組進(jìn)行了升級，編碼就會一直保持升級后的狀態(tài)。

比如前面的數(shù)組 1，2，3，65535，如果我們刪除了 65535，整數(shù)集合還是會維持原有 INTSET_ENC_INT64 的編碼，底層數(shù)組也還是 int64_t 類型的。

以上就是Redis數(shù)據(jù)結(jié)構(gòu)之intset整數(shù)集合使用學(xué)習(xí)的詳細(xì)內(nèi)容，更多關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)intset的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論