Mysql底层原理四:B+树索引

B+树索引(索引的原理)

1.前言

前边我们详细唠叨了InnoDB数据⻚的7个组成部分,知道了各个数据⻚可以组成⼀个双向链表,⽽每个数据⻚中的记录会按照主键值从⼩到⼤的顺序组成⼀个单向链 表,每个数据⻚都会为存储在它⾥边⼉的记录⽣成⼀个⻚⽬录,在通过主键查找某条记录的时候可以在⻚⽬录中使⽤⼆分法快速定位到对应的槽,然后再遍历该槽 对应分组中的记录即可快速找到指定的记录(如果你对这段话有⼀丁点⼉疑惑,那么接下来的部分不适合你,返回去看⼀下数据⻚结构吧)。⻚和记录的关系示 意图如下:

2.没有索引的查找

2.1 在一个页中查找

  • 以主键为搜索条件
  • 以其他列为搜索条件
    对⾮主键列的查找的过程可就不这么幸运了,因为在数据⻚中并没有对⾮主键列建⽴所谓的⻚⽬录,所以我们⽆法通过⼆分法快速定位相应的槽。这种情况下 只能从最⼩记录开始依次遍历单链表中的每条记录,然后对⽐每条记录是不是符合搜索条件。很显然,这种查找的效率是⾮常低的。

2.2 在很多个页中查找

在很多页的时候,我们应该是先定位到对应的页,然后到页中根据槽来查找。但是在没有索引的情况下,由于我们并不能快速定位到记录所在的页,所以只能从第一个页沿着链表遍历所有的页,是不是超级超级蠢。

3.一个简单的索引方案

问题:为什么我们要遍历所有的数据页拿?

因为各个页之间没有规律,我们并不知道怎么去匹配记录,所以不得不遍历所有的数据页。如果我们想快速定位到需要查找的记录该怎么办,其实参照记录目录的方法,我们是不是也可以建立一个有序的的目录🙏,建立这个目录必须完成以下这些事:

  1. 下一个页的记录主键值必须大于 上一个页记录的主键值
  2. 页分裂(一个页放不下的时候,分成两个页)时,依旧要保证上面说的关系。

1)准备工作

建表:

mysql>	CREATE	TABLE	index_demo(
   	->    	c1	INT,
   	->    	c2	INT,
   	->    	c3	CHAR(1),
   	->    	PRIMARY	KEY(c1)
   	->	)	ROW_FORMAT	=	Compact;
Query	OK,	0	rows	affected	(0.03	sec)

插入数据:

mysql>	INSERT	INTO	index_demo	VALUES(1,	4,	'u'),	(3,	9,	'd'),	(5,	3,	'y');
Query	OK,	3	rows	affected	(0.01	sec)
Records:	3 	Duplicates:	0 	Warnings:	0

这时候的页如图所示:

2)插入数据测试

再插入一条记录:

mysql>	INSERT	INTO	index_demo	VALUES(4,	4,	'a');
Query	OK,	1	row	affected	(0.00	sec)

因为页10只能放3个记录,所以我们不能不再分配一个页:

问题:为什么页号不是连续的?

新分配的数据页编号可能并不是连续的,也就是我们使用的页空间上并不是连续的。它们只是通过维护上下页来建立链表关系。另外,⻚10中⽤户记录最⼤的主键值是5,⽽⻚28中有⼀条记录的主键值是4,因为5 > 4,所 以这就不符合下⼀个数据⻚中⽤户记录的主键值必须⼤于上⼀个⻚中⽤户记录的主键值的要求,所以在插⼊主键值为4的记录的时候需要伴随着⼀次记录移动,也 就是把主键值为5的记录移动到⻚28中,然后再把主键值为4的记录插⼊到⻚10中,这个过程的示意图如下:

3)  给页建目录

以页28为例,它对应目录项2,这个目录项包含主键值,页号。比方说我们想查找主键值为20的记录,具体步骤粪两步:

  1. 先从⽬录项中根据⼆分法快速确定出主键值为20的记录在⽬录项3中(因为 12 < 20 < 209),它对应的⻚是⻚9。
  2. 再根据前边说的在⻚中查找记录的⽅式去⻚9中定位具体的记录。

