MySQL索引的底层实现原理
索引的底层实现原理
数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘块(对应索引树的节点),索引树越低,越“矮胖”,磁盘IO次数就少
MySQL支持两种索引,一种的B-树索引,一种是哈希索引,大家知道,B-树和哈希表在数据查询时的效率是非常高的。
这里我们主要讨论一下MySQL InnoDB存储引擎,基于B-树(但实际上MySQL采用的是B+树结构)的索引结构。
B-树是一种m阶平衡树,叶子节点都在同一层,由于每一个节点存储的数据量比较大,索引整个B-树的层数是非常低的,基本上不超过三层。
由于磁盘的读取也是按block块操作的(内存是按page页面操作的),因此B-树的节点大小一般设置为和磁盘块大小一致,这样一个B-树节点,就可以通过一次磁盘I/O把一个磁盘块的数据全部存储下来,所以当使用B-树存储索引的时候,磁盘I/O的操作次数是最少的(MySQL的读写效率,主要集中在磁盘
I/O上)
B-树
从上图可以看到B-树存在的缺点:
- 每个节点中有key,也有data,但是每一个节点的存储空间是有限的,如果data数据较大时会导致每个节点能存储的key的数据很小
- 当存储的数据量很大时同样会导致B-树的高度较大,磁盘IO次数花费增大,效率降低
B+树
那么MySQL最终为什么要采用B+树存储索引结构呢,那么看看B-树和B+树在存储结构上有什么不同?
- B-树的每一个节点,存了关键字和对应的数据地址,而B+树的非叶子节点只存关键字,不存数据地址。因此B+树的每一个非叶子节点存储的关键字是远远多于B-树的,B+树的叶子节点存放关键
字和数据,因此,从树的高度上来说,B+树的高度要小于B-树,使用的磁盘I/O次数少,因此查询会更快一些。 - B-树由于每个节点都存储关键字和数据,因此离根节点进的数据,查询的就快,离根节点远的数据,查询的就慢;B+树所有的数据都存在叶子节点上,因此在B+树上搜索关键字,找到对应数据的时间是比较平均的,没有快慢之分。
- 在B-树上如果做区间查找,遍历的节点是非常多的;B+树所有叶子节点被连接成了有序链表结构,因此做整表遍历和区间查找是非常容易的。
哈希索引
哈希索引当然是由哈希表实现的,哈希表对数据并不排序,只能进行等值比较,因此不适合做区间查找,效率非常低,需要搜索整个哈希表结构。
聚集索引与非聚集索引
MyISAM的索引方式叫做非聚集索引。
MyISAM
主键索引
MyISAM引擎使用B+树作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图:
辅助索引
在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。
根据上图,首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。
可以看到,MyISAM存储引擎,索引结构叶子节点存储关键字和数据地址,也就是说索引关键字和数据没有在一起存放,体现在磁盘上,就是索引在一个文件存储,数据在另一个文件存储,例如一个user表,会在磁盘上存储三个文件 user.frm(表结构文件) user.MYD(表的数据文件) user.MYI(表的索引文件)。
InnoDB
InnoDB的索引树叶节点包含了完整的数据记录,这种索引叫做聚集索引。
主键索引
InnoDB存储引擎的主键索引,叶子节点中,索引关键字和数据是在一起存放的,如图:
辅助索引
InnoDB的辅助索引,叶子节点上存放的是索引关键字和对应的主键,如图:
辅助索引的B+树,先根据关键字找到对应的主键,再去主键索引树上找到对应的行记录数据。从索引树上可以看到,InnoDB的索引关键字和数据都是在一起存放的,体现在磁盘存储上,例如创建一个user表,在磁盘上只存储两种文件,user.frm(存储表的结构),user.ibd(存储索引和数据)。
InnoDB的索引树叶节点包含了完整的数据记录,这种索引叫做聚集索引。因为InnoDB的数据文件本身
要按主键聚集,所以InnoDB要求表必须有主键(区别于MyISAM可以没有),如果没有显式指定,则
MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动
为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。
自适应哈希索引
InnoDB 存储引擎监测到同样的二级索引不断被使用,它会根据这个二级索引树(B+树)上的二级索引值,在内存上构建一个哈希索引,来加速搜索。
相关文章:

MySQL索引的底层实现原理
索引的底层实现原理 数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘块(对应索引树的节点),索引树越低,越“矮胖”,磁盘IO次数…...
Linux 更新
Linux权限系统 01 只读 1 10 只写 2 100 只执行 4 11 可读写 3 101 可读执行 5 110 可写执行 6 111 可读写执行 7...
华为OD机试 - 端口合并(Python)
题目描述 有M个端口组(1<=M<=10), 每个端口组是长度为N的整数数组(1<=N<=100), 如果端口组间存在2个及以上不同端口相同,则认为这2个端口组互相关联,可以合并。 输入描述 第一行输入端口组个数M,再输入M行,每行逗号分割,代表端口组。 备注:端口组内数字…...
分部积分法习题
前置知识:分部积分法 例题 计算积分 I n ∫ [ ( x a ) 2 b 2 ] − k d x ( n ≥ 1 ) I_n\int [(xa)^2b^2]^{-k}dx \quad(n\geq 1) In∫[(xa)2b2]−kdx(n≥1) 解: \qquad 用分部积分法,对任何自然数 k ≥ 1 k\geq 1 k≥1,…...

