redis數據結構之intset的實例詳解

2020-10-28 21:35:29

字體：大中小

來源：轉載

供稿：網友

redis數據結構之intset的實例詳解

在redis中，intset主要用于保存整數值，由于其底層是使用數組來保存數據的，因而當對集合進行數據添加時需要對集合進行擴容和遷移操作，因而也只有在數據量不大時redis才使用該數據結構來保存整數集合。其具體的底層數據結構如下：

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

整數集合主要有三個屬性：encoding用于保存當前集合的編碼，有16位，32位和64位三種；length保存了當前整數集合中保存的數據數量；contents屬性則保存了具體的數據，其每個數據占用的位數由encoding屬性指定。

這里主要需要進行說明的是redis的intset中數據是采用從小到大的順序存儲的，因而對于數據的查詢可以采用二分法進行查詢，具體的搜索代碼如下：

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. */    // 因為底層數組是有序的，如果 value 比數組中最后一個值都要大    // 那么 value 肯定不存在于集合中，    // 并且應該將 value 添加到底層數組的最末端    if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {      if (pos) *pos = intrev32ifbe(is->length);      return 0;    // 因為底層數組是有序的，如果 value 比數組中最前一個值都要小    // 那么 value 肯定不存在于集合中，    // 并且應該將它添加到底層數組的最前端    } else if (value < _intsetGet(is,0)) {      if (pos) *pos = 0;      return 0;    }  }  // 在有序數組中進行二分查找  // 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;    }  }  // 檢查是否已經找到了 value  if (value == cur) {    if (pos) *pos = mid;    return 1;  } else {    if (pos) *pos = min;    return 0;  }}

此外，整數集合中具體還有兩個需要說明的操作是升級和降級。升級指的是當向低編碼的整數集合中添加位數較高的數值時，就會擴容并將整數集合中的所有元素都轉換為高位數的編碼格式，然后把新添加的元素插入到指定位置；降級指的是當將整數集合中唯一一個高位的元素刪除時會將其余元素轉換為低位數的編碼格式，但是為了提升速率，redis中并不會為剩余元素重新分配內存并進行編碼轉換，而只是會將該高位元素給刪除，并重新分配內存給剩余的元素，然后遷移數據。如圖是inset保存數據的示例：