记住,这个目录有个别名,就是索引,哈哈

4. InnoDB的索引方案

4.1  上述的索引方案有什么问题?

  1. 当表中数据不断增多的时候,目录项非常耗费空间,这对于记录数比较多的表不太现实
  2. 我们时常会对记录做增删,假设我们把页28中的记录全部删除了,页28也就没有必要存在 ,同时目录项2也没有存在的必要了。

设计InnoDB的大叔们灵光乍现,发现这些目录项其实和数据页长的差不多,只不过目录项存储的列值时主键和页号,所以他们复用了数据页的结构来存储目录项,为了区分,利用 头信息的record_type属性。 它的各个取值代表意思如下:

  • 0:普通记录
  • 1:目录项
  • 2:最小记录
  • 3:最大记录

4.2 最终实现的样子

从图中可以看出,我们新分配了一个编号为30的页用来专门存储目录项记录。这里再次强调一遍 目录项记录和普通的 用户记录的不同点:

  • 目录项记录的record_type值是1,而普通用户记录的record_type值是0。
  • 目录项记录只有主键值和页的编号两个列,而普通的用户记录是用户自己定义的,可能包含很多列,另外还有InnoDB自己添加的隐藏列。
  • 还记得我们之前在唠叨记录头信息的时候说过一个 min_rec_mask的属性么,只有在存储目录项的页中的**主键值的目录项记录的min_rec_mask值为1,**其他都是0

假设我们按照某个主键20去查找记录,大致步骤分以下几步:

  1. 先看页的目录,也就是30的页通过二分法(这里指的是槽)找到对应的目录项记录,因为12<20<209,所以定位到页9。
  2. 再到页9中,根据二分法快速定位到对应的用户记录。

问题:虽然说目录项记录中只存储主键值和对应的页号,比用户记录需要的空间存储小多了,但是一个页也就16kb,能存放的目录项记录也是有限的,那如果表中的记录数据太多,以至于一个数据页不足以存放所有的目录项记录,该怎么办?

4.3 当一个页目录不够的时候怎么办

当然是再准备一个目录页啦,~ 为了⼤家更好的理解新分配⼀个⽬录项记录⻚的过程,我们假设⼀个存储⽬录项记录的⻚最多只能存放4条⽬录项记录(请 注意是假设哦,真实情况下可以存放好多条的),所以如果此时我们再向上图中插⼊⼀条主键值为320的⽤户记录的话,那就需要分配⼀个新的存储⽬录项记录的⻚喽:

从图中可以看出,我们插入一个主键值为320的时候需要两个数据页:

  • 为存储该记录,新增页31
  • 因为原先存储的目录项记录30已经满了,所以新生成一个目录项页32

假设我们还是要查找主键为20的记录,大致步骤分以下几步:

  1. 确定目录项记录页(先确定记录在哪个目录页内),我们现在的存储⽬录项记录的⻚有两个,即⻚30和⻚32,⼜因为⻚30表示的⽬录项的主键值的范围是[1, 320),⻚32表示的⽬录项的主键值不⼩于320,所以 主键值为20的记录对应的⽬录项记录在⻚30中。
  2. 确定记录所在页(确定真实记录在哪个页内),在一个存储目录项记录的页中通过主键值二分法定位的一条目录项记录
  3. 在数据页中查找主键为20的记录

4.4 当一层页目录越来越多时怎么办

问题:如果数据量特别大,目录页就会越来越多,查询性能就会低下,这时候怎么办?

给页目录再生成一个目录,就像这样:

如图,我们⽣成了⼀个存储更⾼级⽬录项的⻚33,这个⻚中的两条记录分别代表⻚30和⻚32,如果⽤户记录的主键值在[1, 320)之间,则到⻚30中查找更详细的⽬ 录项记录,如果主键值不⼩于320的话,就到⻚32中查找更详细的⽬录项记录。

如果画的更加好一点,最终的样子是这样的:

这玩意是不是长得特别像倒过来的数呀,上头是树根,下头是树叶,我们称之为 B+数

无论是存放用户记录的数据页还是存放目录像记录的数据页,都放到这个B+数结构中了,所以我们都称之为节点。**从图中我们可以看出用户记录时存放到B+树最底层的节点上,我们称之为叶子节点。**其余用来存放目录项的节点称之为非叶子节点。

存储能力:

4.5 常说的聚簇索引是什么

我们上边介绍的B+树本身就是一个目录,或者说本身就是一个索引,它有两个特点:

  1. 使用记录主键值的大小进行记录和页的排序,这包括以下三个方面的含义:
    • ⻚内的记录是按照主键的⼤⼩顺序排成⼀个单向链表。
    • 各个存放⽤户记录的⻚也是根据⻚中⽤户记录的主键⼤⼩顺序排成⼀个双向链表。
    • 存放⽬录项记录的⻚分为不同的层次,在同⼀层次中的⻚也是根据⻚中⽬录项记录的主键⼤⼩顺序排成⼀个双向链表。
  2. B+树的叶子节点存储的是完整的用户记录(这个记录中存储了所有列的值

我们把具有这两种特性B+树称之为聚簇索引 。所有完整的⽤户记录都存放在这个聚簇索引的叶⼦节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使⽤INDEX 语句去创建(后边会介绍索引相关的语句),InnoDB存储引擎会⾃动的为我们创建聚簇索引。另外有趣的⼀点是,在InnoDB存储引擎中,聚簇索引就是数据的存储 ⽅式(所有的⽤户记录都存储在了叶⼦节点),也就是所谓的索引即数据,数据即索引。

4.6 二级索引

问题:上面所说的索引都是围绕主键建立的,当搜索条件是其他列怎么办?

我们可以多建⼏棵B+树,不同的B+树中的数据采⽤不同的排序规则。⽐⽅说我们⽤c2列的⼤⼩作为数据⻚、⻚中记录的排序规则,再建⼀棵B+树,效果如下 图所示:

这个B+树与上面说的聚簇索引有几处不同:

  1. 页内使用记录c2列的大小顺序成一个单链表
  2. 各个存放⽤户记录的⻚也是根据⻚中记录的c2列列⼤⼩顺序排成⼀个双向链表。
  3. 存放⽬录项记录的⻚分为不同的层次,在同⼀层次中的⻚也是根据⻚中⽬录项记录的c2列⼤⼩顺序排成⼀个双向链表。
  4. B+树的叶子节点存储的并不是完整的用户记录,而只是c2列+主键这两个列的值。
  5. 目录像记录中也不再是主键+页号的搭配,而变成了c2列+页号的搭配。

假设我们现在想通过c2列为4的记录为例,查找过程如下:

  1. 根据最高层级的页44确定下一级的目录页42,因为(2<4<9)
  2. 根据页42可以找到真实数据所在的页
    在页42中可以快速定位到实际存储用户记录的页,但是由于c2列并没有唯一性约束,所以c2列值为4的记录可能分布在多个数据页中,又因为2<4<=4,所以可以确定用户记录存放到页34和页35
  3. 到真实页之后,再通过二分法槽找到具体的记录
  4. 最重要的一步二级索引的就是回表:根据主键再去聚簇索引中查找一遍完整的用户记录

问题:为什么用回表操作,不是将数据存储到叶子节点那?

如果把完整的⽤户记录放到叶⼦节点是可以不⽤回表,但是太占地 ⽅了呀~相当于每建⽴⼀棵B+树都需要把所有的⽤户记录再都拷⻉⼀遍,这就有点太浪费存储空间了。因为这种按照⾮主键列建⽴的B+树需要⼀次回表操作才可以 定位到完整的⽤户记录,所以这种B+树也被称为⼆级索引(英⽂名secondary index),或者辅助索引。由于我们使⽤的是c2列的⼤⼩作为B+树的排序规则,所以 我们也称这个B+树为为c2列建⽴的索引。

4.7 联合索引

我们也可以同时以多个列的大小作为排序规则,建立索引,比方说我们想让B+树按照c2和c3列的大小进行排序,这个包含两层含义:

  1. 先把各个记录和页按照c2列排序
  2. 在c2列相同的情况下,采用c3列进行排序

为c2列和c3列建立的索引的示意图如图:

如图所示,我们 需要注意以下几点:

  • 每个目录项记录都是由c2、c3和页号组成,各条记录先按照c2排序,再按照c3排序
  • 叶子节点是由c2、c3和主键c1组成。

其实,本质也是个二级索引,只是无论目录项记录还是数据页记录多了个列而已。

5.InnoDB索引细节

5.1 索引的生成过程 (比较重要)

  1. 每当为某个表创建一个B+树索引的时候,就会为这个索引创建一个根节点页面。最开始既没有目录页,也没有数据页。
  2. 随后向表中插入数据时,先把用户记录存储到根节点中。
  3. 继续向根节点插入数据后,此时根节点的数据会复制到一个新的页,比如页a,然后对这个页做页分裂,得到一个新页,比如页b。往后新插入的数据就会放到a或者b中,根节点就升级成了目录页

一个b+树索引的根节点自诞生之日后,就不会再移动。这样只要我们对某个表建⽴⼀个索引,那么它的根节点的⻚号便会被记录 到某个地⽅,然后凡是InnoDB存储引擎需要⽤到这个索引的时候,都会从那个固定的地⽅取出根节点的⻚号,从⽽来访问这个索引。

⼩贴⼠: 跟⼤家剧透⼀下,这个存储某个索引的根节点在哪个⻚⾯中的信息就是传说中的数据字典中的⼀项信息,关于更多数据字典的内容, 后边会详细唠叨,别着急哈。

5.2 非唯一二级索引

如果我们的数据是这样的:

如果二级索引中目录项记录的内容只是索引列+页号的话,那么图示:

这时候,如果我们想插入一行记录(9,1,‘c’),那么这个时候遇到一个很大的问题,这时候这条记录是插到页4还是页5那?

为了能够让插入的记录能找到自己所在的页,**我们需要保证B+树同一层节点的目录项记录除了页号以外这条记录是唯一的。**所以这时候我们需要再加入一个列:主键。

也就是我们把主键值也添加到⼆级索引内节点中的⽬录项记录了,这样就能保证B+树每⼀层节点中各条⽬录项记录除⻚号这个字段外是唯⼀的,所以我们为c2列建 ⽴⼆级索引后的示意图实际上应该是这样⼦的:

这时候,当我们想插入一条(9,1,‘c’)时,先比较c2列,如果c2列是一样的,再比较主键列,主键列肯定是不一样的,9>7,所以新纪录应该被插入到页5中。

6.总结

6.1 如果没有索引的查找会是很恐怖的,无论是在一个页还是多个页中查找,基本都是遍历的逻辑。

6.2 当我们想通过建立一个类似书籍目录一样的结构来索引数据页的时候,会存在很多问题,比如耗空间、多一种设计实现方式

6.3 最终,我们通过复用数据页的结构来索引数据页,这个叫做目录页,目录页的主要作用就是索引页

6.4 不同的索引具体实现方式

  • 聚簇索引,数据页主键+用户记录,目录页主键+页号
  • 二级唯一索引:数据页排序列+主键,目录页排序列+主键
  • 二级非唯一索引:数据页排序列+主键,目录页排序列+主键+页号 (非唯一的话,目录页多个主键列
  • 联合索引:数据页排序列1+排序列2+主键,目录页排序列1+排序列2+页号

6.5索引的生成方式

参照 5.1,结束peace

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

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

相关文章

Linux系统磁盘扩容——类型(二)

类型&#xff08;二&#xff09;扩容磁盘到现有逻辑分区目录 查看磁盘空间删除现有逻辑分区再次查看磁盘分区大小更新分区大小 查看磁盘空间 lsblk df -h图中扩容sda磁盘&#xff0c;260G已分配250G&#xff0c;还10G未分配&#xff0c;需要分配到逻辑分区5中。 删除现有逻辑…

基于逻辑回归和支持向量机的前馈网络进行乳腺癌组织病理学图像分类

CNN&#xff08;卷积神经网络&#xff09;通过使用反向传播方法来学习特征&#xff0c;这种方法需要大量的训练数据&#xff0c;并且存在梯度消失问题&#xff0c;从而恶化了特征学习。 CNN卷积神经网络 CNN由一个多层神经网络组成&#xff0c;该网络从标记的训练数据集中学习…

redis 集群模式(redis cluster)介绍

目录 一 redis cluster 相关定义 1&#xff0c; redis cluster 是什么 2&#xff0c;redis 集群的组成 3&#xff0c;集群的作用 4&#xff0c;集群架构图 二 Redis集群的数据分片 1&#xff0c;哈希槽是什么 2&#xff0c;哈希槽如何排布 3&#xff0c;Redis集…

iOS 开发中上传 IPA 文件的方法(无需 Mac 电脑)

引言 在 iOS 开发中&#xff0c;将 IPA 文件上传到苹果开发者中心是一个重要的步骤。通常情况下&#xff0c;我们需要使用 Mac 电脑上的 Xcode 或 Application Loader 工具来完成这个任务。然而&#xff0c;如果你没有 Mac 电脑&#xff0c;也没有关系&#xff0c;本文将介绍一…

天软特色因子看板 (2024.4 第2期)

该因子看板跟踪天软特色因子A05005(近一月单笔流出金额占比(%)&#xff0c;该因子为近一月单笔流出金额占比(% 均值因子&#xff0c;用以刻画下跌时的 单成交中可能存在的抄底现象 今日为该因子跟踪第2期&#xff0c;跟踪其在SH000905 (中证500) 中的表现&#xff0c;要点如下 …

【问题处理】银河麒麟操作系统实例分享,ipelbats转发端口访问ftp目录空白问题处理

1.问题环境 系统环境 物理机 网络环境 私有网络 硬件环境 处理器 arm 软件环境 操作系统版本 V10-SP1-0518-arm 内核版本 4.19.90-23.15.ky10.aarch64 2.问题描述 iptables转发端口访问ftp目录空白&#xff0c;同一个脚本在redhat7.8上正常 2023/2/27&#xff0…

由近期 RAGFlow 的火爆看 RAG 的现状与未来

4 月 1 日&#xff0c;InfiniFlow &#xff08;英飞流&#xff09;的端到端 RAG 解决方案 RAGFlow 正式开源&#xff0c;首日即获得了 github 千星&#xff0c;目前已接近 3000 star。在这之前&#xff0c;InfiniFlow 还开源了专门用于 RAG 场景的 AI 原生数据库 Infinity&…

autodl常用工具命令

以下内容仅为当前认识&#xff0c;可能有不足之处&#xff0c;欢迎讨论&#xff01; 文章目录 tar/zip命令镜像版本参考torch包全版本下载torch和cuda版本对应conda命令conda打包conda 环境重命名conda环境复制和转移conda环境删除 tar/zip命令 参考链接 文件目录打包&#x…

加州大学欧文分校英语基础语法专项课程03:Simple Past Tense 学习笔记(完结)

Learn English: Beginning Grammar Specialization Specialization Certificate course 3&#xff1a; Simple Past Tense Course Certificate 本文是学习 https://www.coursera.org/learn/simple-past-tense 这门课的学习笔记&#xff0c;如有侵权&#xff0c;请联系删除。…

爬虫入门教程(一)

爬虫入门教程 1.什么是爬虫 爬虫是一种自动获取网站数据的程序或脚本。它可以自动模拟人类访问网站,获取网页源代码,解析并提取出所需的数据。 爬虫的工作原理类似于搜索引擎的索引程序&#xff0c;它们会按照预定的规则和算法在互联网上不断地爬取网页&#xff0c;收集信息…

mysql 查询变量@i:=@i+1

学习完mysql的查询&#xff1a;基本查询&#xff0c;连接查询和子查询和mysql 正则表达式查询&#xff0c;接下来先学习下变量查询。 mysql中没有oracle序列号那一列。mysql可以使用查询变量的方式去处理。我们先了解下查询变量&#xff0c;后面应用起来就更清晰。 1&#xff0…

盘点那些好用的SAP FIORI App (五)-管理银行账户

SAP的ECC系统里面&#xff0c;House Bank银行账户的维护是在GUI通过T-Code FI12进行创建修改的&#xff0c;但是升级到S4 HANA以后&#xff0c;FI12的创建维护功能已经取消&#xff0c;所有的house bank account,都要通过这个FIORI App 维护。 App ID 如下 银行账户创建 点击…

【Linux 命令】内核、驱动调试手段总结

文章目录 1. printk2. strace3. Itrace4. ptrace5. ftrace6. 动态打印7. perf8. devmem9. demsg参考&#xff1a; 1. printk **printk()**是 Linux 内核中最广为人知的函数之一。它是我们打印消息的标准工具&#xff0c;通常也是追踪和调试的最基本方法。 虽然 printk() 是基…

Stable diffusion 初学者指南

1. Stable diffusion 初学者指南 想掌握Stable Diffusion AI技术吗&#xff1f; 这份初学者指南专为完全没接触过Stable Diffusion或任何AI图像生成器的新手设计。跟随本指南&#xff0c;你将了解Stable Diffusion的基本情况&#xff0c;并获得一些实用的入门技巧。 什么是S…

JavaWeb流行框架(代码案例)

Struts2基础 通过Struts2将请求转发到指定JSP页面 <% page language"java" contentType"text/html; charsetUTF-8"pageEncoding"UTF-8"%> <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://w…

Codeforces Round 938 (Div. 3) (A~E)

Codeforces Round 938 (Div. 3) (A~E) 目录&#xff1a;A B C D E A题&#xff1a;Yogurt Sale 标签: 数学&#xff08;math&#xff09; 题目大意 酸奶价格&#xff0c; a 元一份&#xff0c;b元两份n问&#xff1a;买n份最少多少钱 思路 a元一份&#xff0c;b元两份&#…

js获取上周本周下周的日期(附Demo)

目录 前言1. 基本知识2. Demo3. 彩蛋 前言 现在的时间点是&#xff1a;2024-04-08&#xff0c;对应的日期如下&#xff08;上周、这周、下周&#xff09; 1. 基本知识 讲述Demo之前&#xff0c;先补充一些基础知识 JavaScript 中的 Date 对象是用于处理日期和时间的对象。它…

【ensp】VLAN间通信的解决办法

VLAN间通信简介 VLAN间三层通信是指在VLAN网络中&#xff0c;不同VLAN之间进行通信的过程。 我们知道VLAN是虚拟局域网&#xff0c;在一个局域网内我们是通过Mac地址进行通信&#xff0c;在局域网与局域网之间通过IP地址来通信&#xff0c;大致过程如下&#xff1a; 主机在发…

【SERVERLESS】搭建ServerLess服务

目录 一、前言 二、什么是ServerLess? 三、ServerLess技术选型 四、ServerLess基础服务搭建 Mac安装示例&#xff1a; Windows安装说明&#xff1a; 五、生成ServerLess应用 六、ServerLess部署 验证并访问函数应用 七、ServerLess进阶演示 八、ServerLess最后总结 …

芒果YOLOv8改进组合157:动态标签分配ATSS+新颖高效AsDDet检测头组合改进,共同助力VisDrone涨点1.8%,小目标高效涨点

💡本篇内容:【芒果YOLOv8改进ATSS标签分配策略|第三集】芒果YOLOv8改进组合157:动态标签分配ATSS+新颖高效AsDDet检测头组合改进,共同助力VisDrone涨点1.8%,小目标高效涨点 💡🚀🚀🚀本博客 标签分配策略ATSS改进+ 新颖高效AsDDet检测头组合改进,适用于 YOLOv8 …