服务器之家:专注于服务器技术及软件下载分享
分类导航

Mysql|Sql Server|Oracle|Redis|

服务器之家 - 数据库 - Redis - redis数据结构之intset的实例详解

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

2019-11-08 14:59爱宝贝丶 Redis

这篇文章主要介绍了redis数据结构之intset的实例详解的相关资料, intset也即整数集合,当集合保存的值数量不多时,redis使用intset作为其底层数据保存结构,希望通过本文能帮助到大家,需要的朋友可以参考下

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {
  
  // 编码方式
  uint32_t encoding;
 
  // 集合包含的元素数量
  uint32_t length;
 
  // 保存元素的数组
  int8_t contents[];
 
} intset;

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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保存数据的示例:

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

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

延伸 · 阅读

精彩推荐
  • RedisRedis教程(九):主从复制配置实例

    Redis教程(九):主从复制配置实例

    这篇文章主要介绍了Redis教程(九):主从复制配置实例,本文讲解了Redis的Replication、Replication的工作原理、如何配置Replication、应用示例等内容,需要的朋友可...

    Redis教程网3592019-10-24
  • RedisRedis列表类型的常用命令小结

    Redis列表类型的常用命令小结

    这篇文章给大家整理了在操作Redis列表类型中的常用命令,文章总结的很全面,对大家学习Redis具有一定的参考借鉴价值,下面来一起看看吧。 ...

    daisy2992019-10-30
  • RedisRedis教程(十三):管线详解

    Redis教程(十三):管线详解

    这篇文章主要介绍了Redis教程(十三):管线详解,本文讲解了请求应答协议和RTT、管线(pipelining)、Benchmark等内容,需要的朋友可以参考下 ...

    Redis教程网3062019-10-24
  • RedisRedis教程(六):Sorted-Sets数据类型

    Redis教程(六):Sorted-Sets数据类型

    这篇文章主要介绍了Redis教程(六):Sorted-Sets数据类型,本文讲解了Sorted-Sets数据类型概述、相关命令列表、命令使用示例、应用范围等内容,需要的朋友可以参...

    Redis教程网1842019-10-24
  • RedisRedis 对比 Memcached 并在 CentOS 下进行安装配置详解

    Redis 对比 Memcached 并在 CentOS 下进行安装配置详解

    Redis 是一个开源、支持网络、基于内存、键值对的 Key-Value 数据库,本篇文章主要介绍了Redis 对比 Memcached 并在 CentOS 下进行安装配置详解,有兴趣的可以了...

    cnblogs5042019-11-01
  • RedisUbuntu下安装redis的2种方法分享

    Ubuntu下安装redis的2种方法分享

    redis是一个开源的、使用C语言编写的、支持网络交互的、可基于内存也可持久化的Key-Value数据库。这篇文章对redis就不进行详细的介绍了,这篇文章主要给...

    daisy2072019-11-01
  • Redis将MongoDB作为Redis式的内存数据库的使用方法

    将MongoDB作为Redis式的内存数据库的使用方法

    这篇文章主要介绍了将MongoDB作为Redis式的内存数据库的使用方法,原理其实只是将内存虚拟作为磁盘,需要的朋友可以参考下 ...

    goldensun1772019-10-25
  • Redis基于redis实现的点赞功能设计思路详解

    基于redis实现的点赞功能设计思路详解

    点赞是我们现在经常见到的一个效果,如朋友圈、微博都有点赞的效果,下面这篇文章主要跟大家分享了基于redis实现的点赞功能设计思路的相关资料,文...

    Furion2392019-11-05