《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

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

41. 最大子数组

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。 样例: 给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,...

541
来自专栏Modeng的专栏

Javascript数组系列四之数组的转换与排序Sort方法

今天我们继续来介绍 Javascirpt 数组中的方法,也是数组系列的第四篇文章,因为数组的方法众多,每篇文章我们都对数组的每个方法都有比较细致的描述,只要你能...

641
来自专栏机器学习算法与Python学习

python基础-字符串与编码

转载于:廖雪峰的官方网站-python教程 字符编码 我们已经讲过了,字符串也是一种数据类型,但是,字符串比较特殊的是还有一个编码问题。 因为计算机只能处理数字...

44111
来自专栏鬼谷君

Python pass语句作用与用法

692
来自专栏贾老师の博客

C/C++ 中的异常处理

1022
来自专栏Pythonista

python之字符编码的重要思想

        unicode----->encode-------->utf-8

892
来自专栏CDA数据分析师

教你一招 | Python3新特性(一) :字符串

从python2转到python3的第一个问题就是字符串的问题,我花了些时间把我能想到的和字符串处理有关的东西都整理如下。 1、Python2的字符串编码 在p...

18010
来自专栏Crossin的编程教室

【编程课堂】装饰器浅析

Python 拥有丰富强大的功能和表达特性,其中之一便是装饰器,装饰器能够在不改变函数、方法、类本身的情况下丰富他们的功能。 比如,我们有一个函数 func ,...

2907
来自专栏阿凯的Excel

索引功能(Pandas读书笔记10)

当我们定义一个Series类型的数据的时候,发现Pandas会帮我们自定义生成一个0到3的索引,我个人是比较喜欢使用Pandas给我们生成的自定义索引,但是部分...

631
来自专栏iOS开发攻城狮的集散地

浅谈iOS内存管理机制

1929

扫码关注云+社区