redis笔记-数据结构

zset

zset一方面它是一个 set,保证了内部value 的唯一性,另一方面它可以给每个 value 赋予一个 score,代表这个 value 的排序权重。

zset的底层是由字典和跳表实现。

字典主要用来存储value和score的对应关系。跳表这个数据结构主要用来提供zset按照score排序的功能、指定score范围获取value列表的功能。

struct zset {dict *dict; // all values   value=>scorezskiplist *zsl;  
}

跳表

跳表数据结构包含的属性:

  1. header:表示kv head的地址
  2. maxLevel:最高层级
struct zskiplist {zslnode* header; // 跳跃列表头指针int maxLevel; // 跳跃列表当前的最高层map<string, zslnode*> ht; // hash 结构的所有键值对  
}

以下就是跳表的示意图:

每一个kv按照score有序排列的,不同的 kv 层高可能不一样,层数越高的 kv 越少。也就是不同 kv 的level[ ]长度不一样。同一层的 kv 会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。

为什么需要这么设计呢?如果只有一层,也就是一个双链表,所有元素按照score排序,我们如果想要快速定位到某个score,我们就需要从头指针依次遍历,时间复杂度为O(n)。如果我们设计成跳表这个多层结构,效果类似于二分查找,时间复杂度为O(lg(n))。

在这里插入图片描述

每一个结点包含的属性如下:

struct zslnode {string value;double score;zslforward*[] level; // 多层连接指针zslnode* backward; // 回溯指针
}
struct zslforward {zslnode* forward;long span; // 跨度
}

查找

如果当前节点的下一个节点包含的值比目标元素值小,则继续向右查找。如果下一个节点的值比目标值大,就转到当前层的下一层去查找。

在这里插入图片描述

比如说要查找21,当查找到6这个结点时,6比21小,继续向右查找,因为此时在6结点level[3],level[3]的下一个结点是nil,不符合,那么就转到6的level[2],level[2]的下一个结点是(6->level[2].forward)25,比目标值大,继续转到6的level[1],level[1]的下一个结点是9,9比21小,继续向右查找……

注意: zset 的排序元素不只看 score 值,如果score 值相同还需要再比较 value 值 (字符串比较)。为了防止如果每个元素的score值都相同的话,查找时间复杂度变成O(n)。

插入

当客户端使用 zset add 命令时,redis底层插入元素的过程:

在这里插入图片描述

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {// 存储搜索路径zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;// 存储经过的节点跨度unsigned int rank[ZSKIPLIST_MAXLEVEL];int i, level;serverAssert(!isnan(score));x = zsl->header;// 逐步降级寻找目标节点,得到「搜索路径」for (i = zsl->level-1; i >= 0; i--) {rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];while (x->level[i].forward &&(x->level[i].forward->score < score ||(x->level[i].forward->score == score &&compareStringObjects(x->level[i].forward->obj,obj) < 0))) {// 累计搜索路径中经过各结点的跨度。也就是最后查询到的元素的rank值。rank[i] += x->level[i].span;x = x->level[i].forward;}update[i] = x;}/**正式进入插入过程**/// 随机一个层数level = zslRandomLevel();if (level > zsl->level) {for (i = zsl->level; i < level; i++) {rank[i] = 0;update[i] = zsl->header;update[i]->level[i].span = zsl->length;}zsl->level = level;}// 创建新节点x = zslCreateNode(level,score,obj);// 重排一下前向指针for (i = 0; i < level; i++) {x->level[i].forward = update[i]->level[i].forward;update[i]->level[i].forward = x;x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);update[i]->level[i].span = (rank[0] - rank[i]) + 1;}for (i = level; i < zsl->level; i++) {update[i]->level[i].span++;}// 重排一下后向指针x->backward = (update[0] == zsl->header) ? NULL : update[0];if (x->level[0].forward)x->level[0].forward->backward = x;elsezsl->tail = x;zsl->length++;return x;
}
  • 通过 kv head 这个结点获得最高层的结点地址。
  • 逐层降级寻找目标结点,所经过的结点存储在搜索路径update[]数组中。
  • 创建一个新结点。
  • 为这个结点算一个随机层数,表示这个结点的level[]最大是第几层。
  • 遍历update数组,为这个新创建的结点的每层level设置好前后指针。

删除

删除过程和插入过程类似,都需先把这个「搜索路径」找出来。然后对于每个层的相关节点都重排一下前向后向指针就可以了。同时还要注意更新一下最高层数 maxLevel。

更新

当我们调用 zadd 方法时,如果对应的 value 不存在,那就是【插入过程】。

