Redis の整数の小さなコレクション

整数セット (intset) は、セット キーの基礎となる実装の 1 つです。セットに整数値の要素のみが含まれており、このセット内の要素の数が多くない場合、Redis はセット キーの基礎となる実装として整数セットを使用します。 。

127.0.0.1:6379> sadd numbers 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding numbers
"intset"

この利点は、セット内の整数要素の数が少ない場合、sds など、以前に紹介した他のデータ構造を使用すると比較的大量のメモリを占有しますが、次の場合はより経済的であることです。整数セットとしてのみ保存されます。

整数配列データ構造

整数配列の定義は、次のように intset.h にあります:

typedef struct intset {
    uint32_t encoding;  // 编码方式
    uint32_t length;   // 保存的元素个数
    int8_t contents[];  // 保存元素的数组
 } 
    intset;

intset 構造は、内容属性を int8_t 型の配列として宣言しますが、実際には、内容配列は保存されませんint8_t 型の任意の値 ——内容配列の実際の型は、エンコーディング属性の値によって異なります:

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

/* Return the required encoding for the provided value. */
static uint8_t _intsetValueEncoding(int64_t v) {    
    if (v < INT32_MIN || v > INT32_MAX)        
        return INTSET_ENC_INT64;    
    else if (v < INT16_MIN || v > INT16_MAX)        
        return INTSET_ENC_INT32;    
    else
      return INTSET_ENC_INT16;
}

int_16、int_32、および int_64 に対応する、合計 3 つの型があることがわかります。

整数配列内のすべての要素は、配列内で小さいものから大きいものへの順序で配置され、配列には重複が含まれません。

整数セット操作

整数セットを作成する

// 初始化空的整数集合intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));    
    is->encoding = intrev32ifbe(INTSET_ENC_INT16); // 默认创建int_16的编码格式
    is->length = 0;    
    return is;
}

要素を挿入する

/* Insert an integer in the intset */intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;    
    if (success) *success = 1;    // 如果超出了当前编码格式所能表示的范围，则升级整数集合并添加元素
    if (valenc > intrev32ifbe(is->encoding)) {        
    /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {        // 如果元素已经存在于集合，success返回0
        // 如果不存在的话， 这个函数会返回元素应该插入的位置pos
        if (intsetSearch(is,value,&pos)) {            
        if (success) *success = 0;            
        return is;
        }        // 否则，需要重新调整集合的大小
        is = intsetResize(is,intrev32ifbe(is->length)+1);        // 将pos之后的数据全都向后挪动一个位子
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    _intsetSet(is,pos,value); // 添加数据到第pos位
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1); // 调整元素个数
    return is;
}

要素を挿入する場合、新しい要素のサイズに基づいて使用するエンコーディングを再決定する必要があります。新しい要素が元のエンコードの表現範囲を超える場合は、エンコードを調整する必要があり、コレクション内の他のすべての要素のエンコード形式も調整する必要があります。エンコードの調整は不可逆的なプロセスです。つまり、調整できるのは小さなエンコードから大きなエンコードまでのみで、アップグレードのみ可能でダウングレードはできません。

アップグレードプロセス

整数セットをアップグレードして新しい要素を追加すると、 intsetUpgradeAndAdd 関数が呼び出されます。これは 3 つのステップに分かれています:

• 新しい要素の型に応じて、整数の基になる配列のスペース サイズを拡張します。新しい要素スペースを設定して割り当てます。

• 基になる配列のすべての既存の要素を新しい要素と同じ型に変換し、型変換された要素を正しい位置に配置します。また、要素を配置するプロセス中に、基礎となる配列の順序付けされた性質は変わりません。

• 基礎となる配列に新しい要素を追加します。

/* Upgrades the intset to a larger encoding and inserts the given integer. */static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {    // 当前的编码
    uint8_t curenc = intrev32ifbe(is->encoding);    // 根据新元素的值获得新的编码
    uint8_t newenc = _intsetValueEncoding(value);    
    int length = intrev32ifbe(is->length);    
    // 由于整数集合是一个有序集合，所以新的这个超出范围的元素，要不插入头部，要不插入尾部
    // 当value大于0的时候，就是插入到尾部，否则插入到头部，用参数prepend来标记
    int prepend = value < 0 ? 1 : 0;    
    
    /* First set new encoding and resize */
    // 重新设置整数集合的编码
    is->encoding = intrev32ifbe(newenc);    // 根据新编码调整整数集合的大小
    is = intsetResize(is,intrev32ifbe(is->length)+1);    // 从尾部向头部进行升级，这样在挪动其中的元素的时候，不会覆盖原来的值
    while(length--)        
          // 如果新元素是插入到尾部，prepend==0， 所以原来最后的元素是挪动到length位置
        // 如果新元素是插入到头部，prepend==1，所有的元素都要向后挪动一个位置，将头部空出来
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));    
        
        /* Set the value at the beginning or the end. */
    if (prepend)        
    // 如果prepend==1， 插入到头部
        _intsetSet(is,0,value);    
       else
        // 否则，设置最后一个位置的元素为value
        _intsetSet(is,intrev32ifbe(is->length),value);    // 元素个数加1
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);    
    return is;
}

整数コレクションに対する現在のアプローチでは、コレクションに 3 つの異なるタイプの値を同時に格納できるだけでなく、アップグレード操作が必要な場合にのみ実行されるようにすることで、メモリをできるだけ節約できます。できるだけ。

要素の検索

検索するときは、まず、探している要素が現在のエンコーディングの有効な範囲内にあるかどうかを判断する必要があります。現在の範囲内にない場合は、その要素を直接返すことができます。

また、整数集合は順序集合であるため、二分探索が使用でき、

uint8_t intsetFind(intset *is, int64_t value) {    // 获得目标值的编码
    uint8_t valenc = _intsetValueEncoding(value);    // 只有目标值的编码比当前编码小，才继续执行查找过程
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}// 如果找到这个元素，返回1，同时pos表示这个值在整数集合里边的位置
// 如果没有找到这个元素，返回0， 同时pos表示这个值可以插入的位置
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 */
    // 如果集合的长度为0， 直接返回0
    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. */
        // 如果目标值大于当前最大值，肯定找不到，返回0， 同时待插入的位置pos为length
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {            
        if (pos) *pos = intrev32ifbe(is->length);            
        return 0;
        } else if (value < _intsetGet(is,0)) {            
        // 如果目标址小于当前最小值，返回0， 同时待插入的位置pos为0
            if (pos) *pos = 0;            
            return 0;
        }
    }    // 二分查找
    while(max >= min) {        // 得到中间位置
        mid = ((unsigned int)min + (unsigned int)max) >> 1;        // 得到中间位置的值
        cur = _intsetGet(is,mid);        
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {            
        break;
        }
    }    if (value == cur) {        
    if (pos) *pos = mid;        
    return 1;
    } else {        
    if (pos) *pos = min;        
    return 0;
    }
}

以上がRedis の整数の小さなコレクションの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。