redis數(shù)據(jù)結(jié)構(gòu)之intset的實例詳解
在redis中，intset主要用于保存整數(shù)值，由于其底層是使用數(shù)組來保存數(shù)據(jù)的，因而當(dāng)對集合進(jìn)行數(shù)據(jù)添加時需要對集合進(jìn)行擴(kuò)容和遷移操作，因而也只有在數(shù)據(jù)量不大時redis才使用該數(shù)據(jù)結(jié)構(gòu)來保存整數(shù)集合。其具體的底層數(shù)據(jù)結(jié)構(gòu)如下：
typedef struct intset {
// 編碼方式
uint32_t encoding;
// 集合包含的元素數(shù)量
uint32_t length;
// 保存元素的數(shù)組
int8_t contents[];
} intset;
整數(shù)集合主要有三個屬性：encoding用于保存當(dāng)前集合的編碼，有16位，32位和64位三種；length保存了當(dāng)前整數(shù)集合中保存的數(shù)據(jù)數(shù)量；contents屬性則保存了具體的數(shù)據(jù)，其每個數(shù)據(jù)占用的位數(shù)由encoding屬性指定。
這里主要需要進(jìn)行說明的是redis的intset中數(shù)據(jù)是采用從小到大的順序存儲的，因而對于數(shù)據(jù)的查詢可以采用二分法進(jìn)行查詢，具體的搜索代碼如下：
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
int64_t cur = -1;
/* The value can never be found when the set is empty */
// 處理 is 為空時的情況
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0;
return 0;
} else {
/* Check for the case where we know we cannot find the value,
* but do know the insert position. */
// 因為底層數(shù)組是有序的，如果 value 比數(shù)組中最后一個值都要大
// 那么 value 肯定不存在于集合中，
// 并且應(yīng)該將 value 添加到底層數(shù)組的最末端
if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
if (pos) *pos = intrev32ifbe(is->length);
return 0;
// 因為底層數(shù)組是有序的，如果 value 比數(shù)組中最前一個值都要小
// 那么 value 肯定不存在于集合中，
// 并且應(yīng)該將它添加到底層數(shù)組的最前端
} else if (value _intsetGet(is,0)) {
if (pos) *pos = 0;
return 0;
}
}
// 在有序數(shù)組中進(jìn)行二分查找
// T = O(log N)
while(max >= min) {
mid = (min+max)/2;
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value cur) {
max = mid-1;
} else {
break;
}
}
// 檢查是否已經(jīng)找到了 value
if (value == cur) {
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}
此外，整數(shù)集合中具體還有兩個需要說明的操作是升級和降級。升級指的是當(dāng)向低編碼的整數(shù)集合中添加位數(shù)較高的數(shù)值時，就會擴(kuò)容并將整數(shù)集合中的所有元素都轉(zhuǎn)換為高位數(shù)的編碼格式，然后把新添加的元素插入到指定位置；降級指的是當(dāng)將整數(shù)集合中唯一一個高位的元素刪除時會將其余元素轉(zhuǎn)換為低位數(shù)的編碼格式，但是為了提升速率，redis中并不會為剩余元素重新分配內(nèi)存并進(jìn)行編碼轉(zhuǎn)換，而只是會將該高位元素給刪除，并重新分配內(nèi)存給剩余的元素，然后遷移數(shù)據(jù)。如圖是inset保存數(shù)據(jù)的示例：
如有疑問請留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
您可能感興趣的文章:- Redis底層數(shù)據(jù)結(jié)構(gòu)詳解
- 詳解Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表
- redis中的數(shù)據(jù)結(jié)構(gòu)和編碼詳解
- redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)之SDS簡單動態(tài)字符串詳解
- 詳解redis數(shù)據(jù)結(jié)構(gòu)之sds
- 詳解redis數(shù)據(jù)結(jié)構(gòu)之壓縮列表
- Redis中5種數(shù)據(jù)結(jié)構(gòu)的使用場景介紹
- Redis底層數(shù)據(jù)結(jié)構(gòu)之dict、ziplist、quicklist詳解