如果这个value 已经存在了,只是调整一下 score 的值,

  1. 假设这个新的score 值不会带来排序位置上的改变,那么就不需要调整位置,直接修改元素的 score 值就可以了。
  2. 如果新的score值让排序位置改变了,那就要调整位置。如何调整位置?直接将这个元素删了,然后插入。这一点可以优化,因为如果直接删,然后再插入,需要两次路径搜索,对于改变score值后仍不需要调整位置的情况就可以优化。

字典

dict数据结构可以应用在:

  • hash 结构的数据
  • 整个 Redis 数据库的所有 key 和 value
  • 带过期时间的 key 集合
  • zset 集合中存储 value 和 score 值的映射关系
struct RedisDb {dict* dict; // all keys key=>valuedict* expires; // all expired keys key=>long(timestamp)
}
struct zset {dict *dict; // all values value=>scorezskiplist *zsl;
}

dict数据结构包含的属性:

struct dict {...dictht ht[2]; // 两个dictht结构,也就是两个hashtable
}
struct dictht {dictEntry** table; // 二维,第一维是数组,第二维是链表。数组中存储的是第二维链表的第一个元素的指针。long size; // 第一维数组的长度long used; // hash 表中的元素个数...
}
struct dictEntry {void* key;void* val;dictEntry* next; // 链接下一个 entry
}

rehash

rehash条件:

Dict在每次新增键值对时都会检查负载因子(LoadFactor = used/size) ,满足以下两种情况时会触发哈希表扩容
哈希表的 LoadFactor >= 1,并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程;
哈希表的 LoadFactor > 5 ;

rehash过程:(渐进式rehash)

  • 计算新hash表的realeSize,值取决于当前要做的是扩容还是收缩:

    • 如果是扩容,则新size为第一个大于等于dict.ht[0].used + 1的2^n
    • 如果是收缩,则新size为第一个大于等于dict.ht[0].used的2^n (不得小于4)
  • 按照新的realeSize申请内存空间,创建dictht,并赋值给dict.ht[1]

  • 设置dict.rehashidx = 0,标示开始rehash

  • 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1](注意,这里不是一次性就将所有entry移到ht[1]中。)

    每次执行新增、查询、修改、删除操作时,都检查一下dict.rehashidx是否大于-1,如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1],并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]。—渐进式哈希

  • 将dict.ht[1]赋值给dict.ht[0],给dict.ht[1]初始化为空哈希表,释放原来的dict.ht[0]的内存。

  • 将rehashidx赋值为-1,代表rehash结束。

  • 在rehash过程中,新增操作,则直接写入ht[1],查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增,随着rehash最终为空。

rehash时机:

rehash将ht[0]的数据搬迁到ht[1]是在客户端执行命令中时发生的。也就是渐进性哈希。如果客户端闲下来,redis则通过定时任务对字典进行搬迁。

string

Redis 中的字符串是可以修改的字符串,在内存中它是以字节数组的形式存在的。这个字符串叫「SDS」,也就是 Simple Dynamic String。它的结构是一个带长度信息的字节数组。

SDS

struct SDS<T> {T capacity; // 数组容量T len; // 数组长度byte flags; // 特殊标识位,不理睬它byte[] content; // 数组内容
}

在这里插入图片描述

如上图所示,capacity 表示所分配数组的长度,len 表示字符串的实际长度。

embstr vs raw

Redis 的字符串有两种存储方式,在长度特别短时,使用 emb 形式存储 (embeded),当长度超过 44 时,使用 raw 形式存储。

所有redis对象都有下面这个结构头,包括我们现在研究的SDS对象也会有这个对象头。

struct RedisObject {int4 type; // 4bits   不同的对象具有不同的类型int4 encoding; // 4bits   同一个类型的 type 会有不同的存储形式encoding(4bit),int24 lru; // 24bits   int32 refcount; // 4bytes   每个对象都有个引用计数,当引用计数为零时,对象就会被销毁,内存被回收。void *ptr; // 8bytes,64-bit system   ptr 指针将指向对象内容 (body) 的具体存储位置。
} robj;

这样一个 RedisObject 对象头需要占据 16 字节的存储空间。

我们再看 SDS 结构体的大小:

struct SDS {int8 capacity; // 1byteint8 len; // 1byteint8 flags; // 1bytebyte[] content; // 内联数组,长度为 capacity
}

一个SDS对象头至少是3字节,那么一整个SDS对象至少是3+16=19字节,也就是说分配一个字符串最小空间占用为19字节。

在这里插入图片描述

  • embstr 存储形式将 RedisObject 对象头和 SDS 对象连续存在一起,使用 malloc 方法一次分配。
  • raw 存储形式需要两次malloc,两个对象头在内存地址上一般是不连续的。

内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等,为了能容纳一个完整的 embstr 对象,**jemalloc 最少会分配 32 字节的空间,如果字符串再稍微长一点,那就是 64 字节的空间。**如果总体超出了 64 字节,Redis 认为它是一个大字符串,不再使用 emdstr 形式存储,而该用 raw 形式。

