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

2024-02-16 22:33:17

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

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

typedef struct intset {

  // 编码方式
  uint32_t encoding;

  // 集合包含的元素数量
  uint32_t length;

  // 保存元素的数组
  int8_t contents[];

} intset;

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

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

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保存数据的示例：

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

Linux Redis 的安装步骤详解

Linux Redis 的安装步骤详解前言: Redis 是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库.缓存和消息中间件. 它支持多种类型的数据结构,如字符串(strings), 散列(hashes), 列表(lists), 集合(sets), 有序集合(sorted sets) 与范围查询, bitmaps, hyperloglogs 和地理空间(geospatial) 索引半径查询. redis 是完全开源免费的,是一个高性能的key-value数据库.Re
python脚本实现Redis未授权批量提权

前言本文主要给大家介绍了关于redis未授权批量提权的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 安装依赖 sudo easy_install redis 使用 redis python hackredis.py usage: hackredis.py [-h] [-l IPLIST] [-p PORT] [-r ID_RSAFILE] [-sp SSH_PORT] For Example: -----------------------------------
Redis集群搭建全记录

Redis集群是一个提供在多个Redis节点间共享数据的程序集. Redis集群中不支持处理多个keys的命令. Redis集群通过分区来提供一定程度的可用性.在某个节点宕机或者不可用的时候可以继续处理命令. Redis集群数据分片在Redis集群中,使用数据分片(sharding)而不是一致性hash(consistency hashing)来实现,一个Redis集群包含16384个哈希槽(hash slot),数据库中的每个键都存在这些哈希槽中的某一个,通过CRC16校验后对16384取模
redis集群搭建教程及遇到的问题处理

这里,在一个Linux虚拟机上搭建6个节点的redis伪集群,思路很简单,一台虚拟机上开启6个redis实例,每个redis实例有自己的端口.这样的话,相当于模拟出了6台机器了,然后在以这6个实例组建redis集群就可以了. 前提:redis已经安装,目录为/usr/local/redis-4.0.1 如不会,可以参考一下文章 windows下安装redis Linux下安装redis redis集群是用的ruby脚本,所以要想执行该脚本,需要ruby环境..对应redis的源码src目
redis数据类型_动力节点Java学院整理

Redis支持5种数据类型,它们描述如下: Strings - 字符串 Redis的字符串是字节序列.在Redis中字符串是二进制安全的,这意味着他们有一个已知的长度,是没有任何特殊字符终止决定的,所以可以存储任何东西,最大长度可达512兆. 例子 redis 127.0.0.1:6379> SET name "yiibai" OK redis 127.0.0.1:6379> GET name "yiibai" 在上面的例子使用Redis命令set和ge
Redis 实现队列原理的实例详解

Redis 实现队列原理的实例详解场景说明: ·用于处理比较耗时的请求,例如批量发送邮件,如果直接在网页触发执行发送,程序会出现超时 ·高并发场景,当某个时刻请求瞬间增加时,可以把请求写入到队列,后台在去处理这些请求 ·抢购场景,先入先出的模式命令: rpush + blpop 或 lpush + brpop rpush : 往列表右侧推入数据 blpop : 客户端阻塞直到队列有值输出简单队列: simple.php $stmt = $pdo->prepare('select id, c
redis数据结构之intset的实例详解

redis数据结构之intset的实例详解在redis中,intset主要用于保存整数值,由于其底层是使用数组来保存数据的,因而当对集合进行数据添加时需要对集合进行扩容和迁移操作,因而也只有在数据量不大时redis才使用该数据结构来保存整数集合.其具体的底层数据结构如下: typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; }
数据结构栈的操作实例详解

数据结构栈的操作实例详解说明: 往前学习数据结构,想运行一个完整的顺序栈的程序都运行不了,因为书上给的都是一部分一部分的算法,并没有提供一个完整可运行的程序,听了实验课,自己折腾了一下,总算可以写一个比较完整的顺序栈操作的小程序,对于栈也慢慢开始有了感觉.下面我会把整个程序拆开来做说明,只要把这些代码放在一个文件中,用编译器就可以直接编译运行了. 一.实现 1.程序功能关于栈操作的经典程序,首当要提及进制数转换的问题,利用栈的操作,就可以十分快速地完成数的进制转换. 2.预定义.头文件导入
数据结构之数组Array实例详解

数据结构之数组Array实例详解数组Array 基本操作 Status InitArray(int dimm,...)//若维数dim和随后的各维长度合法,则构造相应的数组A,并返回OK Status DestroyArray() //销毁数组A Status Locate(va_list ap,int &off) //若ap指示的各下标值合法,则求出该元素在A中相对地址off Status Value(ElemType &e,...) //A是n维数组,e为元素变量,随后是n个下标值.
C语言数据结构链表与归并排序实例详解

C语言数据结构链表与归并排序实例详解归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这
数据结构串的操作实例详解

数据结构串的操作实例详解串是一种特殊的线性表,它的每个结点是一个字符,所以串也称作字符串. 关于串的操作主要有求串长,串复制,串连接,求子串,串插入,串删除,子串定位等.串的操作也是C语言笔试中常考的一部分. 下面的代码实现了串的主要操作. #include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 char *String_Create(); //创建串 int String_Length(char *s); //求串长
数据结构双机调度问题的实例详解

数据结构双机调度问题的实例详解 1.问题描述双机调度问题,又称独立任务最优调度:用两台处理机A和B处理n个作业.设第i个作业交给机器A处理时所需要的时间是a[i],若由机器B来处理,则所需要的时间是b[i].现在要求每个作业只能由一台机器处理,每台机器都不能同时处理两个作业.设计一个动态规划算法,使得这两台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总的时间). 研究一个实例:n=6, a = {2, 5, 7, 10, 5, 2}, b = {3, 8, 4, 1
C#数据结构之双向链表(DbLinkList)实例详解

本文实例讲述了C#数据结构之双向链表(DbLinkList).分享给大家供大家参考,具体如下: 这是继上一篇<C#数据结构之单链表(LinkList)实例详解>的继续,对于双向链接,节点上除了Next属性外,还要有Prev属性用来指向前一个节点,DbNode定义如下: namespace 线性表 { public class DbNode<T> { private T data; private DbNode<T> prev; private DbNode<T&g
数据结构之归并排序的实例详解

归并排序基本思想归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表:将这些有序序列再次归并,得到n/4个长度为4的有序序列:如此反复进行下去,最后得到一个长度为n的有序序列.所以呢,我们总结一下归并排序其实就只有两步:
Java数据结构与算法入门实例详解

第一部分:Java数据结构要理解Java数据结构,必须能清楚何为数据结构? 数据结构: Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构. 而一个数据结构的设计过程分成抽象层.数据结构层和实现层. 数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构. 一.Java数据结构之:线性数据结构线性数据结构:常见的

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

相关推荐

随机推荐