快捷導(dǎo)航

redis數(shù)據(jù)結(jié)構(gòu)之intset的實(shí)例詳解

更新時(shí)間：2017年09月22日 14:18:51 作者：愛(ài)寶貝丶

這篇文章主要介紹了redis數(shù)據(jù)結(jié)構(gòu)之intset的實(shí)例詳解的相關(guān)資料, intset也即整數(shù)集合，當(dāng)集合保存的值數(shù)量不多時(shí)，redis使用intset作為其底層數(shù)據(jù)保存結(jié)構(gòu)，希望通過(guò)本文能幫助到大家，需要的朋友可以參考下

redis數(shù)據(jù)結(jié)構(gòu)之intset的實(shí)例詳解

在redis中，intset主要用于保存整數(shù)值，由于其底層是使用數(shù)組來(lái)保存數(shù)據(jù)的，因而當(dāng)對(duì)集合進(jìn)行數(shù)據(jù)添加時(shí)需要對(duì)集合進(jìn)行擴(kuò)容和遷移操作，因而也只有在數(shù)據(jù)量不大時(shí)redis才使用該數(shù)據(jù)結(jié)構(gòu)來(lái)保存整數(shù)集合。其具體的底層數(shù)據(jù)結(jié)構(gòu)如下：

typedef struct intset {
  
  // 編碼方式
  uint32_t encoding;

  // 集合包含的元素?cái)?shù)量
  uint32_t length;

  // 保存元素的數(shù)組
  int8_t contents[];

} intset;

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

這里主要需要進(jìn)行說(shuō)明的是redis的intset中數(shù)據(jù)是采用從小到大的順序存儲(chǔ)的，因而對(duì)于數(shù)據(jù)的查詢(xún)可以采用二分法進(jìn)行查詢(xú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 為空時(shí)的情況
  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. */
    // 因?yàn)榈讓訑?shù)組是有序的，如果 value 比數(shù)組中最后一個(gè)值都要大
    // 那么 value 肯定不存在于集合中，
    // 并且應(yīng)該將 value 添加到底層數(shù)組的最末端
    if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
      if (pos) *pos = intrev32ifbe(is->length);
      return 0;
    // 因?yàn)榈讓訑?shù)組是有序的，如果 value 比數(shù)組中最前一個(gè)值都要小
    // 那么 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ù)集合中具體還有兩個(gè)需要說(shuō)明的操作是升級(jí)和降級(jí)。升級(jí)指的是當(dāng)向低編碼的整數(shù)集合中添加位數(shù)較高的數(shù)值時(shí)，就會(huì)擴(kuò)容并將整數(shù)集合中的所有元素都轉(zhuǎn)換為高位數(shù)的編碼格式，然后把新添加的元素插入到指定位置；降級(jí)指的是當(dāng)將整數(shù)集合中唯一一個(gè)高位的元素刪除時(shí)會(huì)將其余元素轉(zhuǎn)換為低位數(shù)的編碼格式，但是為了提升速率，redis中并不會(huì)為剩余元素重新分配內(nèi)存并進(jìn)行編碼轉(zhuǎn)換，而只是會(huì)將該高位元素給刪除，并重新分配內(nèi)存給剩余的元素，然后遷移數(shù)據(jù)。如圖是inset保存數(shù)據(jù)的示例：