0.前言
上個(gè)篇章回顧，我們上個(gè)章節(jié)我們學(xué)習(xí)了《Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)字典(Dictionary)詳解》，我們從源碼層了解字典是一種以鍵值對(duì)（key-value）形式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。在 Redis 中，字典使用哈希表來(lái)實(shí)現(xiàn)。哈希表是一種以常數(shù)時(shí)間復(fù)雜度 O(1) 進(jìn)行插入、刪除和查找的數(shù)據(jù)結(jié)構(gòu)。了解到在 Redis 中，字典被廣泛應(yīng)用于實(shí)現(xiàn)哈希表和集合等數(shù)據(jù)結(jié)構(gòu)。
本章節(jié)，我們?cè)敿?xì)了解一下在Redis又一個(gè)底層數(shù)據(jù)結(jié)構(gòu)整數(shù)集（IntSet），它是用于存儲(chǔ)整型數(shù)據(jù)，是一種緊湊的、高效的數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)實(shí)現(xiàn)集合等功能。
當(dāng)一個(gè)集合只包含整數(shù)值元素，并且這個(gè)集合的元素?cái)?shù)量不多時(shí)，Redis 就會(huì)使用整數(shù)集合作為集合鍵的底層實(shí)現(xiàn)。
1.IntSet基本詳解
整數(shù)集的實(shí)現(xiàn)方式與普通的數(shù)組和鏈表不同，它采用了一種特殊的壓縮算法，可以在盡可能少的內(nèi)存空間中存儲(chǔ)大量的整型數(shù)據(jù)。在Redis中，整數(shù)集通常用來(lái)存儲(chǔ)集合中的元素，例如有序集合中的分值。
整數(shù)集的結(jié)構(gòu)示意如下所示：
+--------+--------+--------+--------+--------+--------+
| header | data | data | data | data | data |
+--------+--------+--------+--------+--------+--------+
整數(shù)集由一個(gè)頭部和多個(gè)數(shù)據(jù)塊組成。頭部中存儲(chǔ)了整數(shù)集的元素個(gè)數(shù)、編碼方式和數(shù)據(jù)塊的起始地址等信息。數(shù)據(jù)塊中存儲(chǔ)了實(shí)際的整型數(shù)據(jù)。
IntSet的設(shè)計(jì)目標(biāo)是盡可能地節(jié)省內(nèi)存空間，同時(shí)保證高效的操作性能。它可以存儲(chǔ)三種類型的整數(shù)：8位整數(shù)、16位整數(shù)和32位整數(shù)。IntSet的內(nèi)部結(jié)構(gòu)示意如下圖所示：
| 32位無(wú)符號(hào)整數(shù) | 16位無(wú)符號(hào)整數(shù) | 8位無(wú)符號(hào)整數(shù) | 8位標(biāo)志位 |
IntSet由一個(gè)數(shù)組和一個(gè)標(biāo)志位組成。數(shù)組中按照從小到大的順序存儲(chǔ)了所有整數(shù)值，標(biāo)志位用于記錄數(shù)組中存儲(chǔ)的整數(shù)類型（即8位整數(shù)、16位整數(shù)還是32位整數(shù)）。如果標(biāo)志位為0，則表示數(shù)組中存儲(chǔ)的都是8位整數(shù)；如果標(biāo)志位為1，則表示數(shù)組中存儲(chǔ)的都是16位整數(shù)；如果標(biāo)志位為2，則表示數(shù)組中存儲(chǔ)的都是32位整數(shù)。
在IntSet中，每個(gè)整數(shù)值只會(huì)出現(xiàn)一次，重復(fù)的整數(shù)會(huì)被自動(dòng)去重。在插入新的整數(shù)值時(shí)，IntSet會(huì)自動(dòng)根據(jù)當(dāng)前數(shù)組中存儲(chǔ)的整數(shù)類型進(jìn)行擴(kuò)容，以保證能夠存儲(chǔ)新的整數(shù)值。
IntSet支持的操作包括插入、刪除、查找、遍歷等。具體來(lái)說(shuō)，插入和刪除操作的時(shí)間復(fù)雜度均為O(1)；查找操作的時(shí)間復(fù)雜度為O(N)，其中N為IntSet中存儲(chǔ)的整數(shù)數(shù)量；遍歷操作的時(shí)間復(fù)雜度為O(N)。
在Redis6中，IntSet進(jìn)行了一些優(yōu)化。具體來(lái)說(shuō)，Redis6中的IntSet支持了快速的非對(duì)稱迭代操作，這意味著可以在不需要完全遍歷整個(gè)IntSet的情況下，快速地獲取滿足特定條件的整數(shù)值。此外，Redis6中的IntSet還支持了壓縮操作，可以通過(guò)壓縮來(lái)減少IntSet占用的內(nèi)存空間。
在使用Redis時(shí)需要存儲(chǔ)大量的整數(shù)值，可以考慮使用IntSet來(lái)優(yōu)化存儲(chǔ)空間和操作性能。在Redis6中，IntSet還支持了更多的優(yōu)化和功能，可以更好地滿足實(shí)際需求。
首先我們了解一下整數(shù)集的編碼方式有三種：
-
INTSET_ENC_INT16：表示整數(shù)集中的元素都是16位的整數(shù)。
-
INTSET_ENC_INT32：表示整數(shù)集中的元素都是32位的整數(shù)。
-
INTSET_ENC_INT64：表示整數(shù)集中的元素都是64位的整數(shù)。
整數(shù)集的編碼方式是根據(jù)元素的大小來(lái)自動(dòng)選擇的。如果所有元素都可以放在16位或32位中，就選擇相應(yīng)的編碼方式；否則，就選擇64位編碼方式。
整數(shù)集的壓縮算法是在保證元素按照升序排列的前提下，盡量壓縮每個(gè)元素的存儲(chǔ)空間。具體來(lái)說(shuō)，整數(shù)集會(huì)對(duì)連續(xù)的整型數(shù)據(jù)進(jìn)行壓縮，只存儲(chǔ)它們的起始值和步長(zhǎng)，而不是每個(gè)元素的實(shí)際值。這種算法可以在盡可能少的內(nèi)存空間中存儲(chǔ)大量的整型數(shù)據(jù)，提高了內(nèi)存的利用率。
先不看源碼，我們先看八股文。
1.1 整數(shù)集的壓縮算法原理
整數(shù)集（IntSet）的壓縮算法是一種特殊的算法，可以在盡可能少的內(nèi)存空間中存儲(chǔ)大量的整型數(shù)據(jù)。整數(shù)集的壓縮算法基于以下兩個(gè)原則：
-
整數(shù)集中的元素按照升序排列。
-
對(duì)于連續(xù)的整型數(shù)據(jù)，只存儲(chǔ)它們的起始值和步長(zhǎng)，而不是每個(gè)元素的實(shí)際值。
具體來(lái)說(shuō)，整數(shù)集會(huì)根據(jù)元素的大小選擇合適的編碼方式（INTSET_ENC_INT16、INTSET_ENC_INT32或INTSET_ENC_INT64），然后將整數(shù)集中的元素按照升序排列。對(duì)于連續(xù)的整型數(shù)據(jù)，整數(shù)集會(huì)計(jì)算它們的起始值和步長(zhǎng)，并將它們存儲(chǔ)在數(shù)據(jù)塊中。例如，假設(shè)整數(shù)集中有以下元素：1、2、3、4、5、10、11、12、13、14，整數(shù)集的數(shù)據(jù)塊可以存儲(chǔ)以下內(nèi)容：
+--------+--------+--------+--------+--------+--------+--------+--------+
| 1 | 1 | 4 | 10 | 1 | 5 | 2 | 4 |
+--------+--------+--------+--------+--------+--------+--------+--------+
在上面的數(shù)據(jù)塊中，第一個(gè)元素1表示整數(shù)集的編碼方式（INTSET_ENC_INT16），第二個(gè)元素1表示整數(shù)集中有6個(gè)元素，后面的數(shù)據(jù)塊中，每?jī)蓚€(gè)元素表示一個(gè)連續(xù)的整型數(shù)據(jù)的起始值和步長(zhǎng)。例如，第三個(gè)元素4表示整數(shù)集中有4個(gè)連續(xù)的整數(shù)（4、5、6、7），第四個(gè)元素10表示這些整數(shù)的起始值，第五個(gè)元素1表示這些整數(shù)的步長(zhǎng)。
整數(shù)集的壓縮算法可以在盡可能少的內(nèi)存空間中存儲(chǔ)大量的整型數(shù)據(jù)，提高了內(nèi)存的利用率。在實(shí)際的Redis應(yīng)用中，整數(shù)集被廣泛應(yīng)用于集合等數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。通過(guò)使用整數(shù)集，Redis可以在保證高效的操作性能的同時(shí)，減少內(nèi)存的浪費(fèi)，提高內(nèi)存利用率。
1.2 整數(shù)集編碼方式選擇原理
雖然在Redis中，整數(shù)集（IntSet）的編碼方式是根據(jù)元素的大小來(lái)自動(dòng)選擇的。整數(shù)集的編碼方式有三種：INTSET_ENC_INT16、INTSET_ENC_INT32和INTSET_ENC_INT64，分別表示整數(shù)集中的元素都是16位、32位和64位的整數(shù)。
1.2.1 判斷邏輯
當(dāng)向整數(shù)集中添加元素時(shí)，Redis會(huì)根據(jù)新元素的大小和整數(shù)集中已有元素的大小，自動(dòng)選擇合適的編碼方式。具體來(lái)說(shuō)，如果新元素的大小可以放在整數(shù)集的當(dāng)前編碼方式中，就直接將新元素添加到整數(shù)集中；否則，Redis會(huì)根據(jù)新元素的大小和已有元素的大小，選擇一個(gè)更大的編碼方式，并將整數(shù)集中的所有元素轉(zhuǎn)換為新的編碼方式，然后再將新元素添加到整數(shù)集中。
1.2.2 舉例說(shuō)明
例如，假設(shè)整數(shù)集中已有32位整數(shù)，此時(shí)向整數(shù)集中添加一個(gè)16位整數(shù)。由于16位整數(shù)可以放在32位整數(shù)中，因此Redis會(huì)直接將新元素添加到整數(shù)集中，不需要進(jìn)行編碼方式的轉(zhuǎn)換。但是，如果向上面的整數(shù)集中添加一個(gè)64位整數(shù)，由于64位整數(shù)無(wú)法放在32位整數(shù)中，Redis會(huì)選擇64位編碼方式，并將整數(shù)集中的所有元素轉(zhuǎn)換為64位編碼方式，然后再將新元素添加到整數(shù)集中。
整數(shù)集的自動(dòng)編碼方式選擇可以在保證高效性能的同時(shí)，減少內(nèi)存的浪費(fèi)，提高內(nèi)存利用率。在實(shí)際的Redis應(yīng)用中，整數(shù)集被廣泛應(yīng)用于集合等數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。通過(guò)使用整數(shù)集，Redis可以在保證高效的操作性能的同時(shí)，減少內(nèi)存的浪費(fèi)，提高內(nèi)存利用率。
2. 源碼解析
說(shuō)了在多理論的概念和舉例都略顯單薄，很多同學(xué)可能在想"talk is cheap, show me code"。那么接下來(lái)我們進(jìn)行一下源碼解讀。
在Redis的GitHub倉(cāng)庫(kù)中，IntSet的代碼文件位于以下路徑：intset.h：https://github.com/redis/redis/blob/6.0/src/intset.hintset.c：https://github.com/redis/redis/blob/6.0/src/intset.c
6.0分支是Redis6的分支，包含了最新的代碼修改和功能更新。所以如果有同學(xué)想詳細(xì)的了解一下，也可以在該分支下找到最新的IntSet代碼文件，如果對(duì)Redis7的源碼也想了解，只需要在上面切換一下分支即可。參考代碼實(shí)現(xiàn)來(lái)深入了解IntSet的數(shù)據(jù)結(jié)構(gòu)和操作還是很簡(jiǎn)單的。其實(shí)相比較前幾個(gè)章節(jié)學(xué)習(xí)的底層數(shù)據(jù)結(jié)構(gòu)，intset 不算復(fù)雜的。
注：如果你對(duì)C也算是了解的話，可能下面的內(nèi)容就不必再看了，點(diǎn)擊我上面的源碼地址，掃一遍這兩個(gè)文件基本上就一目了然。如果你是C小白，請(qǐng)繼續(xù)。
上面截圖中
intset.h：IntSet的頭文件，定義了IntSet的結(jié)構(gòu)體類型和相關(guān)函數(shù)的聲明。intset.c：IntSet源文件，實(shí)現(xiàn)了IntSet的各種操作函數(shù)，包括創(chuàng)建、添加、刪除、查找和升級(jí)等操作函數(shù)。
從上面的源碼截圖我們可以看出來(lái)IntSet的定義如下：
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
IntSet是一個(gè)結(jié)構(gòu)體類型，其中包含三個(gè)成員變量：
- encoding：表示IntSet所使用的編碼格式，可以是8位整數(shù)、16位整數(shù)或32位整數(shù)。
- length：表示IntSet中存儲(chǔ)的整數(shù)數(shù)量。
- contents：表示IntSet中存儲(chǔ)的整數(shù)值的數(shù)組，是一個(gè)靈活數(shù)組成員（flexible array member）。
接下來(lái)，我們來(lái)看一下IntSet的基本操作函數(shù)。
2.1. intsetNew
intsetNew函數(shù)用于創(chuàng)建一個(gè)新的IntSet結(jié)構(gòu)體，并返回該結(jié)構(gòu)體的指針。函數(shù)定義如下：
intset *intsetNew(void) {
intset *is = zmalloc(sizeof(intset));
is->encoding = INTSET_ENC_INT16;
is->length = 0;
return is;
}
在該函數(shù)中，使用zmalloc函數(shù)動(dòng)態(tài)分配了一段大小為sizeof(intset)的內(nèi)存空間，并將其初始化為0。然后將該內(nèi)存空間強(qiáng)制轉(zhuǎn)換為intset類型，并將encoding設(shè)置為INTSET_ENC_INT16，表示使用16位整數(shù)編碼方式。最后返回該IntSet結(jié)構(gòu)體的指針。
2.2. intsetAdd
intsetAdd函數(shù)用于向IntSet中添加一個(gè)整數(shù)值，函數(shù)定義如下：
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t valenc = _intsetValueEncoding(value);
if (valenc > is->encoding) {
return intsetUpgradeAndAdd(is,value,success);
}
......
}
在intsetAdd中首先調(diào)用_intsetValueEncoding函數(shù)判斷value的編碼方式，并將其賦值給valenc。然后判斷valenc是否大于當(dāng)前IntSet的編碼方式，如果是，則調(diào)用intsetUpgradeAndAdd函數(shù)進(jìn)行升級(jí)操作。否則，繼續(xù)執(zhí)行后面的操作。
接下來(lái)，根據(jù)valenc的值，將value插入到IntSet中。具體來(lái)說(shuō)，如果valenc等于8，則將value轉(zhuǎn)換為8位整數(shù)，并插入到IntSet的數(shù)組中；如果valenc等于16，則將value轉(zhuǎn)換為16位整數(shù)，并插入到IntSet的數(shù)組中；如果valenc等于32，則將value轉(zhuǎn)換為32位整數(shù)，并插入到IntSet的數(shù)組中。插入操作完成后，將success設(shè)置為1，表示插入成功。
2.3. intsetRemove
intsetRemove函數(shù)用于從IntSet中刪除一個(gè)整數(shù)值，函數(shù)定義如下：
int intsetRemove(intset *is, int64_t value, int *success) {
uint8_t valenc = _intsetValueEncoding(value);
uint8_t *p;
uint64_t u64;
int32_t i32;
int16_t i16;
uint8_t i8;
if (valenc <= is->encoding) {
......
}
*success = 0;
return 0;
}
在該函數(shù)中，首先調(diào)用_intsetValueEncoding函數(shù)判斷value的編碼方式，并將其賦值給valenc。然后判斷valenc是否小于等于當(dāng)前IntSet的編碼方式，如果是，則繼續(xù)執(zhí)行后面的操作。否則，直接返回0，表示刪除失敗。
接下來(lái)，根據(jù)valenc的值，在IntSet的數(shù)組中查找value，并將其刪除。具體來(lái)說(shuō)，如果valenc等于8，則將value轉(zhuǎn)換為8位整數(shù)，并在數(shù)組中查找并刪除；如果valenc等于16，則將value轉(zhuǎn)換為16位整數(shù)，并在數(shù)組中查找并刪除；如果valenc等于32，則將value轉(zhuǎn)換為32位整數(shù)，并在數(shù)組中查找并刪除。刪除操作完成后，將success設(shè)置為1，表示刪除成功。
2.4. intsetFind
intsetFind函數(shù)用于在IntSet中查找一個(gè)整數(shù)值，函數(shù)定義如下：
uint8_t intsetFind(intset *is, int64_t value) {
uint8_t valenc = _intsetValueEncoding(value);
if (valenc <= is->encoding) {
......
}
return 0;
}
在該函數(shù)中，首先調(diào)用_intsetValueEncoding函數(shù)判斷value的編碼方式，并將其賦值給valenc。然后判斷valenc是否小于等于當(dāng)前IntSet的編碼方式，如果是，則繼續(xù)執(zhí)行后面的操作。否則，直接返回0，表示查找失敗。
接下來(lái)，根據(jù)valenc的值，在IntSet的數(shù)組中查找value。具體來(lái)說(shuō)，如果valenc等于8，則將value轉(zhuǎn)換為8位整數(shù)，并在數(shù)組中查找；如果valenc等于16，則將value轉(zhuǎn)換為16位整數(shù)，并在數(shù)組中查找；如果valenc等于32，則將value轉(zhuǎn)換為32位整數(shù)，并在數(shù)組中查找。如果在數(shù)組中找到了value，則返回1，表示查找成功；否則返回0，表示查找失敗。
2.5. intsetUpgradeAndAdd
intsetUpgradeAndAdd函數(shù)用于將IntSet的編碼方式升級(jí)，并向IntSet中添加一個(gè)整數(shù)值，函數(shù)定義如下：
/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t curenc = is->encoding;
uint8_t newenc = _intsetValueEncoding(value);
int length = is->length;
int prepend = value < 0 ? 1 : 0;
is->encoding = newenc;
while(length--) {
int64_t v;
_intsetGet(is,length,&v);
intsetRemove(is,v,NULL);
intsetAdd(is,v,success);
}
*success = intsetAdd(is,value,success);
return is;
}
在該函數(shù)中，首先獲取當(dāng)前IntSet的編碼方式curenc、新的整數(shù)值value的編碼方式newenc和IntSet的長(zhǎng)度length。然后根據(jù)value的正負(fù)性，判斷是否需要在數(shù)組的開(kāi)頭添加新的整數(shù)值。
接下來(lái)，將IntSet的編碼方式設(shè)置為newenc，并遍歷IntSet中的每個(gè)整數(shù)值。對(duì)于每個(gè)整數(shù)值，先在IntSet中刪除，然后重新添加到IntSet中，這樣可以將所有整數(shù)值的編碼方式都升級(jí)到newenc。
最后，向IntSet中添加新的整數(shù)值value，并將success設(shè)置為1，表示添加成功。
2.6 收獲
通過(guò)掃一遍源碼我們基本上可以了解到IntSet提供了多種操作函數(shù)，包括添加整數(shù)、刪除整數(shù)、查找整數(shù)、升級(jí)整數(shù)集合的操作等。了解到這些操作函數(shù)的實(shí)現(xiàn)原理，包括如何進(jìn)行二分查找、如何調(diào)整整數(shù)集合的大小等。它可以在O(log N)的時(shí)間復(fù)雜度內(nèi)完成查找、添加、刪除操作等。如何利用連續(xù)內(nèi)存和二分查找來(lái)提高性能等。
3.總結(jié)
在實(shí)際的Redis應(yīng)用中，整數(shù)集被廣泛應(yīng)用于集合等數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。通過(guò)使用整數(shù)集，Redis可以在保證高效的操作性能的同時(shí)，減少內(nèi)存的浪費(fèi)，提高內(nèi)存利用率?？梢杂糜诖鎯?chǔ)大量的整數(shù)值，并支持快速的插入、刪除和查找操作。如果您需要存儲(chǔ)大量的整數(shù)值，可以考慮使用IntSet來(lái)優(yōu)化存儲(chǔ)空間和操作性能。
4.思考題
應(yīng)一位網(wǎng)友的建議，在每個(gè)章節(jié)后面留個(gè)思考題，供大家繼續(xù)學(xué)習(xí)。下次分享來(lái)揭曉答案。本次的思考題只有一道。1. Redis6是如何使用IntSet來(lái)實(shí)現(xiàn)集合和有序集合？文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-489195.html
5. Redis從入門到精通系列文章
《Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)字典(Dictionary)詳解》
《Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)快表QuickList詳解》
《Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單動(dòng)態(tài)字符串(SDS)詳解》
《Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)壓縮列表(ZipList)詳解》
《Redis從入門到精通【進(jìn)階篇】之?dāng)?shù)據(jù)類型Stream詳解和使用示例》
大家好，我是冰點(diǎn)，今天的Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)整數(shù)集(IntSet)詳解，全部?jī)?nèi)容就是這些。如果你有疑問(wèn)或見(jiàn)解可以在評(píng)論區(qū)留言。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-489195.html
到了這里，關(guān)于Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)整數(shù)集(IntSet)詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
