Mysql索引的实现原理,B+Tree,WAL

InnoDB 引擎,每一个数据表有两个文件 .frm.ibd,分别为表结构,数据和索引,数据挂在主索引的叶子节点上,此主索引称为聚簇索引。

MyISAM 引擎,每一个数据表有三个文件.frm.MYI.MYD,分别为表结构,索引,数据;也就是说其索引和数据是分开的,索引的叶子节点存储的不是数据而是磁盘地址,称为非聚簇索引。

下面只分析 InnoDB 引擎。

一、为什么是 B+Tree 而不是 B-Tree

B-Tree

img

B+Tree

img

他两最大的区别就是 B+Tree 将data部分下沉到了最后一级,即叶子节点。

对于基于磁盘的存储,一般使用对磁盘的IO次数来评判索引结构的优劣,假设操作系统对磁盘的每次IO能读取 4K 数据(块),假设索引结构的每一个节点有16K的固定空间,这个16K称为页,索引以页作为最基本的管理单位,所以每一次读取要4次IO,从节省IO次数的角度讲,如果每个节点上如果能存储更多的key就能减少IO的次数,而B+Tree是将所有的data下放到叶子节点,其他节点全部用来存储key和指针,显然IO效率更高。

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针。在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,做这个优化的目的是为了提高区间访问的性能。也就是说,通过这个指针你可以访问到已经排序好的key的列表。

二、InnoDB 引擎读写磁盘的过程

我们经常听人说Mysql对磁盘的写操作是随机寻址的,所以需要WAL组件。但是为什么Mysql对磁盘的写操作是随机寻址的呢?这就需要了解它读写磁盘的过程。

就以InnoDB引擎为例,其索引结构和源数据都存在.ibd文件里,文件是一块大的连续的磁盘空间,收到查询请求后引擎就去读取此文件的主索引,以页(16K)为单位读取,从B+Tree的根节点开始,当然有时候一个节点不止一页,如果没有找到这个key就要接着读,直到找到了data。

从根节点指向一级节点的时候,那么一级节点存在文件中的哪个位置呢,或者说即便你知道了它在文件中的位置,你要怎么读到它呢,我们可以使用相对于文件起始位置的偏移量来读取那一块的数据,或者计算出其在磁盘上的地址,然后直接读取磁盘,所以指向子节点使用的是指针,整个的读取过程是跳跃的随机的。

同样的,在写入的时候,要写入的目标磁盘块的位置也是跳跃的,所以说写操作是随机的寻址,它不是append模式。有时候在写入后现有节点还要调整。

说到底这些节点都还是存在于文件中,文件是一块大的连续的磁盘空间,所以这里的指针应该是相对于文件起始地址的相对地址,而不能是磁盘的绝对地址,否则你一移动文件那岂不都失效了。

在机械硬盘上面,这种随机寻址会严重影响磁盘的IO性能。

三、需要 WAL (Write-Ahead Logging)

既然直接落盘性能堪忧,那就改成异步落盘。基本上所有的数据库都使用WAL模式来解决这个问题,实现方式可能各有不同,但大致思路都是一样的。

一个修写入请求,先写入日志文件,成功之后才写入缓存,然后有后台程序将日志文件的内容落盘。

在写日志文件的时候,使用 append模式,这就是顺序写,要比随机写好很多。

redo log:保证数据一致性。如果Mysql宕机了,重启的时候可以将日志文件中未落盘的数据落盘。

undo log:保证事务的原子性,实现多版本并发控制(MVCC)。它相当于在修改之前做一下备份。

组提交机制:将多个小的事务合并成一组再执行落盘,可以大幅度降低磁盘的 IOPS 消耗。

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

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

相关文章

深入理解计算机系统 CSAPP 家庭作业7.13

用一下496页提到的工具咯 A: whereis libm.a file lidm.a gedit libm.a libm.a是个ASCII text文件打开一看原来 libm-2.27.a 和libmvec.a才是我们要看的 所以我们cd到目标地址后 ar -t libm-2.27.a ar -t libmvec.a B: gcc -Og bar5.c foo5.c 用之前的两个文件链接后生成…

【CS.DS】数据结构 —— 图:深入了解三种表示方法之邻接表(Adjacency List)

文章目录 1 概念2 无向图的邻接表2.1 示例2.2 Mermaid 图示例2.3 C实现2.3.1 简单实现2.3.2 优化封装 2.4 总结 3 有向图的邻接表3.1 示例3.2 C实现3.3 总结 4 邻接图的遍历5 拓展补充References 数据结构 1 概念 优点:空间效率高,适合稀疏图。动态性强…

springboot 整合redis

