MySQL:B+树索引
InnoDB索引方案
为了使用二分法快速定位具体的目录项,假设所有目录项都可以在物理存储器上连续存储,有以下问题:
- InnoDB使用页为管理存储空间的基本单位,最多只能保证16KB的连续存储空间,记录数据量多可能需要非常大的连续存储空间才能放下所有目录项
- 增删操作,如果把某页的记录都删除,则该页及目录项都没有存在的必要,如果要把后面的目录项都向前移,牵一发而动全身;如果不移动作为冗余放在目录项列表,浪费存储空间
复用存储用户记录的数据页来存储目录项,record_type=1标志目录项记录
目录项记录和普通用户记录的不同点
- 目录项记录record_type为1,普通用户记录的record_type为0
- 目录项记录只有主键值和页的编号两个列,普通用户记录的列由用户自己定义,可能包含多列,还有InnoDB自己添加的隐藏列
- 只有目录项记录的min_rec_flag属性为1,普通用户记录的min_rec_flag属性都是0
如果存储目录项的页也很多,则为这些存储目录项记录的页再生成一个更高级的目录
真正的用户记录都存放在B+树🌲的叶子节点上【第0层】
Page Header部分PAGE_LEVEL属性代表这个数据页作为节点在B+树中的层级
聚簇索引
B+树本身就是一个目录/一个索引,有以下两个特点:
- 使用记录主键值的大小进行记录和页的排序
- 页【包括叶子节点和内节点】内的记录按照主键的大小排序排成一个单向链表,页内的记录被划分成若干个组,每个组中主键值最大的记录在页内的偏移量会被当作槽依次放在页目录项中,可以在页目录中通过二分法快速定位到主键列等于某值的记录
- 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表
- 存放目录项记录的页分为不同的层级,在同一层级中的页也是根据页中目录项记录的主键大小排序排成一个双向链表
- B+树的叶子节点存储的是完整的用户记录【所有列的值,包括隐藏列】
在InnoDB存储引擎中,聚簇索引就是数据的存储方式【索引即数据,数据即索引】
二级索引
聚簇索引只能在搜索条件是主键值时才能发挥作用【B+树中的数据都是按照主键进行排序】
多建几颗B+树,不同的B+树中的数据采用不同的排序规则
与聚簇索引的不同:
- 使用记录c2列的大小进行记录和页的排序
- 页【包括叶子节点和内节点】内的记录是按照c2列的大小顺序排成的一个单向链表,页内的记录被划分成若干个组,每个组中c2列值最大的记录在页内的偏移量会被当作槽一次存放在页目录中
- 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成的一个双向链表
- 存放目录项记录的页分为不同的层级,在同一层级中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表
- B+树的叶子节点存储的不是完整的用户记录,而只是c2列+主键这两个列的值
- 目录项记录中不再是主键+页号的搭配,变成了c2列+页号的搭配
C2列并没有唯一性约束,也就是说满足搜索条件c2=4的记录可能有多条,只需要在该B+树的叶子节点处定位到第一条满足搜索条件c2=4的记录,然后沿着由记录组成的单向链表一直向后扫描即可**【页内的记录是按照c2列的大小顺序排成的一个单向链表】,各个叶子节点组成了双向链表**,搜索完了本页记录后可以跳到下一页面中第一条记录继续向后扫描
查找c2=4记录的过程:
- 确定第一条符合条件的目录项记录所在的页【定位到页42(2<4<9)】
- 通过第一条符合条件的目录项记录所在的页面确定第一条符合条件的用户记录所在的页【定位到第一条符合c2=4的用户记录所在页为34/35(2<4≤ 4)】
- 在真正存储第一条符合条件的用户记录的页中定位到具体的记录【如果在页34定位到第一条就不需要再到页35定位第一条记录】
- 这个B+树只记录了c2和主键两个列,在定位到第一条符合条件的用户记录后,需要根据该记录中的主键信息到聚簇索引中查找到完整的用户记录,这个通过携带主键信息到聚簇索引中重新定位完整记录的过程也称为回表,然后再返回到这颗B+树叶子节点处沿单向链表继续向后搜索其他满足条件的记录【找到一条就去聚簇索引找到完整记录】
因为需要回表才能获取完整的记录,这种B+树也称为二级索引/辅助索引
联合索引/复合索引/多列索引
可以同时以多个列的大小作为排序规则,即同时为多个列建立索引
- 每条目录项记录都由c2列、c3列、页号这三部分组成,记录先按c2列的值进行排序,c2相同的情况下再按照c3列的值进行排序
- B+树叶子节点处的用户记录由c2列、c3列和主键c1组成
本质上也是一个二级索引
InnoDB中B+树索引的注意事项
- 根页面万年不动窝【页号不再改变】【存簇索引根节点在某个页面,数据字典中的一项信息】
- 每当为某个表创建B+树索引【聚簇索引默认存在】时,就会为这个索引创建一个根节点页面,最开始表中没有数据的时候,每个B+树索引对应的根节点中既没有用户记录也没有目录项记录
- 向表中插入用户记录时,先把用户记录存储到这个根节点中
- 在根节点中可用空间用完时继续插入记录,1⃣️将根节点中所有记录复制到一个新分配的页a中,2⃣️对这个新页进行页分裂操作,3⃣️得到另一个新页b,新插入的记录会根据键值【主键值/二级索引对应的索引列值】的大小分配到页a/页b中,根节点升级为存储目录项记录的页,需要把页a和页b对应的目录项记录插入到根节点中【由空叶子节点形成树的过程】
- 内节点中目录项记录的唯一性
-
目录项记录的内容是索引列加页号的搭配,但对于二级索引来说不够严谨,为了让新插入的记录找到在哪个页,需要保证B+树同一层内节点的目录项记录除页号字段以外是唯一的【二级索引内节点的目录项记录的内容由:索引列的值、主键值、页号构成】
-
-
图6-16如果插入列值为1的记录,则该记录会找不到该往页4插还是页5
-
如图6-17,先把新记录的列值与页3各目录项记录的列值比较,如果列值相同,可以接着比较主键,B+树同一层中不同目录项记录的列值+主键的值肯定不同,最后肯定能定位到唯一一条目录项记录
-
对二级索引记录来说,先按二级索引列的值进行排序,如果列值相同的情况下,再按主键值排序,为c2列建立索引相当于为(c2,c1)列建立一个联合索引
-
对于唯一二级索引【当为某列或列组合声明UNIQUE属性时,便会为这个列或列组合建立唯一二级索引】来说,也可能会出现多条记录键值相同的情况【声明为UNIQUE属性的列可能存储多个NULL值;MVCC服务】,唯一二级索引的内节点的目录项记录也会包含记录的主键值
-
- 一个页面至少容纳2条记录
- InnoDB一个数据页至少可以存放2条记录,如果只能存放一条则目录层级会非常多,最后叶子节点也只有一条记录,效率大打折扣
- 如果B+树叶子节点只存储一条记录,内节点存储多条记录也是可以发挥B+树作用的,但是为了避免B+树层级增长过高,InnoDB要求所有数据页都至少可以容纳两条记录
相关文章:
MySQL:B+树索引
InnoDB索引方案 为了使用二分法快速定位具体的目录项,假设所有目录项都可以在物理存储器上连续存储,有以下问题: InnoDB使用页为管理存储空间的基本单位,最多只能保证16KB的连续存储空间,记录数据量多可能需要非常大…...
如何建立可复用的项目管理模板
建立可复用的项目管理模板能够显著提高项目执行效率、减少重复劳动、确保项目管理标准化。在企业中,项目管理往往涉及多个步骤和多个团队,然而每次开始一个新项目时,如果都从头开始设计流程和文档,势必浪费大量的时间和精力。通过…...
Go:goroutine 和通道
goroutine f() // 等待 f() 返回 go f() // 新建一个调用 f() 的 goroutine,不用等待在 Go 语言里,goroutine 是并发执行的活动单元。与顺序执行程序不同,在有多个 goroutine 的并发程序中,不同函数可同时执行。程序启动时&…...
盛水最多的容器问题详解:双指针法与暴力法的对比与实现
文章目录 问题描述方法探讨方法一:暴力法(Brute Force)思路代码实现复杂度分析 方法二:双指针法(Two Pointers)思路正确性证明代码实现复杂度分析 方法对比总结 摘要 盛水最多的容器(Container …...
VMWare 16 PRO 安装 Rocky8 并部署 MySQL8
VMWare 16 PRO 安装 Rocky8 并部署 MySQL8 一.Rocky OS 下载1.官网 二.配置 Rocky1.创建新的虚拟机2.稍后安装系统3.选择系统模板4.设置名字和位置5.设置大小6.自定义硬件设置核心、运存和系统镜像7.完成 三.启动安装1.上下键直接选择安装2.回车安装3.设置分区(默认…...
日常学习开发记录-slider组件
日常学习开发记录-slider组件 从零开始实现一个优雅的Slider滑块组件前言一、基础实现1. 组件结构设计2. 基础样式实现3. 基础交互实现 二、功能增强1. 添加拖动功能2. 支持范围选择3. 添加垂直模式 三、高级特性1. 键盘操作支持2. 禁用状态 五、使用示例六、总结 从零开始实现…...
AIDL 中如何传递 Parcelable 对象
目录 1. 直接在 AIDL 中定义 Parcelable 对象2. 自定义 Parcelable 对象的传递3. 以 Rect 类为例的 Parcelable 实现4. 注意安全性5. 小结1. 直接在 AIDL 中定义 Parcelable 对象 背景说明 从 Android 10(API 级别 29)开始,AIDL 允许直接在 .aidl 文件中定义 Parcelable 对…...
LVGL实战训练——计算器实现
目录 一、简介 二、部件知识 2.1 按钮矩阵部件(lv_btnmatrix) 2.1.1 按钮矩阵部件的组成 2.1.2 按钮文本设置 2.1.3 按钮索引 2.1.4 按钮宽度 2.1.5 按钮属性 2.1.6 按钮互斥 2.1.7 按钮文本重着色 2.1.8 按钮矩阵部件的事件 2.1.9 按钮矩阵部件的 API 函数 2.2…...
代码随想录算法训练营Day30
力扣452.用最少数量的箭引爆气球【medium】 力扣435.无重叠区间【medium】 力扣763.划分字母区间【medium】 力扣56.合并区间【medium】 一、力扣452.用最少数量的箭引爆气球【medium】 题目链接:力扣452.用最少数量的箭引爆气球 视频链接:代码随想录 题…...
AIDL 语言简介
目录 软件包类型注释导入AIDL 的后端AIDL 语言大致上基于 Java 语言。AIDL 文件不仅定义了接口本身,还会定义这个接口中用到的数据类型和常量。 软件包 每个 AIDL 文件都以一个可选软件包开头,该软件包与各个后端中的软件包名称相对应。软件包声明如下所示: package my.pac…...
经典算法 判断一个图中是否有环
判断一个图中是否有环 问题描述 给一个以0 0结尾的整数对列表,除0 0外的每两个整数表示一条连接了这两个节点的边。假设节点编号不超过100000大于0。你只要判断由这些节点和边构成的图中是否存在环。存在输出YES,不存在输出NO。 输入样例1 6 8 5 3 …...
Transformer-PyTorch实战项目——文本分类
Transformer-PyTorch实战项目——文本分类 ———————————————————————————————————————————— 【前言】 这篇文章将带领大家使用Hugging Face里的模型进行微调,并运用在我们自己的新项目——文本分类中。需要大家提前下…...
Linux-服务器负载评估方法
在 Linux 服务器中,top 命令显示的 load average(平均负载)反映了系统在特定时间段内的负载情况。它通常显示为三个数值,分别代表过去 1 分钟、5 分钟和 15 分钟的平均负载。 1. 什么是 Load Average? Load average …...
Transformer编程题目,结合RTX 3060显卡性能和市场主流技术
以下是10道针对4年经验开发者的Transformer编程题目,结合RTX 3060显卡性能和市场主流技术,每题包含模型选择和实现逻辑描述: 题目1:医疗报告结构化提取 模型选择:BioBERT-base 要求: 开发从PDF医疗报告中提…...
Web三漏洞学习(其二:sql注入)
靶场:NSSCTF 、云曦历年考核题 二、sql注入 NSSCTF 【SWPUCTF 2021 新生赛】easy_sql 这题虽然之前做过,但为了学习sql,整理一下就再写一次 打开以后是杰哥的界面 注意到html网页标题的名称是 “参数是wllm” 那就传参数值试一试 首先判…...
VLAN的知识
1.什么是VLAN? VLAN是虚拟局域网,逻辑隔离广播域和网络区域 是一种通过将局域网内的设备逻辑地划分为一个个网络的技术 2.对比逻辑网络分割和物理网络分割? 逻辑网络分割是VLAN,隔离广播域和网络区域 物理网络分割是路由&…...
RFID 赋能部队智能物联网仓储建设:打造信息化高效解决方案
在当今军事现代化进程的宏大背景下,部队后勤保障工作无疑占据着举足轻重的地位,而仓储管理作为其中的核心环节,更是至关重要。传统的仓储管理模式在面对当下物资种类繁杂、数量庞大的现状时,已显得力不从心,效率低下、…...
结构型屏蔽在高频电子设备中的应用与优化
在当今高度电子化的时代,随着电子产品工作频率不断提高,设备内部温度上升,电磁环境日趋复杂,电磁兼容(EMC)问题成为设计和制造过程中必须重点解决的问题。EMC不仅关系到设备自身的稳定运行,更涉…...
【教程】Ubuntu修改ulimit -l为unlimited
转载请注明出处:小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你,欢迎[点赞、收藏、关注]哦~ 目录 问题描述 解决方法一 解决方法二 解决方法三 (终极) 问题描述 查系统资源限制 ulimit -l如果返回的是 64 或其他较小值,那么RDM…...
【HDFS】BlockPlacementPolicyRackFaultTolerant#getMaxNode方法的功能及具体实例
方法参数说明: numOfChosen:已经选择的节点数numOfReplicas:还需要选择的副本数方法的返回值是一个长度为2的数组:[调整后的要选出多少个节点(不包括已经选择的), 每个机架最大能选择的节点数] @Overrideprotected int[] getMaxNodesPerRack(int numOfChosen, int numOfR…...
水污染治理(生物膜+机器学习)
文章目录 **1. 水质监测与污染预测****2. 植物-微生物群落优化****3. 系统设计与运行调控****4. 维护与风险预警****5. 社区参与与政策模拟****挑战与解决思路****未来趋势** 前言: 将机器学习(ML)等人工智能技术融入植树生物膜系统ÿ…...
数模小白变大神的日记2025.4.15日
分工 1.论文:mathtype (Latex) 2.建模;相应的建模知识与撰写方法,写摘要 3.编程:matlab、SPSs、(Python) 评价模型 1. 层次分析法 ①层次分析法是一种多目标、多准则的决策问题 ②层次分析法是一种主观加权法 ③层次分析法通过以下步骤实现: 1.构…...
STM32提高篇: 以太网通讯
STM32提高篇: 以太网通讯 一.以太网通讯介绍二.W5500芯片介绍1.W5500芯片特点2.W5500应用目标3.接入框图 三.驱动移植四.tcp通讯五.udp通讯六.http_server 一.以太网通讯介绍 以太网(Ethernet)是一种计算机局域网技术。IEEE组织的IEEE 802.3标准制定了以…...
4-15记录(冒泡排序,快速选择排序)
算法稳定 简单选择排序的实质就是最后一个和第一个比较,小,就换位置,然后继续用最后一个数字和第二个比较,以此类推。 但是算法不稳定,本来下划线的2在后面,但是经过算法后去了前面 快速排序 实现过程&am…...
Ubuntu系统18.04更新驱动解决方法
原始是:ubuntu18.04里面的驱动是470,对应cuda11.4 现在需要更新为525,对应cuda为12.0 实现: 1、打开终端 Ctrl Alt T2、使用 lspci 命令(快速查看显卡型号) lspci | grep -i vga3、终端输入 ubuntu-d…...
Rocky Linux 9.x 基于 kubeadm部署k8s
搭建集群使用docker下载K8s,使用一主两从模式 主机名IP地址k8s- master192.168.1.141k8s- node-1192.168.1.142k8s- node-2192.168.1.143 一:准备工作 VMware Workstation Pro新建三台虚拟机Rocky Linux 9(系统推荐最小化安装) …...
MATLAB程序实现了一个物流配送优化系统,主要功能是通过遗传算法结合四种不同的配送策略,优化快递订单的配送方案
%% 主函数部分 % function main()clear; clc; close all;% 生成或加载算例 filename = D:\快递优化\LogisticsInstance.mat; if ~exist(filename, file)instance = generate_instance();save(filename, -struct, instance); elseinstance = load(filename); end% 遗传算法参数配…...
利用宝塔面板搭建RustDesk服务
一、介绍 1.1官网 https://rustdesk.com/ 1.2github仓库 https://github.com/rustdesk/rustdesk 1.3特点 RustDesk 支持多种操作系统,包括 Windows、macOS、Linux、Android 和 iOS。它甚至提供网页版客户端,可以在浏览器中直接使用。 用户可以通过…...
前端与Java后端交互出现跨域问题的14种解决方案
跨域问题是前端与后端分离开发中的常见挑战,以下是14种完整的解决方案: 1 前端解决方案( 开发环境代理) 1.1 Webpack开发服务器代理 // vue.config.js 或 webpack.config.js module.exports {devServer: {proxy: {/api: {target: http://localhost:8…...
PBKDF2全面指南(SpringBoot实现版)
文章目录 第一部分:PBKDF2基础概念1. 什么是PBKDF2?2. 为什么需要PBKDF2?3. PBKDF2的工作原理4. PBKDF2与其他密码散列函数的比较第二部分:在Java和SpringBoot中使用PBKDF21. Java内置的PBKDF2支持2. SpringBoot中集成PBKDF22.1 添加依赖2.2 配置PBKDF2密码编码器2.3 自定义…...
基于RV1126开发板的rknn-toolkit-lite使用方法
1. rknn-toolkit-lite介绍 rknn-toolkit-lite是用于python算法的推理的组件,当前已经在EASY-EAI-Nano完成适配,用户可以用它进行深度学习算法的纯python开发。而且同时支持已经进行了预编译的模型,短短几行代码即可完成算法的推理,…...
一款轻量级的PHP地址发布页面源码
源码介绍 一款轻量级的PHP链接发布页面源码,适合快速搭建个性化的链接导航网站,支持动态链接管理和多种风格模板切换 1:后台登录地址为/admin/login.php,提供便捷的配置入口。 2:默认用户名是admin,密码为…...
分布式计算领域的前沿工具:Ray、Kubeflow与Spark的对比与协同
在当今机器学习和大数据领域,分布式计算已成为解决大规模计算问题的关键技术。本文将深入探讨三种主流分布式计算框架——Ray、Kubeflow和Spark,分析它们各自的特点、应用场景以及如何结合它们的优势创建更强大的计算平台。 Spark批量清洗快,…...
【专题刷题】双指针(一)
📝前言说明: 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录,按专题划分每题主要记录:1,本人解法 本人屎山代码;2,优质解法 优质代码;3,精益求精,…...
火山引擎旗下防御有哪些
首先,我需要确认用户是不是打错了,比如把“引擎”当成了“云”,或者他们真的想了解火山引擎的防御机制。火山引擎是字节跳动旗下的云服务平台,类似于阿里云或腾讯云,所以用户可能想了解的是其安全防护措施。 接下来&am…...
python程序打包——nuitka使用
目前python打包成exe的工具主要有:PyInstaller Briefcase py2exe py2app Nuitka CX_Freeze等。 不同于C代码,可以直接编译成可执行的exe文件,或者js代码在浏览器中就能执行,python代码必须通过python解释器来运行,…...
编写了一个专门供强化学习玩的贪吃蛇小游戏,可以作为后续学习的playgraound
文章目录 **试玩效果****项目背景****核心设计思路****代码亮点解析****与强化学习算法的对接示例****扩展方向****总结****完整代码**把训练一个会玩小游戏的智能体,作为学习强化学习的一个目标,真的是很有乐趣的一件事。我已经不知为此花费了多少日夜了。如今已是着魔了一般…...
chain_type=“stuff 是什么 ? 其他方式有什么?
chain_type="stuff 是什么 ? 其他方式有什么? 目录 chain_type="stuff 是什么 ? 其他方式有什么?1. `chain_type="stuff"`2. `chain_type="map_reduce"`3. `chain_type="refine"`4. `chain_type="map_rerank"`在 LangCh…...
在IDEA里面建立maven项目(便于java web使用)
具体步骤: 第一次有的电脑你再创建项目的时候右下角会提醒你弹窗:让你下载没有的东西 一定要下载!!可能会很慢 运行结果: 因为他是默认的8080端口所以在运行的时候输入的url如下图: 新建了一个controller代…...
MyBatis 详解
1. 什么是 MyBatis? MyBatis 是一款优秀的 持久层框架,它通过 XML 或注解配置,将 Java 对象(POJO)与数据库操作(SQL)进行灵活映射,简化了 JDBC 的复杂操作。 核心思想:S…...
郑州工程技术学院党委书记甘勇一行莅临埃文科技调研交流
为深化产教融合、推动人工智能领域人才培养与产业需求精准对接,2025年4月9日下午,郑州工程技术学院党委书记甘勇、河南省人工智能产业创新发展联盟执行秘书长孟松涛等一行莅临埃文科技调研交流。 一、聚焦技术前沿 共话AI产业变革 座谈会上,…...
AI应用开发之扣子第一课-夸夸机器人
首先,进入官网:点击跳转至扣子。 1.创建智能体 登录进网站后,点击左上角+图标,创建智能体,输入智能体名称、功能介绍 2.输入智能体提示词 在“人设与回复逻辑”输入以下内容: # 角色 你是一…...
Node.js 数据库 CRUD 项目示例
希望使用Nodejs操作数据库做CRUD,用deepseek实战搜索“使用Nodejs对数据库表做CRUD的项目例子”,找到了解决方案,如下图所示: 项目结构 nodejs-crud-example/ ├── config/ │ └── db.js # 数据库连接配置 ├──…...
ESP8266/32作为AVR编程器(ISP programmer)的使用介绍
ESP8266作为AVR编程器( ISP programmer)的使用介绍 🌿ESP8266自带库例程:https://github.com/esp8266/Arduino/tree/master/libraries/ESP8266AVRISP📍支持ESP8266/32的ESP_AVRISP其它开源工程(个人没有再去验证)&…...
union all几个常见问题及其解决方案
UNION ALL 是 SQL 中用于合并两个或多个 SELECT 语句结果集的操作符。与 UNION 不同,UNION ALL 不会去除重复的记录,它简单地将一个查询的结果附加到另一个查询的结果之后。尽管 UNION ALL 相对来说更高效(因为它不需要检查重复项)…...
21.C++11
1.列表初始化 1.1C11中的{} •C11以后想统⼀初始化⽅式,试图实现⼀切对象皆可⽤{}初始化,{}初始化也叫做列表初始化。 • 内置类型⽀持,⾃定义类型也⽀持,⾃定义类型本质是类型转换,中间会产⽣临时对象,最…...
【交叉编译】目标机编译安装对应依赖库总结
1、解压目标机交叉编译工具链 # 创建工具链存放目录(可选) sudo mkdir -p /opt/toolchain# 解压到目标路径(示例路径:/opt/toolchain) sudo tar -xzvf 目标主机编译工具链.tar.gz -C /opt/toolchain# 查看解压后的目录…...
Docker华为云创建私人镜像仓库
Docker华为云创建私人镜像仓库 在华为云官网的 产品 中搜索 容器镜像服务 : 或者在其他页面的搜索栏中搜索 容器镜像服务 : 进入到页面后,点击 创建组织 (华为云的镜像仓库称为组织): 设置组织名字后&…...
【15】数据结构之基于树的查找算法篇章
目录标题 二叉排序树 Binary Sort Tree二叉排序树的插入二叉树排序树的删除二叉排序树的查找二叉排序树的调试与代码集合 平衡二叉树-AV树平衡二叉树的平衡化旋转平衡二叉树的代码调试与代码集合 B树B树的查找B树的插入B树和B*树 二叉排序树 Binary Sort Tree 二叉…...
自定义类型之结构体
1.结构体类型概述 结构体类型是一种用户自定义的数据类型,用于将不同类型的数据组合成一个整体。在C语言中,结构体使用struct关键字定义,由一系列具有相同类型或不同类型的数据构成的数据集合,也称为结构。结构体中的数据在逻辑上…...