《Redis设计与实现》读书笔记（五） ——Redis中的整数集合

《Redis设计与实现》读书笔记（五） ——Redis中的整数集合

（原创内容，转载请注明来源，谢谢）

一、概述

整数集合（intset）是redis数据结构集合（set）的底层实现之一，如果set中只包含整数元素，且元素个数不多时，redis会使用整数集合作为set的底层实现。

二、整数集合实现

整数集合是redis保存整数值集合的底层实现，可以保存int16_t、int32_t、int64_t的整数值，且集合中每个值都不一样。结构如下：

typedef struct         intset{
uint32_t encoding;
uint32_t length;
int8_t contents[];
}intset;

其中，encoding是编码方式，length是集合的元素个数，contents是保存集合中的元素，每个元素在contents数组中，从小到大排列。

contents虽然被定义是int8_t类型，但是实际是根据encoding进行确认。如果encoding是INTSET_ENC_INT16，则contents里面每一个元素都是int16_t类型（值在-32768~32767）；如果是INTSET_ENC_INT32，则contents里面每一个元素都是int32_t类型（值在-2^32~2^32-1）；如果encoding是INTSET_ENC_INT64，则contents里面每一个元素都是int64_t类型（值在-2^64~2^64-1）。

包含五个整数元素的整数集合如下图所示：

该contents占底层空间大小是16*5=80字节。

三、整数集合升级

1、升级过程

当要将一个新元素添加到contents里面，而该元素的类型比contents现有的元素长时，则redis会对contents进行升级（upgrade）。升级过程如下：

1）根据新元素的类型，扩展contents底层空间大小，并为新元素分配空间（但还没将元素添加进数组）。

2）将底层现有元素都转换成新类型，转换后继续放在原位置上，保持大小顺序不变。

3）将新元素添加到底层数组，并且将intset的length值加1，修改encoding的值为新的数据类型。

由于新元素加入后，导致类型需要扩充，说明这个新元素，要么比现有最大的元素大，要么比现有最小的元素小，即新元素的索引要么是0，要么是length-1。

因此，底层数组元素转换后，迁移位置的过程是：

1）如果新元素最大，则转换过程是将现有最大的元素转换到最后新增的位置前面的位置（最后的位置留给新元素），然后次大的数据转换，以此类推。

2）如果新元素最小，则转换过程是将现有最大的元素转换到最后新增的位置，然后次大的转换，直到原contents最小的元素转换后，第一个位置留给新元素。

2、升级的优势

升级的主要优势是提升灵活性、节约内存。

1）灵活性

C语言是静态语言，redis由C语言实现，因此为了避免错误，不会将不同的类型放到一个数据结构里面。因此，redis的自动升级，使得可以放置不同类型的整数，而不会报错。

2）节约内存

当有需要的时候才升级，而不是默认都用int64_t类型，则节约了内存。

3、不支持降级

redis不支持降级，因此一旦升级后，即使后来大类型的元素被删除，仍会保持原来的状态。例如已经升级到int64_t，后面集合的所有int64_t的元素都被删除，只剩下int32_t的元素，contents的编码仍将采用int64_t。

——written by linhxx 2017.08.30