当前位置: 首页 > news >正文

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+树在存储结构上有什么不同?

  1. B-树的每一个节点,存了关键字和对应的数据地址,而B+树的非叶子节点只存关键字,不存数据地址。因此B+树的每一个非叶子节点存储的关键字是远远多于B-树的,B+树的叶子节点存放关键
    字和数据,因此,从树的高度上来说,B+树的高度要小于B-树,使用的磁盘I/O次数少,因此查询会更快一些。
  2. B-树由于每个节点都存储关键字和数据,因此离根节点进的数据,查询的就快,离根节点远的数据,查询的就慢;B+树所有的数据都存在叶子节点上,因此在B+树上搜索关键字,找到对应数据的时间是比较平均的,没有快慢之分。
  3. 在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行,每行逗号分割,代表端口组。 备注:端口组内数字…...

分部积分法习题

前置知识&#xff1a;分部积分法 例题 计算积分 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) 解&#xff1a; \qquad 用分部积分法&#xff0c;对任何自然数 k ≥ 1 k\geq 1 k≥1&#xff0c;…...

C++—非递归【循环】遍历二叉树(前序,中序,后序)思路讲解+代码实现

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

前端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、文件系统的目录结构&#xff1a;2、组织架构图&#xff1a;3、菜单和菜单项&#xff1a;4、使用场景总结&#xff1a; 角色定义Component 抽象构件角色:Leaf 叶子构件:Composite 树枝构件: 需求背景代码实现Component&#xff08;抽象构件角色…...

【MySQL】多表查询

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

关于在线帮助中心你需要思考以下几个问题

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

基于FPGA+JESD204B 时钟双通道 6.4GSPS 高速数据采集模块设计(一)总体方案

本章将根据高速数据采集指标要求&#xff0c;分析并确定高速数据采集模块的设计方 案&#xff0c;由此分析数据存储需求及存储速度需求给出高速大容量数据存储方案&#xff0c;完成 双通道高速数据采集模块总体设计方案&#xff0c;并综合采集、存储方案及 AXIe 接口需求 …...

二、Spring Cloud Alibaba环境搭建

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

瑞萨e2studio(24)----电容触摸配置(1)

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

数据开发常见问题

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

Ae:橡皮擦工具

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

干货 | 正确引用参考文献的6大技巧

Hello&#xff0c;大家好&#xff01; 这里是壹脑云科研圈&#xff0c;我是喵君姐姐&#xff5e; 对于学术研究而言&#xff0c;正确引用参考文献非常重要。参考文献不仅展现了自己的学术水平&#xff0c;同时也给研究定位&#xff0c;突显研究在前人研究基础上作出的贡献。 …...

区块链系统探索之路:基于椭圆曲线的私钥与公钥生成

前两节我们探讨了抽象代数的重要概念&#xff1a;有限域&#xff0c;然后研究了基于椭圆曲线上点的怪异”“操作&#xff0c;两者表面看起来牛马不相及&#xff0c;实际上两者在逻辑上有着紧密的联系&#xff0c;简单来说如果我们在椭圆曲线上取一点G,然后让它跟自己做”“操作…...

Linux命令集(Linux常用命令--echo指令篇)

Linux命令集&#xff08;Linux常用命令--echo指令篇&#xff09; Linux常用命令集&#xff08;echo指令篇&#xff09;2.echo(echo)1. 输出自定义内容2. 禁止输出末尾换行符3. 转义功能4. 与特殊字符配合使用实现其余功能 Linux常用命令集&#xff08;echo指令篇&#xff09; 如…...

【电子学会】2023年03月图形化一级 -- 甲壳虫走迷宫

甲壳虫走迷宫 1. 准备工作 &#xff08;1&#xff09;绘制如图所示迷宫背景图&#xff0c;入口在左下角&#xff0c;出口在右上角&#xff0c;线段的颜色为黑色&#xff1b; &#xff08;2&#xff09;删除默认小猫角色&#xff0c;添加角色&#xff1a;Beetle&#xff1b; …...

老外从神话原型中提取的12个品牌个性

老外从神话原型中提取的12个品牌个性 也是西方视角&#xff0c;需要本土化 参照心理学大师荣格的理论&#xff1a;心理学潜意识派 趣讲大白话&#xff1a;品牌的调调是啥 【趣讲信息科技151期】 **************************** 12种原型又归属于4种人性动机。 1、稳定&#xff0…...

unity中的Quaternion.AngleAxis

介绍 unity中的Quaternion.AngleAxis 方法 Quaternion.AngleAxis() 函数是 Unity 引擎中的一个数学函数&#xff0c;用于创建一个绕着某个轴旋转一定角度的旋转四元数。在游戏开发中&#xff0c;经常会用到该函数来旋转物体或计算旋转后的方向向量。 该函数的函数原型为&…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...