也就是如果分配的是64字节的空间,那么扣掉SDS对象头和redis对象头,剩下64 - 19 = 45字节给字符串,而字符串是以字节\0 结尾的,因此字符串长度最大为44字节,如果超过44字节,那么用raw形式存储。

oc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等,为了能容纳一个完整的 embstr 对象,**jemalloc 最少会分配 32 字节的空间,如果字符串再稍微长一点,那就是 64 字节的空间。**如果总体超出了 64 字节,Redis 认为它是一个大字符串,不再使用 emdstr 形式存储,而该用 raw 形式。

也就是如果分配的是64字节的空间,那么扣掉SDS对象头和redis对象头,剩下64 - 19 = 45字节给字符串,而字符串是以字节\0 结尾的,因此字符串长度最大为44字节,如果超过44字节,那么用raw形式存储。

参考

《Redis深度历险:核心原理和应用实践》
https://www.jianshu.com/p/09c3b0835ba6

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/467225.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

day20-21之间的项目实战:若依ruoyi开发(可以跳过)

一&#xff0c;项目概述 官网文档地址&#xff1a;http://doc.ruoyi.vip/ rouyi是一个后台管理系统&#xff0c;基于经典技术组合&#xff08;spring boot&#xff0c;apache shiro&#xff0c;mybatis&#xff0c;thymeleaf&#xff09;主要是让开发者注重专注业务&#xff0…

【Android】名不符实的Window类

1.“名不符实”的Window类 Window 是一个窗口的概念&#xff0c;是所有视图的载体&#xff0c;不管是 Activity&#xff0c;Dialog&#xff0c;还是 Toast&#xff0c;他们的视图都是附加在 Window 上面的。例如在桌面显示一个悬浮窗&#xff0c;就需要用到 Window 来实现。Wi…

SDL事件相关

文章目录 事件相关的函数和数据结构用户自定义事件代码相关&#xff1a; 事件相关的函数和数据结构 SDL_WaitEvent :等待一个事件SDL_PushEvent 发送一个事件SDL_PumpEvents(): 将硬件设备产生的时间放入事件队列 &#xff0c;用于读取事件&#xff0c;在调用该函数之前&#…

机器人课程——使用TIA Portal V15博图软件进行西门子组态——带显示屏

一.打开TIA Portal V15博图软件创建项目 1.选择创建新项目 创建完成后选择PLC 二.创建完成后选择设备PLC (此处以S7-1200 1214FC DC/DC/DC 为例) 三.添加扩展板&#xff08;如有——这里以223-1BL32-0XB0为例&#xff09; 四.更改扩展版地址 五.添加触摸屏&#xff08;这里以…

【数据集】【YOLO】【目标检测】道路结冰数据集 1527 张,YOLO目标检测实战训练教程!

数据集介绍 【数据集】道路结冰数据集 1527 张&#xff0c;目标检测&#xff0c;包含YOLO/VOC格式标注。数据集中包含2种分类&#xff1a;“clear_road, ice_road”。数据集来自国内外图片网站和视频截图&#xff0c;部分数据经过数据增强处理。检测范围监控视角检测、无人机视…

【Mysql NDB Cluster 集群(CentOS 7)安装笔记一】

Mysql NDB Cluster 集群(CentOS 7)安装笔记 NDB集群核心概念 NDBCLUSTER(也称为NDB)是一个内存存储引擎,提供高可用性和数据保存功能。 NDBCLUSTER存储引擎可以配置一系列故障转移和负载平衡选项,但从集群级别的存储引擎开始是最容易的。NDB集群的NDB存储引擎包含一整套…

利用京东API接口实现商品详情数据获取与表格化展示

在电商数据分析与运营过程中&#xff0c;获取商品详情数据是至关重要的一环。京东作为国内领先的电商平台&#xff0c;其开放平台提供了丰富的API接口&#xff0c;使得开发者能够高效地获取商品信息。本文将详细介绍如何通过京东API接口获取商品详情数据&#xff0c;并将其整理…

数据结构-并查集专题(1)

一、前言 因为要开始准备年底的校赛和明年年初的ACM、蓝桥杯、天梯赛&#xff0c;于是开始按专题梳理一下对应的知识点&#xff0c;先从简单入门又值得记录的内容开始&#xff0c;并查集首当其冲。 二、我的模板 虽然说是借用了jiangly鸽鸽的板子&#xff0c;但是自己也小做…

博奥龙/诊断原料抗体对

