您的位置:js12345金沙官网登入 > 网络编程 > Redis 的底层数据结构

Redis 的底层数据结构

2020-03-13 10:54

redis数据结构之intset的实例详解

时间: 2019-09-20阅读: 121标签: 结构

在redis中,intset主要用于保存整数值,由于其底层是使用数组来保存数据的,因而当对集合进行数据添加时需要对集合进行扩容和迁移操作,因而也只有在数据量不大时redis才使用该数据结构来保存整数集合。其具体的底层数据结构如下:

当一个集合中只包含整数,并且元素的个数不是很多的话,redis 会用整数集合作为底层存储,它的一个优点就是可以节省很多内存,虽然字典结构的效率很高,但是它的实现结构相对复杂并且会分配较多的内存空间。

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

而我们的整数集合(intset)可以做到使用较少的内存空间却达到和字典一样效率的实现,但也是前提的,集合中只能包含整型数据并且数量不能太多。整数集合最多能存多少个元素在 redis 中也是有体现的。

整数集合主要有三个属性:encoding用于保存当前集合的编码,有16位,32位和64位三种;length保存了当前整数集合中保存的数据数量;contents属性则保存了具体的数据,其每个数据占用的位数由encoding属性指定。

OBJ_SET_MAX_INTSET_ENTRIES 512

这里主要需要进行说明的是redis的intset中数据是采用从小到大的顺序存储的,因而对于数据的查询可以采用二分法进行查询,具体的搜索代码如下:

也就是超过 512 个元素,或者向集合中添加了字符串或其他数据结构,redis 会将整数集合向字典结构进行转换。

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 */ // 处理 is 为空时的情况 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. */ // 因为底层数组是有序的,如果 value 比数组中最后一个值都要大 // 那么 value 肯定不存在于集合中, // 并且应该将 value 添加到底层数组的最末端 if (value  _intsetGet(is,intrev32ifbe(is-length)-1)) { if (pos) *pos = intrev32ifbe(is-length); return 0; // 因为底层数组是有序的,如果 value 比数组中最前一个值都要小 // 那么 value 肯定不存在于集合中, // 并且应该将它添加到底层数组的最前端 } else if (value  _intsetGet(is,0)) { if (pos) *pos = 0; return 0; } } // 在有序数组中进行二分查找 // T = O(log N) while(max = min) { mid = (min+max)/2; cur = _intsetGet(is,mid); if (value  cur) { min = mid+1; } else if (value  cur) { max = mid-1; } else { break; } } // 检查是否已经找到了 value if (value == cur) { if (pos) *pos = mid; return 1; } else { if (pos) *pos = min; return 0; }}

一、基本的数据结构

此外,整数集合中具体还有两个需要说明的操作是升级和降级。升级指的是当向低编码的整数集合中添加位数较高的数值时,就会扩容并将整数集合中的所有元素都转换为高位数的编码格式,然后把新添加的元素插入到指定位置;降级指的是当将整数集合中唯一一个高位的元素删除时会将其余元素转换为低位数的编码格式,但是为了提升速率,redis中并不会为剩余元素重新分配内存并进行编码转换,而只是会将该高位元素给删除,并重新分配内存给剩余的元素,然后迁移数据。如图是inset保存数据的示例:

intset 的结构定义很简单,有以下成员构成:

如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

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

encoding 记录当前 intset 使用编码,有三个取值:

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

length 记录整数集合中目前存储了多少个元素,contents 记录我们实际的数据集合,虽然我们看到结构体中给数组元素的类型定死成 int8_t,但实际上这个 int8_t 定义的毫无意义,因为这里的处理方式非常规的数组操作,content 字段虽然被定义成指向一个 int8_t 类型数据的指针,但实际上 redis 无论是读取数组元素还是新增元素进去都依赖 encoding 和 length 两个字段直接操作的内存。

基本数据结构还是非常的简单的,下面我们来看看它的一些核心方法。

二、核心 API 实现

1、初始化一个 intset

intset *intsetNew(void) { intset *is = zmalloc(sizeof(intset)); is-encoding = intrev32ifbe(INTSET_ENC_INT16); is-length = 0; return is;}

可见,默认的 inset 配置是使用 INTSET_ENC_INT16 作为数据存储大小,并且不会为 content 数组初始化。常规的数组需要先预先确定数组长度,然后分配内存,继而通过 contents[x] 可以访问数组中任一元素。

但是,inset 这里是非常规式操作数组,encoding 字段定义了数组中每个元素实际类型,lenth 字段定义了数组中实际的元素个数,那么 contents[x] 是失效的,这种方式只会按照 int8_t 进行内存偏移,这种方式是拿不到正确的数据的,所以 redis 中通过 memcpy 按照 encoding 字段的值暴力直接偏移地址操作内存读取数据。

所以,这也是为什么 intset 初始化时不初始化 content 数组的原因所在,因为没有必要。而每当新增一个元素的时候都会去动态扩容原数组的长度以盛放下新插入进来的元素,扩容不会扩容很多,刚好一个新元素所占用的内存即可。具体的细节,我们接着看。

本文由js12345金沙官网登入发布于网络编程,转载请注明出处:Redis 的底层数据结构

关键词: