MySQL深入:B+树的演化、索引和索引结构

提示:内容是读《MySQL技术内幕:InnoDB存储引擎》,笔记摘要

文章目录

  • 二叉查找树
    • 平衡二叉树(AVL)
  • B树(BTree)
  • B+树(B+Tree)
  • InnoDB B+树索引
  • 索引结构(InnoDB B+树)
  • B+树存放的数据量


二叉查找树

在这里插入图片描述
在二叉查找树中,左子树的键值总是小于根的键值,右子树的键值总是大于根的键值,因此可以通过中序遍历得到键值的排序输出。对上图进行中序遍历(左-根-右)后输出:2、3、5、6、7、8。

平衡二叉树(AVL)

为解决二叉查找树数据左右分配不平衡,出数据大面积分布存储在根节点左侧(或右侧),查询效率低的问题,故引入平衡二叉查找树-AVL树。
平衡二叉树的定义
首先符合二叉查找树的定义; 其次必须满足任何节点的两棵子树的高度最大差为1。
平衡二叉树的缺点
平衡二叉树的查询速度的确快,但是维护一棵平衡二叉树的存储成本有很大,通常需要1次或多次左旋或右旋来得到经过插入或更新操作后二叉树的平衡性。
例如: 平衡二叉树【 1、2、4、5、9】,增加新数据节点3。
在这里插入图片描述

B树(BTree)

概念:
B树和平衡二叉树不同,B树属于多叉树又名平衡多路查找树(查找路径不只两个),数据库索引里大量使用者B-Tree和B+Tree的数据结构。
特点:
(1)排序方式:所有节点关键字是按递增次序排列,并遵循左小右大原则;
(2)子节点数:非叶节点的子节点数范围(1,M] , 且M>=2,空树除外;
(注:M阶代表一个树节点最多有多少个查找路径,当M=3则是3叉树);
(3)关键字数Key:枝节点的关键字Key数量数据范围[ceil(M/2)-1,M-1]
(注:ceil()是个朝正无穷方向取整的函数 如3阶B树时ceil(1.5)结果为2,关键字数范围[1,2]);
(4)所有叶子节点均在同一层、叶子节点包含关键字和数据;
(5)拥有n-1个key值非叶子节点必须有n个孩子节点;
(6)一个节点的所有key值必须是升序排序的;
在这里插入图片描述BTree是单个节点可以存储多个键值和数据的多路平衡查找树
在存储海量的数据,因为平衡二叉树的每个节点只存储一个键值和数据,节点将会非常多且高度也其高,当查找数据时会进行很多次磁盘IO,查找的效率将会极低,为了解决平衡二叉树的这个弊端,需要一种单个节点可以存储多个键值和数据的平衡树(BTree)

B+树(B+Tree)

概念
B+树是B树的一个进化,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。结构如下:
在这里插入图片描述
特点:
(1)非叶子节点只存储索引(键值 + 指针 ),不存储data
(2)叶子节点存储键值和所有data,记录节点都是按键值的大小顺序存放在同一层的叶子节点,并通过指针进行链接

InnoDB B+树索引

    在MySQL数据库中,索引是在存储引擎层实现的,这意味着每个引擎的B+树索引的实现方式可能是不同的,取决于存储引擎实现的本身。
    在InnoDB存储引擎中,数据文件本身就是按照B+树方式存放数据的。其中,B+树的键值为主键,若在建立时没有显式地指定主键,则InnoDB存储引擎会自动创建一个6字节的列作为主键(rowId)。因此在InnoDB存储引擎中,可以将B+树索引分为聚集索引和辅助索引(非聚集索引)。无论是何种索引,每个页的大小都为16KB,且不能更改。
聚集索引和辅助索引的区别
聚集索引与辅助索引,底层数据结构都是B+树,区别仅在于所存放数据的内容:
聚集索引是根据主键创建的一棵B+树,叶子节点存放表中的所有记录
辅助索引(普通索引)是根据索引键创建的一棵B+树,叶子节点仅存放索引键值,以及该索引键值指向的主键
提示:如果通过辅助索引来查找数据,那么当找到辅助索引的叶子节点后,很有可能还需要根据主键值查找聚集索引来得到数据,这种查找方式又被称为回表。因为辅助索引不包含行记录的所有数据,这就意味着每页可以存放更多的键值,因此其高度一般都要小于聚集索引。
在这里插入图片描述
在这里插入图片描述
回表:先通过普通索引扫描出数据所在的行(存储的是聚簇索引-主键的值,而非数据),再通过行主键值去主键(聚集)索引的叶子节点中去获取完整的数据,这样的查询等同于需要多扫描一棵索引树,这就是回表, 简单说就是基于非主键索引的查询需要多扫描一棵索引树。

如何避免回表? 可通过索引覆盖解决。在索引中包含所有需要获取的所有字段,查询结果可以直接全部拿到字段数据,不需要通过主键索引再次去获取。

索引结构(InnoDB B+树)

存储单元
磁盘:最小单元是扇区,一个扇区的大小是 512个字节
文件系统:最小单元是块,一个块的大小是 4K
InnoDB存储引擎:最小单元称之为(数据页Page),一个页的大小是16K,MySQL的InnoDB存储引擎以Data Page(数据页)作为磁盘和内存之间交互的基本单位。
B+树存储结构
mysql数据库中,table表中的表数据(记录)都是存储在页中,是以页的形式存放的,页在磁盘中不一定是连续, 且页是分布在表空间文件(.ibd文件)内,例如 user 用户表表空间文件:
在这里插入图片描述
数据页结构图在这里插入图片描述
说明:
在这里插入图片描述

B+树存放的数据量

B+树的存储总记录数 = 根节点指针数 * 单个叶子节点记录条数

假设一条的记录大小为1KB,单个叶子节点记录条数=数据页16KB/1KB = 16(条);
假设主键ID为bigint类型,长度为8字节,而指针大小为6字节,共14字节。
则一个页中可存放组合(即指针),即 1024 * 16 / 14 =1170,可以算出一棵高度为2的B+树,能存放 1170 * 16 = 1.87万,3阶的B+树能存放 1170 * 1170 * 16 = 2200万 数据记录。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

FairGuard游戏加固实机演示

此前,FairGuard对市面上部分游戏遭遇破解的案例进行了详细分析,破解者会采用静态分析与动态调试相结合的手段,逆向分析出代码逻辑并对其进行篡改,实现作弊功能,甚至是对游戏资源文件进行篡改,从而制售外挂。…

聊一聊Elasticsearch的索引数据搜索过程

与向索引写入数据的时候必须是主分片来承担不同。搜索的时候,主分片和副本分片均可以承担,最终选用主分片还是副本分片是通过轮询的方式来进行选择的。 索引数据的搜索过程,依据有无路由值,分为两种:不带路由值的搜索…

视频修复技术和实时在线处理

什么是视频修复? 视频修复技术的目标是填补视频中的缺失部分,使视频内容连贯合理。这项技术在对象移除、视频修复和视频补全等领域有着广泛的应用。传统方法通常需要处理整个视频,导致处理速度慢,难以满足实时处理的需求。 技术发…

自动化运维-检测Linux服务器CPU、内存、负载、IO读写、机房带宽和服务器类型等信息脚本

前言:以上脚本为今年8月1号发布的,当时是没有任何问题,但现在脚本里网络速度测试py文件获取不了了,测速这块功能目前无法实现,后面我会抽时间来研究,大家如果有建议也可以分享下。 脚本内容: #…

C语言-11-18笔记

1.C语言数据类型 类型存储大小值范围char1 字节-128 到 127 或 0 到 255unsigned char1 字节0 到 255signed char1 字节-128 到 127int2 或 4 字节-32,768 到 32,767 或 -2,147,483,648 到 2,147,483,647unsigned int2 或 4 字节0 到 65,535 或 0 到 4,294,967,295short2 字节…

【HashMap篇】HashMap实现原理|put方法|扩容机制|寻址算法|1.7情况下的多线程死循环问题

目录 一、二叉树、红黑树、散列表简单介绍 1.二叉树 (1)什么是二叉树 (2)什么是二叉搜索树 2.红黑树 (1)什么是红黑树 3.散列表 (1)什么是散列表 (2)…

AI 大模型重塑软件开发的未来

✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…

idea 配置 leetcode插件 代码模版

