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

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

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

1、整數(shù)集合

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

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

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

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

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

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

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

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

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

2、升級(jí)

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

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

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

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

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

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

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

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

3、升級(jí)的好處

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

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

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

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

4、降級(jí)

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

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

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

最新評(píng)論