小程序开发的价格,百度站长工具seo综合查询,给手机开发网站,九江网站建设张旭目录
一、内存映射数据结构
二、整数集合
1、整数集合的应用
2、数据结构和主要操作
3、intset运行实例
创建新intset
添加新元素到 intset
添加新元素到 intset#xff08;不需要升级#xff09;
添加新元素到 intset (需要升级)
4、升级
升级实例
5、关于升级 …目录
一、内存映射数据结构
二、整数集合
1、整数集合的应用
2、数据结构和主要操作
3、intset运行实例
创建新intset
添加新元素到 intset
添加新元素到 intset不需要升级
添加新元素到 intset (需要升级)
4、升级
升级实例
5、关于升级
第一从较短整数到较长整数的转换并不会更改元素里面的值。
第二集合编码元素的方式由元素中长度最大的那个值来决定。
6、 关于元素移动
7、 其他操作
读取
写入
删除
降级
三、小结 一、内存映射数据结构
虽然内部数据结构非常强大但是创建一系列完整的数据结构本身也是一件相当耗费内存的工作当一个对象包含的元素数量并不多或者元素本身的体积并不大时使用代价高昂的内部数据结构并不是最好的办法。
为了解决这一问题 Redis在条件允许的情况下会使用内存映射数据结构来代替内部数据结构。
内存映射数据结构是一系列经过特殊编码的字节序列创建它们所消耗的内存通常比作用类似的内部数据结构要少得多如果使用得当内存映射数据结构可以为用户节省大量的内存。
不过因为内存映射数据结构的编码和操作方式要比内部数据结构要复杂得多所以内存映射数据结构所占用的 CPU时间会比作用类似的内部数据结构要多。
这一部分将对 Redis目前正在使用的两种内存映射数据结构进行介绍。
二、整数集合
整数集合 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 。
1、整数集合的应用
Intset是集合键的底层实现之一如果一个集合
1.只保存着整数元素
2.元素的数量不多
那么 Redis就会使用 intset来保存集合元素。
2、数据结构和主要操作
以下是intset.h/intset 类型的定义
typedef structintset {//保存元素所使用的类型的长度uint32_t encoding;//元素个数uint32_t length;//保存元素的数组int8_tcontents[];} intset;
encoding 的值可以是以下三个常量的其中一个定义位于 intset.c
#define INTSET_ENC_INT16 (sizeof(int16_t))#define INTSET_ENC_INT32 (sizeof(int32_t))#define INTSET_ENC_INT64 (sizeof(int64_t))
contents 数组是实际保存元素的地方数组中的元素有以下两个特性
•没有重复元素
•元素在数组中从小到大排列
contents 数组的int8_t类型声明比较容易让人误解实际上 intset并不使用 int8_t类型来保存任何元素结构中的这个类型声明只是作为一个占位符使用在对 contents 中的元素进行读取或者写入时程序并不是直接使用 contents 来对元素进行索引而是根据 encoding的值对 contents 进行类型转换和指针运算计算出元素在内存中的正确位置。在添加新元素进行内存分配时分配的容量也是由 encoding 的值决定。
下表列出了处理 intset的一些主要操作以及这些操作的算法复杂度 3、intset运行实例
让我们跟踪一个 intset的创建和添加过程籍此了解 intset的运作方式。
创建新intset
intset.c/intsetNew 函数创建一个新的 intset并为它设置初始化值
intset*isintsetNew();// intset-encoding INTSET_ENC_INT16;// intset-length 0;// intset-contents [];
注意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 类型的整数添加到集合的过程以及在添加过程中集合的状 态
intset*isintsetNew();intsetAdd(is, 10,NULL);// is-encoding INTSET_ENC_INT16;// is-length 1;// is-contents [10];intsetAdd(is, 5,NULL);// is-encoding INTSET_ENC_INT16;// is-length 2;// is-contents [5, 10];intsetAdd(is, 12, NULL);// is-encoding INTSET_ENC_INT16;// is-length 3;// is-contents [5, 10, 12]
因为添加的三个元素都可以表示为 int16_t 因此 is-encoding 一直都是 INTSET_ENC_INT16 。
另一方面is-length 和 is-contents 的值则随着新元素的加入而被修改。
添加新元素到 intset (需要升级)
当要添加新元素到 intset 并且 intset 当前的编码并不适用于新元素的编码时就需要对 inset 进行升级。
以下代码演示了带升级的添加操作的执行过程:
intset *is intsetNew();
intsetAdd(is, 1, NULL);
// is-encoding INTSET_ENC_INT16;
// is-length 1;
// is-contents [1];
intsetAdd(is, 65535, NULL);
// is-encoding INTSET_ENC_INT32;
// is-length 2;
// is-contents [1, 65535];
intsetAdd(is, 70000, NULL);
// is-encoding INTSET_ENC_INT32;
// is-length 3;
// is-contents [1, 65535, 70000];
intsetAdd(is, 4294967295, NULL);
// is-encoding INTSET_ENC_INT64;
// is-length 4;
// is-contents [1, 65535, 70000, 4294967295];
// 所有值使用 int16_t 保存
// 升级
// 所有值使用 int32_t 保存
// 升级
// 所有值使用 int64_t 保存
在添加 65535 和 4294967295 之后encoding 属性的值以及 contents 数组保存值的方式 都被改变了。
4、升级
在添加新元素时如果 intsetAdd 发现新元素不能用现有的编码方式来保存它就会将升级集
合和添加新元素的任务转交给 intsetUpgradeAndAdd 来完成: intsetUpgradeAndAdd 需要完成以下几个任务: 对新元素进行检测看保存这个新元素需要什么类型的编码; 将集合encoding属性的值设置为新编码类型并根据新编码类型对整个contents数 组进行内存重分配。 调整contents数组内原有元素在内存中的排列方式让它们从旧编码调整为新编码。 将新元素添加到集合中。
整个过程中最复杂的就是第三步让我们用一个例子来理解这个步骤。
升级实例
假设有一个 intset 里面包含三个用 int16_t 方式保存的数值分别是 1 、2 和 3 它的结 构如下:
intset-encoding INTSET_ENC_INT16;
intset-length 3;
intset-contents [1, 2, 3];
其中intset-contents 在内存中的排列如下:
bit 0 15 31 47
value | 1 | 2 | 3 |
现在我们要要将一个长度为 int32_t 的值 65535 加入到集合中intset 需要执行以下步骤:
1. 将encoding属性设置为INTSET_ENC_INT32。 2. 根据encoding属性的值对contents数组进行内存重分配。
重分配完成之后contents 在内存中的排列如下:
bit 0 15 31 47 63 95 127
value | 1 | 2 | 3 | ? | ? | ? |
3.因为原来的 3 个 int16_t 值还“挤在”contents 前面的 48 个位里所以程序需要对它们
进行移动和类型转换从而让它们适应集合的新编码方式。 首先是移动 3 : 接着移动2: 最后移动 1 : 4.最后将新值 65535 添加到数组: 将 intset-length 设置为 4 。
至此集合的升级和添加操作完成现在的 intset 结构如下:
intset-encoding INTSET_ENC_INT32;
intset-length 4;
intset-contents [1, 2, 3, 65535];
5、关于升级
关于升级操作还有两点需要提醒一下:
第一从较短整数到较长整数的转换并不会更改元素里面的值。
在 C 语言中从长度较短的带符号整数到长度较长的带符号整数之间的转换(比如从 int16_t 转换为 int32_t )总是可行的(不会溢出)、无损的。
另一方面从较长整数到较短整数之间的转换可能是有损的(比如从 int32_t 转换为 int16_t )。
因为 intset 只进行从较短整数到较长整数的转换(也即是只“升级” 不“降级” )因此 “升 级”操作并不会修改元素原有的值。
第二集合编码元素的方式由元素中长度最大的那个值来决定。
就像前面演示的例子一样当要将一个 int32_t 编码的新元素添加到集合时集合原有的所有 int16_t 编码的元素都必须转换为 int32_t 。
尽管这个集合真正需要用 int32_t 长度来保存的元素只有一个但整个集合的所有元素都必须 转换为这种类型。
6、 关于元素移动
在进行升级的过程中需要对数组内的元素进行“类型转换”和“移动”操作。
其中移动不仅出现在升级(intsetUpgradeAndAdd)操作中还出现其他对 contents 数组内 容进行增删的操作上比如 intsetAdd 和 intsetRemove 因为这种移动操作需要处理 intset 中的所有元素所以这些函数的复杂度都不低于 O(N) 。
7、 其他操作
以下是一些关于 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 进行升级新 intset 中每个 元素的位长度都等于新添加值的位长度但原有元素的值不变。 升级会引起整个 intset 进行内存重分配并移动集合中的所有元素这个操作的复杂度 O(N) Intset 只支持升级不支持降级。 Intset 是有序的程序使用二分查找算法来实现查找操作复杂度为 O(lgN) 。
