【2.22】MySQL、Redis、动态规划
认识Redis
-
Redis是一种基于内存的数据库,对数据的读写操作都是在内存中完成的,因此读写速度非常快,常用于缓存,消息队列,分布式锁等场景。
-
Redis提供了多种数据类型来支持不同的业务场景,比如String(字符串)、Hash(哈希)、 List (列表)、Set(集合)、Zset(有序集合),并且对数据类型的操作都是原子性的。
- 原子性:因为Redis是单线程的,不存在并发竞争问题。
-
除此之外,Redis 还支持事务 、持久化、Lua 脚本、多种集群方案(主从复制模式、哨兵模式、切片机群模式)、发布/订阅模式,内存淘汰机制、过期删除机制等等。
Redis和Memcached有什么区别?
-
相同点
- 都是基于内存的数据库,一般都用来当做缓存使用。
- 都有过期策略
- 两者的性能都非常高。
-
区别
-
Redis的数据结构更加丰富,Memcached只支持key-value数据类型;
-
Redis 支持数据的持久化,可以将内存中的数据保持在磁盘中,重启的时候可以再次加载进行使用,而 Memcached 没有持久化功能,数据全部存在内存之中,Memcached 重启或者挂掉后,数据就没了;
-
Redis 原生支持集群模式,Memcached 没有原生的集群模式,需要依靠客户端来实现往集群中分片写入数据;
-
Redis 支持发布订阅模型、Lua 脚本、事务等功能,而 Memcached 不支持;
-
为什么用Redis作为MySQL的缓存?
-
主要是因为Redis 具备「高性能」和「高并发」两种特性。
-
假如用户第一次访问 MySQL 中的某些数据。这个过程会比较慢,因为是从硬盘上读取的。将该用户访问的数据缓存在 Redis 中,这样下一次再访问这些数据的时候就可以直接从缓存中获取了,操作 Redis 缓存就是直接操作内存,所以速度相当快。
-
单台设备的 Redis 的 QPS(Query Per Second,每秒钟处理完请求的次数) 是 MySQL 的 10 倍,Redis 单机的 QPS 能轻松破 10w,而 MySQL 单机的 QPS 很难破 1w。直接访问 Redis 能够承受的请求是远远大于直接访问 MySQL 的,所以我们可以考虑把数据库中的部分数据转移到缓存中去,这样用户的一部分请求会直接到缓存这里而不用经过数据库。
-
从数据页的角度看B + 树
InnoDB是如何存储数据的?
- InnoDB的数据是按照数据页为单位来读写的,默认的大小是16KB。
- 数据页由以下七个部分组成:File Header文件头、Page Header页头、UserRecords用户空间 、Infimum + Supermum最大 + 最小记录、Free + Space空闲空间、PageDirectory页目录、File Trailer文件尾。
- 数据页中的文件头有两个指针,分别指向上一个和下一个数据页。连接起来的数据页相当于一个双向链表。实现逻辑上的连续存储。数据页中的记录按照主键的顺序组成单向链表。
- 数据页中的页目录起到记录的索引作用。页目录由多个槽组成,槽相当于分组记录的索引。我们通过槽查找记录时,可以使用二分法快速定位要查询的记录在哪个槽(哪个记录分组),定位到槽后,再遍历槽内的所有记录,找到对应的记录,槽对应的值都是这个组的主键最大的记录。
- 在页的 7 个组成部分中,我们自己存储的记录会按照我们指定的行格式存储到
User Records
部分。一开始生成页的时候,并没有 User Records 这个部分,每当我们插入一条记录,都会从 Free Space 部分申请一个记录大小的空间划分到 User Records 部分。当 Free Space 部分的空间全部被 User Records 部分替代掉之后,也就意味着这个页使用完了,如果还有新的记录插入的话,就需要去申请新的页了。
B + 树是如何进行查询的?
-
B + 树的每个节点都是一个数据页。B + 树只有叶子节点才会存放数据,非叶子节点仅用来存放目录项作为索引。所有节点按照索引键大小排序,构成双向链表,便于范围查找。
-
定位记录所在哪一个页时,B + 树通过二分法快速定位到包含该记录的页。定位到该页后,又会在该页内进行二分法快速定位记录所在的分组(槽号),最后在分组内进行遍历查找。
-
索引又可以分成聚簇索引和非聚簇索引(二级索引),它们区别就在于叶子节点存放的是什么数据:
-
聚簇索引的叶子节点存放的是实际数据,所有完整的用户记录都存放在聚簇索引的叶子节点;
- 因为表的数据都是存放在聚簇索引的叶子节点里,所以 InnoDB 存储引擎一定会为表创建一个聚簇索引,且由于数据在物理上只会保存一份,所以聚簇索引只能有一个
- InnoDB 在创建聚簇索引时,会根据不同的场景选择不同的列作为索引:
- 如果有主键,默认会使用主键作为聚簇索引的索引键;
- 如果没有主键,就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键;
- 在上面两个都没有的情况下,InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键;
-
二级索引的叶子节点存放的是主键值,而不是实际数据。
- 一张表只能有一个聚簇索引,那为了实现非主键字段的快速搜索,就引出了二级索引(非聚簇索引/辅助索引),它也是利用了 B+ 树的数据结构,但是二级索引的叶子节点存放的是主键值,不是实际数据。
-
为什么MySQL采用B + 树作为索引?
怎样的索引的数据结构是好的?
- MySQL的数据是持久化的,保存在磁盘上。磁盘读写的最小单位是扇区,扇区只有512B大小,操作系统会读写多个扇区,最小的读取单位是块。Linux中块的大小为4KB,也就是8个扇区。由于数据库的索引是保存在磁盘上的,所以查询数据时,要先读取索引到内存,通过索引找到磁盘中的某行数据,然后读入到内存,I/O操作次数越多,所消耗的时间也越大。所以设计MySQL索引的数据结构时,要尽可能减少磁盘I/O次数,并且能够高效地查找某一个记录,也要能高效的范围查找。
- 为什么不用二分查找树?
- 二叉查找树的特点是一个节点的左子树的所有节点都小于这个节点,右子树的所有节点都大于这个节点,搜索速度块,解决了插入新节点的问题,但是当每次插入的元素都是二叉查找树中最大的元素,二叉查找树就会退化成了一条链表,查找数据的时间复杂度变成了 O(n)。
- 随着插入元素越多,树的高度也就越高,磁盘IO操作也就越多,查询性能严重下降。
- 为什么不用自平衡二叉树(AVL树)?
- 自平衡二叉树在二叉查找树的基础上增加了一些条件约束:每个节点的左子树和右子树的高度差不能超过 1。但是随着插入的元素变多,会导致树的高度变高,磁盘IO操作次数就会变多,影响整体数据查询效率。
- 为什么不用B树?
- B树解决了树的高度问题,但是B树的每个节点都包含数据(索引+记录),而用户记录的数据大小有可能远远超过索引数据,就要花费更多的IO来读取到有用的索引数据。
- B + 树
- B + 树对B树进行了升级,与B树的区别主要是以下几点:
- 叶子节点(最底部的节点)才会存放实际数据(索引+记录),非叶子节点只会存放索引;
- 所有索引都会在叶子节点出现,叶子节点之间构成一个有序链表;
- 非叶子节点的索引也会同时存在在子节点中,并且是在子节点中所有索引的最大(或最小)。
- 非叶子节点中有多少个子节点,就有多少个索引;
- B树进行单个索引查询时,最快可以在O(1)的时间内就找到,平均时间会比B + 树快,但是B+ 树的非叶子节点不存放实际的记录数据,仅存放索引,因此数据量相同的情况下,相比既存索引又存记录的 B 树,B+树的非叶子节点可以存放更多的索引,因此 B+ 树可以比 B 树更「矮胖」,查询底层节点的磁盘 I/O次数会更少。
- B+ 树有大量的冗余节点,这样使得删除一个节点的时候,可以直接从叶子节点中删除,甚至可以不动非叶子节点,这样删除非常快,B树没有冗余节点,在删除节点时,可能涉及到复杂的树的变化。
- B+ 树所有叶子节点间还有一个链表进行连接,这种设计对范围查找非常有帮助
- B + 树对B树进行了升级,与B树的区别主要是以下几点:
MySQL中的B + 树
- Innodb 使用的 B+ 树有一些特别的点,比如:
- B+ 树的叶子节点之间是用「双向链表」进行连接,这样的好处是既能向右遍历,也能向左遍历。
- B+ 树点节点内容是数据页,数据页里存放了用户的记录以及各种信息,每个数据页默认大小是 16 KB。
- Innodb 根据索引类型不同,分为聚集和二级索引。他们区别在于,聚集索引的叶子节点存放的是实际数据,所有完整的用户记录都存放在聚集索引的叶子节点,而二级索引的叶子节点存放的是主键值,而不是实际数据。
总结
- MySQL 默认的存储引擎 InnoDB 采用的是 B+ 树作为索引的数据结构,原因有:
- B+ 树的非叶子节点不存放实际的记录数据,仅存放索引,因此数据量相同的情况下,相比存储即存索引又存记录的 B 树,B+树的非叶子节点可以存放更多的索引,因此 B+ 树可以比 B 树更「矮胖」,查询底层节点的磁盘 I/O次数会更少。
- B+ 树有大量的冗余节点(所有非叶子节点都是冗余索引),这些冗余索引让 B+ 树在插入、删除的效率都更高,比如删除根节点的时候,不会像 B 树那样会发生复杂的树的变化;
- B+ 树叶子节点之间用链表连接了起来,有利于范围查询,而 B 树要实现范围查询,因此只能通过树的遍历来完成范围查询,这会涉及多个节点的磁盘 I/O 操作,范围查询效率不如 B+ 树。
动态规划
LeetCode
-
leetcode 518
注意,该题是求组合数,所以用递推公式:
dp[j] += dp[j - coins[i]]
。在求装满背包有几种方案的时候,难点在于遍历顺序:
如果求组合数就是外层for循环遍历物品,内层for遍历背包。(正常遍历顺序,组合数不分数字先后)
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
class Solution {public int change(int amount, int[] coins) {int n = coins.length;int dp [] = new int [amount + 1];dp[0] = 1;for(int i = 0 ;i < n;i ++){for(int j = coins[i]; j <= amount; j ++){dp[j] += dp[j - coins[i]];}}return dp[amount];} }
-
leetcode377
class Solution {public int combinationSum4(int[] nums, int target) {//dp[j]的含义:当总和为j时的组合数个数。//由于顺序不同的序列被视作不同的组合。所以先遍历容量,后遍历物品。int dp [] = new int [target + 1];dp[0] = 1;for(int j = 0; j <= target ; j++){for(int i = 0 ; i < nums.length ; i ++){if(j >= nums[i]){dp[j] += dp[j - nums[i]];}}}return dp[target];} }
-
leetcode322
class Solution {public int coinChange(int[] coins, int amount) {//每种硬币无限,完全背包问题。//coins[i]为物品,coins[i]同时也表示重量。//dp[j]: 凑整j的最少硬币个数。 对于dp[j]来说,每个硬币的价值为1。//先遍历物品,再遍历背包。int dp [] = new int [amount + 1];for(int i = 0 ; i < dp.length; i ++){dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for(int i = 0; i < coins.length; i ++){for(int j = coins[i]; j <= amount ; j ++){if(dp[j - coins[i]] != Integer.MAX_VALUE)dp[j] = Math.min(dp[j] , dp[j - coins[i]] + 1);}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];} }
-
leetcode279
完全平方数的大小不可能超过n,所以
i* i <= n
。同理,背包的容量也不会超过n。class Solution {public int numSquares(int n) {//完全平方数就是i * i。int dp [] = new int [n + 1];int max = Integer.MAX_VALUE;for(int i = 0 ; i < dp.length ; i++){dp[i] = max;}dp[0] = 0;for(int i = 1; i * i <= n ; i ++){ //先遍历物品for(int j = i * i ; j <= n ; j ++){ //再遍历背包 dp[j] = Math.min(dp[j] , dp[j - i * i] + 1);}}return dp[n];} }
相关文章:
【2.22】MySQL、Redis、动态规划
认识Redis Redis是一种基于内存的数据库,对数据的读写操作都是在内存中完成的,因此读写速度非常快,常用于缓存,消息队列,分布式锁等场景。 Redis提供了多种数据类型来支持不同的业务场景,比如String(字符串…...

2年手动测试,裸辞后找不到工作怎么办?
我们可以从以下几个方面来具体分析下,想通了,理解透了,才能更好的利用资源提升自己。一、我会什么?先说第一个我会什么?第一反应:我只会功能测试,在之前的4年的中我只做了功能测试。内心存在一种…...

Leetcode6. N字形变换
一、题目描述: 将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下: 之后,你的输出需要从左往右逐行读取,产…...
将Nginx 核心知识点扒了个底朝天(十)
ngx_http_upstream_module的作用是什么? ngx_http_upstream_module用于定义可通过fastcgi传递、proxy传递、uwsgi传递、memcached传递和scgi传递指令来引用的服务器组。 什么是C10K问题? C10K问题是指无法同时处理大量客户端(10,000)的网络套接字。 Nginx是否支持将请求压…...
GPU显卡环境配置安装
前言 最近公司购买了一张RTX3090的显卡和一台新的服务器,然后对机器的GPU环境进行了安装和配置,然后简单记录一下 环境版本 操作系统:Centos7.8 显卡型号:RTX3090 Python版本:3.7.6 Tensorflow版本:2…...

CIMCAI super unmanned intelligent gate container damage detect
世界港航人工智能领军者企业CIMCAI中集飞瞳打造全球最先进超级智能闸口无人闸口ceaspectusG™视频流动态感知集装箱箱况残损检测箱况残损识别率99%以上,箱信息识别率99.95%以上World port shipping AI leader CIMCAIThe worlds most advanced super intelligent gat…...
web概念概述
软件架构:1. C/S: Client/Server 客户端/服务器端* 在用户本地有一个客户端程序,在远程有一个服务器端程序* 如:QQ,迅雷...* 优点:1. 用户体验好* 缺点:1. 开发、安装,部署,维护 麻烦…...

编译原理笔记(1)绪论
文章目录1.什么是编译2.编译系统的结构3.词法分析概述4.语法分析概述5.语义分析概述6.中间代码生成和后端概述1.什么是编译 编译的定义:将高级语言翻译成汇编语言或机器语言的过程。前者称为源语言,后者称为目标语言。 高级语言源程序的处理过程&#…...
MySQL(八)
服务器参数设置 general datadir/var/lib/mysql 数据文件存放的目录socket/var/lib/mysql/mysql.sock mysql.socket表示server和client在同一台服务器,并且使用localhost进行连接,就会使用socket进行连接pid_file/var/lib/mysql/mysql.pid 存储mysql的p…...

steam搬砖项目,小投入高回报,可放大操作,(内附教学资料)
我必须要说,steam搬砖项目就是全网门槛最低的副业,有手就行! 本人90后底层员工一枚,新入csgo搬砖项目,轻松翻身 什么做抖音、海外问卷、直播卖货,电商等等对比我这个都是小钱。我这个方法是利用了大部分人…...
华为OD机试真题Python实现【最多提取子串数目】真题+解题思路+代码(20222023)
最多提取子串数目 题目 给定由 [a-z] 26 个英文小写字母组成的字符串 A 和 B,其中 A 中可能存在重复字母,B 中不会存在重复字母 现从字符串 A 中按规则挑选一些字母,可以组成字符串 B。 挑选规则如下: 1) 同一个位置的字母只能被挑选一次 2) 被挑选字母的相对先后顺序不…...

day32 多线程(上)
文章目录相关概念codeThreadTest01ThreadTest02 编写一个类,直接继承java.lang.Thread,重写run方法ThreadTest03 实现线程的第二种方法ThreadTest04 采用匿名内部类的方式ThreadTest05 获取线程名字ThreadTest06 sleep方法sleep面试题ThreadTest08 终止线…...
【flink】 各种join类型对比
表定义 动态表(dynamic table):动态表是流的另一种表达方式,动态表作为一个逻辑的抽象概念,使我们更容易理解flink中将streaming发展到table这个层次的设计,本质都是对无边界、持续变更数据的表示形式,所以动态表与流之…...
常用正则表达式
一、校验数字的表达式 数字:^[0-9]*$ n位的数字:^\d{n}$ 至少n位的数字:^\d{n,}$ m-n位的数字:^\d{m,n}$ 零和非零开头的数字:^(0|[1-9][0-9]*)$ 非零开头的最多带两位小数的数字:^([1-9][0-9]*)(.[0…...

PMP考试有没有什么技巧可以介绍一下么?
一、试题形式 ——中英文对照 即每道题都是一遍英文,一遍翻译的中文,在审题的时候有一些小的技巧需要注意。首先如果你的英文水平足够好,建议直接阅读原文。PMP试题毕竟是美国人出的,语言的组织、思想的表达,肯定更符…...

2022-2023年营销报告(B站平台) | 5大行业势态、流量大盘全景洞察
一直以来,手持高活跃、高粘性用户群体的B站是行业用来观察年轻人消费习惯的重要平台。以至于用户群体的不断壮大带动了B站的商业价值。如今B站的商业舞台越来越大,不断地向外界招手,欢迎更多品牌积极加入到这个千万年轻人聚集的内容社区。为了…...
Python的异常与工具包
异常 当检测到一个错误时,python解释器就无法继续执行了,反而出现了一些错误的提示,这就是所谓的异常。 捕获异常 世界上没有完美的程序,任何程序在运行的过程中,都有可能出现异常,导致程序无法完美运行…...

基于SSM的婴幼儿商城
基于SSM的婴幼儿商城 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取项目下载方式🍅 一、项目背景介绍: …...

2023年新能源汽车行业研究报告
第一章 行业概况 新能源汽车,是指采用新型动力系统,完全或者主要依靠新型能源驱动的汽车,包括纯电动汽车、插电式混合动力汽车、增程式混合动力汽车和燃料电池汽车等。国际上,混合动力汽车(含中混、强混、插电式混动&…...

手写Promise方法(直击Promise A+规范)
前言:大家好,我是前端獭子。高效优雅是我的创作方式。学习是一个渐进的过程,要把知识串联起来才能解决某一方面的问题。 Promise 构造函数 我们先来写 Promise 构造函数的属性和值,以及处理new Promise()时会传入的两个回调函数。…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...