文章目录 一、Jedis二、Lettuce三、RedisTemplate(重点)单机3.1 springboot 整合swagger3.2 序列化中文问题集群3.3 applications配置3.4 问题 一、Jedis package com.example.redis;import redis.clients.jedis.Jedis;import javax.print.DocFlavor; import java.util.*;/***…

【编译原理】绪论

1.计算机程序语言以及编译 编译是对高级语言的翻译 源程序是句子的集合,树可以较好的反应句子的结构 编译程序是一种翻译程序 2.编号器在语言处理系统中的位置 可重定位:在内存中存放的起始位置不是固定的 加载器:修改可重定位地址&#x…

古文字识别笔记

前置知识 部件:大部分的汉字是由若干组笔画结构拼合而成的,这些相对独立的笔画结构称为「部件」。 部件是大于基本笔画(例如:点、横、撇、捺等)而小于或等同于 偏旁 的结构单位。 例如「测」字有三个部件:…

【学习】使用PyTorch训练与评估自己的ResNet网络教程

参考:保姆级使用PyTorch训练与评估自己的ResNet网络教程_训练自己的图像分类网络resnet101 pytorch-CSDN博客 项目地址:GitHub - Fafa-DL/Awesome-Backbones: Integrate deep learning models for image classification | Backbone learning/comparison…

高效修复机床导轨磨损,保障加工精度!

机床导轨是支承和引导运动构件沿着一定轨迹运动的传动装置,在机器设备中是个十分重要的部件,在机床中是常见的部件。机床的加工精度与导轨精度有直接的联系,且导轨一旦损坏,维修较复杂且困难。我们简单总结了以下几点对于机床导轨…

编程设计思想

健康检查脚本 nmap:扫描端口 while true do healthycurl B:httpPORT/healthy -i | grep HTTP/1.1 | tail -n 1 | awk {print $2} done 批量操作类型脚本(记录每一步日志) 将100个nginx:vn推送到harbor仓库192.168.0.100 根据镜像对比sha值…

【开源项目】自然语言处理领域的明星项目推荐:Hugging Face Transformers

在当今人工智能与大数据飞速发展的时代,自然语言处理(NLP)已成为推动科技进步的重要力量。而在NLP领域,Hugging Face Transformers无疑是一个备受瞩目的开源项目。本文将从项目介绍、代码解释以及技术特点等角度,为您深…

面向对象修炼手册(四)(多态与空间分配)(Java宝典)

🌈 个人主页:十二月的猫-CSDN博客 🔥 系列专栏: 🏀面向对象修炼手册 💪🏻 十二月的寒冬阻挡不了春天的脚步,十二点的黑夜遮蔽不住黎明的曙光 目录 前言 1 多态 1.1 多态的形式&…

需求之 实现获取调试信息在h5页面,在手机端可以查看调试(二)

事实证明 chatgpt很好用,有不懂的问题可以问它 https://zhuanlan.zhihu.com/p/690118775 国内外9个免费的ChatGPT网站 我筛选出来的比较好用免费的网站 fchat.dykyzdh.cn/ 这个也可以 阿里云的 通义灵码 在vscode中安装使用 而且阿里云有一个产品,可以…

面试-Java线程池

1.利用Excutors创建不同的线程池满足不同场景的需求 分析: 如果并发的请求的数量非常多,但每个线程执行的时间非常短,这样就会频繁的创建和销毁线程。如此一来,会大大降低系统的效率。 可能出现,服务器在为每个线程创建…

jdk1.8升级到jdk11遇到的各种问题

一、第三方依赖使用了BASE64Decoder 如果项目中使用了这个类 sun.misc.BASE64Decoder,就会导致错误,因为再jdk11中,该类已经被删除。 Caused by: java.lang.NoClassDefFoundError: sun/misc/BASE64Encoder 当然这个类也有替换方式&#xf…

MySQL实训--原神数据库

原神数据库 er图DDL/DML语句查询语句存储过程/触发器 er图 DDL/DML语句 SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;DROP TABLE IF EXISTS artifacts; CREATE TABLE artifacts (id int NOT NULL AUTO_INCREMENT,artifacts_name varchar(255) CHARACTER SET utf8 COLLATE …

一文搞懂Linux多线程【下】

目录 🚩多线程代码的健壮性 🚩多线程控制 🚩线程返回值问题 🚩关于Linux线程库 🚩对Linux线程简单的封装 在观看本博客之前,建议大家先看一文搞懂Linux多线程【上】由于上一篇博客篇幅太长,为…

文件操作<C语言>

导言 平时我们在写程序时,在运行时申请内存空间,运行完时内存空间被收回,如果想要持久化的保存,我们就可以使用文件,所以下文将要介绍一些在程序中完成一些文件操作。 目录 导言 文件流 文件指针 文件的打开与关闭 …

《黑神话悟空》电脑配置要求

《黑神话:悟空》这款国内优秀的3A游戏大作,拥有顶级的特效与故事剧情,自公布以来便备受玩家期待,其精美的画面与流畅的战斗体验,对玩家的电脑配置提出一定要求。那么这款优秀的游戏需要什么样的电脑配置,才…

记录:[android] SSLHandshakeException: Handshake failed 问题;已解决!

1、问题描述:在使用Retrofit2 时在安卓老设备上(安卓6.0)网络无法请求、安卓 10 、 11 未出现此问题?what? 原因:服务端 TLS 版本过高 2、废话不多说、解决方案A 、添加依赖:implementation org.conscrypt…

黑马苍穹外卖6 清理redis缓存+Spring Cache+购物车的增删改查

缓存菜品 后端服务都去查询数据库,对数据库访问压力增大。 解决方式:使用redis来缓存菜品,用内存比磁盘性能更高。 key :dish_分类id String key “dish_” categoryId; RestController("userDishController") RequestMapping…

游戏工厂:AI(AIGC/ChatGPT)与流程式游戏开发

游戏工厂:AI(AIGC/ChatGPT)与流程式游戏开发 码客 卢益贵 ygluu 关键词:AI(AIGC、ChatGPT、文心一言)、流程式管理、好莱坞电影流程、电影工厂、游戏工厂、游戏开发流程、游戏架构、模块化开发 一、前言…