在ELISA中&#xff0c;抗体与抗原的结合精确度依赖于抗体的特异性和灵敏度。特异性较差的抗体可能导致显著的非特异性背景信号&#xff0c;而特异好但亲和力弱的抗体可能会被洗掉&#xff0c;从而产生假阴性数据。因此&#xff0c;选择合适的可避免交叉反应和确保检测结果的准确…

OceanBase详解及如何通过MySQL的lib库进行连接

OceanBase详解及如何通过MySQL的lib库进行连接 一、引言二、OceanBase概述1. 起源与发展2. 核心技术特点3. 应用场景三、OceanBase架构解析1. 系统架构2. 存储引擎3. 分布式架构四、如何使用MySQL的lib库连接OceanBase1. 前提条件2. 安装MySQL Connector/C3. 编写连接代码4. 编…

java导出word文件(手绘)

文章目录 代码细节效果图参考资料 代码细节 使用的hutool的WordUtil&#xff0c;WordUtil对poi进行封装&#xff0c;但是这一块的官方封装的很少&#xff0c;很多细节都没有。代码中是常见的绘制段落&#xff0c;标题、表格等常用api Word07Writer writer WordUtil.getWriter(…

RNN(循环神经网络)详解

1️⃣ RNN介绍 前馈神经网络&#xff08;CNN&#xff0c;全连接网络&#xff09;的流程是前向传播、反向传播和参数更新&#xff0c;存在以下不足&#xff1a; 无法处理时序数据&#xff1a;时序数据长度一般不固定&#xff0c;而前馈神经网络要求输入和输出的维度是固定的&a…

qt QHttpMultiPart详解

1. 概述 QHttpMultiPart是Qt框架中用于处理HTTP多部分请求的类。它类似于RFC 2046中描述的MIME multipart消息&#xff0c;允许在单个HTTP请求中包含多个数据部分&#xff0c;如文件、文本等。这种多部分请求在上传文件或发送带有附件的邮件等场景中非常有用。QHttpMultiPart类…

2-148 基于matlab的铣削动力学仿真

基于matlab的铣削动力学仿真&#xff0c;推导出指导加工的稳定性叶瓣图&#xff0c;并得到各主轴转速下对应的极限切深。输入不同方向刚度和切入角、切削力系数等参数&#xff0c;进行铣削动力学仿真。程序已调通&#xff0c;可直接运行。 下载源程序请点链接&#xff1a;2-14…

使用STM32F407xx的GPIO引脚实现跑马灯效果的详细步骤

1、使用Keil创建一个新工程 2、在弹出的对话框&#xff0c;填写工程的名字&#xff0c;例如工程名字为demo_led 3、为保存的工程&#xff0c;选择对应的芯片 4、为当前工程&#xff0c;添加相应的库函数 5、若库函数添加成功&#xff0c;则显示当前工程目录树 6、在当前工程目录…

_浅谈单片机的gcc优化级别__以双音频信号发生器为例

一、简介 gcc有多种优化级别&#xff0c;一般不选择的情况下&#xff0c;IDE默认是按照-Og或这-O2优化的。 以gcc编译器为例&#xff0c;浅谈一下优化级别&#xff0c;我们常见的优化一般是指gcc的-O2、-Og。除此之外&#xff0c;gcc还有-Os等一系列优化&#xff0c;链接器也有…

用JavaScript、Nodejs写一个本地tcp服务,用于前端WebSocket调试

效果&#xff1a; 准备工作&#xff1a; 新建一个文件夹&#xff0c;在根目录安装依赖&#xff1a; npm install ws express 依赖介绍&#xff1a; WS是一个轻量级、高效的WebSocket库&#xff0c;适用于Node.js环境。 express 是一个流行的Node.js Web应用程序框架。 新…

企业常见的主数据管理挑战及解决方案

在当今高度数字化的商业环境中&#xff0c;数据已成为企业决策、运营和战略规划的核心。主数据管理&#xff08;MDM&#xff09;作为管理核心业务数据的一种方式&#xff0c;帮助企业确保其关键数据在整个组织中保持一致、准确和可信。然而&#xff0c;许多企业在实施主数据管理…

Python http打印(http打印body)flask demo(http调试demo、http demo、http printer)

文章目录 代码解释 代码 # flask_http_printer.pyfrom flask import Flask, request, jsonify import jsonapp Flask(__name__)app.route(/printinfo, methods[POST]) def print_info():# 分隔符separator "-" * 60# 获取请求头headers request.headers# 获取 JS…

从无音响Windows 端到 有音响macOS 端实时音频传输播放

以下是从 Windows 端到 macOS 端传输音频的优化方案&#xff0c;基于上述链接中的思路进行调整&#xff1a; Windows 端操作 安装必要软件 安装 Python&#xff08;确保版本兼容且已正确配置环境变量&#xff09;。安装 PyAudio 库&#xff0c;可通过 pip install pyaudio 命令…