Redisbook学习笔记（2）内存映射数据结构（1）整数集合

虽然内部数据结构非常强大，但是创建一系列完整的数据结构本身也是一件相当耗费内存的工

作，当一个对象包含的元素数量并不多，或者元素本身的体积并不大时，使用代价高昂的内部

数据结构并不是最好的办法。

为了解决这一问题，Redis 在条件允许的情况下，会使用内存映射数据结构来代替内部数据结构。

内存映射数据结构是一系列经过特殊编码的字节序列，创建它们所消耗的内存通常比作用类似

的内部数据结构要少得多，如果使用得当，内存映射数据结构可以为用户节省大量的内存。

不过，因为内存映射数据结构的编码和操作方式要比内部数据结构要复杂得多，所以内存映射

数据结构所占用的CPU 时间会比作用类似的内部数据结构要多。

这一部分将对Redis 目前正在使用的两种内存映射数据结构进行介绍。

1、整数集合

整数集合（intset）用于有序、无重复地保存多个整数值，它会根据元素的值，自动选择该用什

么长度的整数类型来保存元素。

举个例子，如果在一个intset 里面，最长的元素可以用int16_t 类型来保存，那么这个intset

的所有元素都以int16_t 类型来保存。

另一方面，如果有一个新元素要加入到这个intset ，并且这个元素不能用int16_t 类型来保存

——比如说，新元素的长度为int32_t ，那么这个intset 就会自动进行“升级” ：先将集合中现

有的所有元素从int16_t 类型转换为int32_t 类型，接着再将新元素加入到集合中。

根据需要，intset 可以自动从int16_t 升级到int32_t 或int64_t ，或者从int32_t 升级到

int64_t 。

整数集合的应用

Intset 是集合键的底层实现之一，如果一个集合：

1. 只保存着整数元素；

2. 元素的数量不多；

那么Redis 就会使用intset 来保存集合元素。

数据结构和主要操作

以下是intset.h/intset 类型的定义：

encoding 的值可以是以下三个常量的其中一个（定义位于intset.c ）：

contents 数组是实际保存元素的地方，数组中的元素有以下两个特性：

没有重复元素；

元素在数组中从小到大排列；

contents 数组的int8_t 类型声明比较容易让人误解，实际上，intset 并不使用int8_t 类型

来保存任何元素，结构中的这个类型声明只是作为一个占位符使用：在对contents 中的元素

进行读取或者写入时，程序并不是直接使用contents 来对元素进行索引，而是根据encoding

的值，对contents 进行类型转换和指针运算，计算出元素在内存中的正确位置。在添加新元

素，进行内存分配时，分配的容量也是由encoding 的值决定。

intset 运行实例

让我们跟踪一个intset 的创建和添加过程，籍此了解intset 的运作方式。

创建新intset

intset.c/intsetNew 函数创建一个新的intset ，并为它设置初始化值：

注意encoding 使用INTSET_ENC_INT16 作为初始值。

添加新元素到intset

创建intset 之后，就可以对它添加新元素了。

添加新元素到intset 的工作由intset.c/intsetAdd 函数完成，它需要处理以下三种情况：

1. 元素已存在于集合，不做动作；

2. 元素不存在于集合，并且添加新元素并不需要升级；

3. 元素不存在于集合，但是要在升级之后，才能添加新元素；

并且，intsetAdd 需要维持intset->contents 的以下性质：

1. 确保数组中没有重复元素；

2. 确保数组中的元素按从小到大排序；

整个intsetAdd 的执行流程可以表示为下图：

以下两个小节分别演示添加操作在升级和不升级两种情况下的执行过程。

添加新元素到intset （不需要升级）

如果intset 现有的编码方式适用于新元素，那么可以直接将新元素添加到intset ，无须对intset

进行升级。

以下代码演示了将三个int16_t 类型的整数添加到集合的过程，以及在添加过程中，集合的状

态：

因为添加的三个元素都可以表示为int16_t ，因此is->encoding 一直都是INTSET_ENC_INT16

。

另一方面，is->length 和is->contents 的值则随着新元素的加入而被修改。

添加新元素到intset （需要升级）

当要添加新元素到intset ，并且intset 当前的编码并不适用于新元素的编码时，就需要对inset

进行升级。

以下代码演示了带升级的添加操作的执行过程：

在添加65535 和4294967295 之后，encoding 属性的值，以及contents 数组保存值的方式，

都被改变了。

升级

在添加新元素时，如果intsetAdd 发现新元素不能用现有的编码方式来保存，它就会将升级集

合和添加新元素的任务转交给intsetUpgradeAndAdd 来完成：

intsetUpgradeAndAdd 需要完成以下几个任务：