开启自定义模版 codeFileName: $!velocityTool.camelCaseName(${question.titleSlug})Code Template: ${question.content} package leetcode.editor.cn; /*** ${question.title}* author lww* since $!velocityTool.date()*/ public class $!velocit…

微软Microsoft有许多耳熟能详的软件?

微软有许多耳熟能详的软件,以下是一些比较有代表性的: 一、软件类 操作系统: Windows 系列:这是微软最为著名且广泛使用的操作系统,如 Windows 10、Windows 11 等。它为全球绝大多数个人电脑提供了操作平台&#xff0c…

Confluence|Confluence报错:连接MySQL数据库失败

报错信息:Problem connecting to your database 解决方案: 增加一个mysql驱动jar包到容器内部 docker cp ./mysql-connector-java-8.0.19.jar confluence:/opt/atlassian/confluence/confluence/WEB-INF/lib/ 作者:Kkoo 链接:ht…

扣子(Coze):构建智能助手并嵌入个人网站的新选择

首发地址(欢迎大家访问):扣子(Coze):构建智能助手并嵌入个人网站的新选择 1. 前言 之前写了一篇关于使用 MaxKB 搭建个人知识库并集成到个人网站的博客; 整个技术路线我觉得还是很好的&#x…

LeetCode - #139 单词拆分

文章目录 前言摘要1. 描述2. 示例3. 答案题解动态规划的思路代码实现代码解析1. **将 wordDict 转换为 Set**2. **初始化 DP 数组**3. **状态转移方程**4. **返回结果** **测试用例**示例 1:示例 2:示例 3: 时间复杂度空间复杂度总结关于我们 前言 本题由于没有合适答案为以往遗…

SpringCloud篇(服务保护 - Sentinel)

目录 一、雪崩问题及解决方案 1. 雪崩问题 2. 解决方案 方案一:超时处理 方案二:仓壁模式 方案三:断路器模式 方案四:限流 3. 总结 二、服务保护技术对比 三、Sentinel介绍与安装 1. 初识Sentinel 2. Sentinel 优势 3…

MACOS开发、使用常见问题汇总

MACOS常见问题 本文记录使用macos遇到的常见问题,后面会持续更新,觉得有用的可以收藏一下。 打不开xxx.app,因为它来自身份不明的开发者解决方法(开启任何来源) 打开终端(Terminal)程序 拷贝sudo spctl --master-di…

网络安全之国际主流网络安全架构模型

目前,国际主流的网络安全架构模型主要有: ● 信息技术咨询公司Gartner的ASA(Adaptive Security Architecture自适应安全架构) ● 美国政府资助的非营利研究机构MITRE的ATT&CK(Adversarial Tactics Techniques &…

Linux下 GDB调试器的使用

文章目录 1. 可执行程序的Debug版和Release版区别一、编译选项与目的二、性能与体积三、功能与特性四、查看可执行文件 2. GDB 相关命令GDB常用命令 1. 可执行程序的Debug版和Release版区别 一、编译选项与目的 Debug版: 编译选项:通常使用包含调试信息…

RN开发搬砖经验之—Layout Inspector看不到 DecorView

最近我发现自己已经很久没有使用Layout Inspector这个工具了。今天,为了深入分析React Native(RN)框架中的一个UI问题,我需要查看RN组件对应的Android原生组件视图层级(View tree)的实际情况。因此&#xf…

go-zero(三) 数据库操作

go-zero 数据库操作 在本篇文章中,我们将实现一个用户注册和登录的服务。我们将为此构建一个简单而高效的 API,包括请求参数和响应参数的定义。 一、Mysql连接 1. 创建数据库和表 在 MySQL 中创建名为 test_zero的数据库,并创建user 表 …

23种设计模式-模板方法(Template Method)设计模式

文章目录 一.什么是模板方法模式?二.模板方法模式的特点三.模板方法模式的结构四.模板方法模式的应用场景五.模板方法模式的优缺点六.模板方法模式的C实现七.模板方法模式的JAVA实现八.代码解析九.总结 类图: 模板方法设计模式类图 一.什么是模板方法模…

uniapp实现开发遇到过的问题(持续更新中....)

1. 在ios模拟器上会出现底部留白的情况 解决方案: 在manifest.json文件,找到开源码视图配置,添加如下: "app-plus" : {"safearea":{"bottom":{"offset" : "none" // 底部安…