C++—非递归【循环】遍历二叉树(前序,中序,后序)思路讲解+代码实现
非递归遍历二叉树 前序中序后序 接下来我们在研究如何使用循环实现遍历二叉树时,以下面的二叉树为例: 在下文的讲解中,不对如何构建这颗二叉树做讲解,直接给出代码,如果有不懂的地方欢迎私信我。 文章中的完整源代码链…...

前端002_初始化项目
1、命名和启动项目 将目录名 vue-admin-template-master 重命名为 db-manager-system 将 db-manager-system/package.json 中的 name 值改为 db-manager-system {"name": "db-manager-system","version": "1.0.1","descriptio…...
组合设计模式
组合模式 组合模式定义使用场景1、文件系统的目录结构:2、组织架构图:3、菜单和菜单项:4、使用场景总结: 角色定义Component 抽象构件角色:Leaf 叶子构件:Composite 树枝构件: 需求背景代码实现Component(抽象构件角色…...

【MySQL】多表查询
上一篇介绍了外键约束,外键约束是用于连接两张数据表的,所以在此基础上就有了多表查询 之前的查询都是单表查询,这里我们会将多个数据表的数据结果返回在一张表上 文章目录 1.多表关系2.多表查询2.1 多表查询分类2.2 内连接2.3 外连接2.4 自连接2.5 联合查询2.6子查询 1.多表关…...

关于在线帮助中心你需要思考以下几个问题
搭建帮助中心是大多数企业都在尝试做的事情,它的重要性对于企业来说不言而喻。现在对于企业来说,搭建帮助中心或许不是什么难事,但是关于帮助中心,有几个问题需要思考清楚,才能让其发挥最大的价值。 一、如何让用户养成…...

基于FPGA+JESD204B 时钟双通道 6.4GSPS 高速数据采集模块设计(一)总体方案
本章将根据高速数据采集指标要求,分析并确定高速数据采集模块的设计方 案,由此分析数据存储需求及存储速度需求给出高速大容量数据存储方案,完成 双通道高速数据采集模块总体设计方案,并综合采集、存储方案及 AXIe 接口需求 …...

二、Spring Cloud Alibaba环境搭建
一、依赖环境 SpringCloud Alibaba 依赖 Java 环境来运行。还需要为此配置 Maven环境,请确保是在以下版本环境中安装使用。 64 bit JDK 1.8;Maven 3.2.x。 spring-cloud-alibaba相关网址: 地址:https://github.com/alibaba/spring-cloud-…...

瑞萨e2studio(24)----电容触摸配置(1)
瑞萨e2studio.24--电容触摸配置1 概述硬件准备新建工程工程模板保存工程路径芯片配置工程模板选择时钟配置添加TOUCH驱动配置CapTouch开启调优界面启动 CapTouch 调优通过电容触摸点亮LED 概述 这篇文档将创建一个使用 e2 studio 集成 QE 的电容式触摸应用示例,通…...

数据开发常见问题
目录 环境变量过多或者参数值过长时,为什么提交作业失败? 为什么Shell作业状态和相关的YARN Application状态不一致? 创建作业和执行计划的区别是什么? 如何查看作业运行记录? 如何在OSS上查看日志? 读…...

Ae:橡皮擦工具
橡皮擦工具 Eraser Tool 快捷键:Ctrl B 橡皮擦工具 Eraser Tool在工作原理上同 Ae 中的其它绘画工具(画笔、仿制图章)工具基本一致,都是通过绘制路径,然后基于此路径进行描边(可统称为“绘画描边”&…...

干货 | 正确引用参考文献的6大技巧
Hello,大家好! 这里是壹脑云科研圈,我是喵君姐姐~ 对于学术研究而言,正确引用参考文献非常重要。参考文献不仅展现了自己的学术水平,同时也给研究定位,突显研究在前人研究基础上作出的贡献。 …...
区块链系统探索之路:基于椭圆曲线的私钥与公钥生成
前两节我们探讨了抽象代数的重要概念:有限域,然后研究了基于椭圆曲线上点的怪异”“操作,两者表面看起来牛马不相及,实际上两者在逻辑上有着紧密的联系,简单来说如果我们在椭圆曲线上取一点G,然后让它跟自己做”“操作…...
Linux命令集(Linux常用命令--echo指令篇)
Linux命令集(Linux常用命令--echo指令篇) Linux常用命令集(echo指令篇)2.echo(echo)1. 输出自定义内容2. 禁止输出末尾换行符3. 转义功能4. 与特殊字符配合使用实现其余功能 Linux常用命令集(echo指令篇) 如…...

【电子学会】2023年03月图形化一级 -- 甲壳虫走迷宫
甲壳虫走迷宫 1. 准备工作 (1)绘制如图所示迷宫背景图,入口在左下角,出口在右上角,线段的颜色为黑色; (2)删除默认小猫角色,添加角色:Beetle; …...

老外从神话原型中提取的12个品牌个性
老外从神话原型中提取的12个品牌个性 也是西方视角,需要本土化 参照心理学大师荣格的理论:心理学潜意识派 趣讲大白话:品牌的调调是啥 【趣讲信息科技151期】 **************************** 12种原型又归属于4种人性动机。 1、稳定࿰…...
unity中的Quaternion.AngleAxis
介绍 unity中的Quaternion.AngleAxis 方法 Quaternion.AngleAxis() 函数是 Unity 引擎中的一个数学函数,用于创建一个绕着某个轴旋转一定角度的旋转四元数。在游戏开发中,经常会用到该函数来旋转物体或计算旋转后的方向向量。 该函数的函数原型为&…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...