1. 对新元素进行检测，看保存这个新元素需要什么类型的编码；

2. 将集合encoding 属性的值设置为新编码类型，并根据新编码类型，对整个contents 数

组进行内存重分配。

3. 调整contents 数组内原有元素在内存中的排列方式，让它们从旧编码调整为新编码。

4. 将新元素添加到集合中。

整个过程中，最复杂的就是第三步，让我们用一个例子来理解这个步骤。

升级实例

假设有一个intset ，里面包含三个用int16_t 方式保存的数值，分别是1 、2 和3 ，它的结

构如下：

现在，我们要要将一个长度为int32_t 的值65535 加入到集合中，intset 需要执行以下步骤：

1. 将encoding 属性设置为INTSET_ENC_INT32 。

2. 根据encoding 属性的值，对contents 数组进行内存重分配。

重分配完成之后，contents 在内存中的排列如下：

contents 数组现在共有可容纳4 个int32_t 值的空间。

3. 因为原来的3 个int16_t 值还“挤在”contents 前面的48 个位里，所以程序需要对它们

进行移动和类型转换，从而让它们适应集合的新编码方式。

首先是移动3 ：

4. 最后，将新值65535 添加到数组：

至此，集合的升级和添加操作完成，现在的intset 结构如下：

关于升级

关于升级操作，还有两点需要提醒一下：

第一，从较短整数到较长整数的转换，并不会更改元素里面的值。

在C 语言中，从长度较短的带符号整数到长度较长的带符号整数之间的转换（比如从int16_t

转换为int32_t ）总是可行的（不会溢出）、无损的。

另一方面，从较长整数到较短整数之间的转换可能是有损的（比如从int32_t 转换为int16_t

）。

因为intset 只进行从较短整数到较长整数的转换（也即是，只“升级” ，不“降级” ），因此， “升

级”操作并不会修改元素原有的值。

第二，集合编码元素的方式，由元素中长度最大的那个值来决定。

就像前面演示的例子一样，当要将一个int32_t 编码的新元素添加到集合时，集合原有的所有

int16_t 编码的元素，都必须转换为int32_t 。

尽管这个集合真正需要用int32_t 长度来保存的元素只有一个，但整个集合的所有元素都必须

转换为这种类型。

关于元素移动

在进行升级的过程中，需要对数组内的元素进行“类型转换”和“移动”操作。

其中，移动不仅出现在升级（intsetUpgradeAndAdd）操作中，还出现其他对contents 数组内

容进行增删的操作上，比如intsetAdd 和intsetRemove ，因为这种移动操作需要处理intset

中的所有元素，所以这些函数的复杂度都不低于O(N) 。

其他操作

以下是一些关于intset 其他操作的讨论。

读取

有两种方式读取intset 的元素，一种是_intsetGet ，另一种是intsetSearch ：

_intsetGet 接受一个给定的索引pos ，并根据intset->encoding 的值进行指针运算，

计算出给定索引在intset->contents 数组上的值。

intsetSearch 则使用二分查找算法，判断一个给定元素在contents 数组上的索引。

写入

除了前面介绍过的intsetAdd 和intsetUpgradeAndAdd 之外，_intsetSet 也对集合进行写

入操作：它接受一个索引pos ，以及一个new_value ，将contents 数组pos 位置的值设为

new_value 。

删除

删除单个元素的工作由intsetRemove 操作，它先调用intsetSearch 找到需要被删除的元素

在contents 数组中的索引，然后使用内存移位操作，将目标元素从内存中抹去，最后，通过

内存重分配，对contents 数组的长度进行调整。

降级

Intset 不支持降级操作。

Intset 定位为一种受限的中间表示， 只能保存整数值， 而且元素的个数也不能超过

redis.h/REDIS_SET_MAX_INTSET_ENTRIES （目前版本值为512 ） 这些条件决定了它被保

存的时间不会太长，因此对它进行太复杂的操作，没有必要。

小结

Intset 用于有序、无重复地保存多个整数值，它会根据元素的值，自动选择该用什么长度

的整数类型来保存元素。

当一个位长度更长的整数值添加到intset 时，需要对intset 进行升级，新intset 中每个

元素的位长度都等于新添加值的位长度，但原有元素的值不变。

升级会引起整个intset 进行内存重分配，并移动集合中的所有元素，这个操作的复杂度

为O(N) 。

Intset 只支持升级，不支持降级。

Intset 是有序的，程序使用二分查找算法来实现查找操作，复杂度为O(lgN) 。

本文转自shayang8851CTO博客，原文链接：http://blog.51cto.com/janephp/1354757，如需转载请自行联系原作者