MySQL为什么用b+树

索引是一种数据结构,用于帮助我们在大量数据中快速定位到我们想要查找的数据。 索引最形象的比喻就是图书的目录了。注意这里的大量,数据量大了索引才显得有意义,如果我想要在[1,2,3,4]中找到4这个数据,直接对全数据检索也很快,没有必要费力气建索引再去查找。索引在mysql数据库中分三类:

B+树索引、Hash索引、全文索引

我们今天要介绍的是工作开发中最常接触到innodb存储引擎中的的B+树索引。

要介绍B+树索引,就不得不提二叉查找树,平衡二叉树和B树这三种数据结构。B+树就是从他们仨演化来的。

二叉查找树

首先,让我们先看一张图

从图中可以看到,我们为user表(用户信息表)建立了一个二叉查找树的索引。图中的圆为二叉查找树的节点,节点中存储了键(key)和数据(data)。

键对应user表中的id,数据对应user表中的行数据。二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值,右子节点的键值都大于当前节点的键值。 顶端的节点我们称为根节点,没有子节点的节点我们称之为叶节点。

如果我们需要查找id=12的用户信息,利用我们创建的二叉查找树索引,查找流程如下:

  • \1. 将根节点作为当前节点,把12与当前节点的键值10比较,12大于10,接下来我们把当前节点>的右子节点作为当前节点。

  • \2. 继续把12和当前节点的键值13比较,发现12小于13,把当前节点的左子节点作为当前节点。

  • \3. 把12和当前节点的键值12对比,12等于12,满足条件,我们从当前节点中取出data,即id=12,name=xm。

利用二叉查找树我们只需要3次即可找到匹配的数据。如果在表中一条条的查找的话,我们需要6次才能找到。

平衡二叉树

上面我们讲解了利用二叉查找树可以快速的找到数据。但是,如果上面的二叉查找树是这样的构造:

这个时候可以看到我们的二叉查找树变成了一个链表。

如果我们需要查找id=17的用户信息,我们需要查找7次,也就相当于全表扫描了。

导致这个现象的原因其实是二叉查找树变得不平衡了,也就是高度太高了,从而导致查找效率的不稳定。

为了解决这个问题,我们需要保证二叉查找树一直保持平衡,就需要用到平衡二叉树了。

平衡二叉树又称AVL树,在满足二叉查找树特性的基础上,要求每个节点的左右子树的高度差不能超过1。

下面是平衡二叉树和非平衡二叉树的对比:

由平衡二叉树的构造我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。

平衡二叉树保证了树的构造是平衡的,当我们插入或删除数据导致不满足平衡二叉树不平衡时,平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。

平衡二叉树相比于二叉查找树来说,查找效率更稳定,总体的查找速度也更快。

B树

因为内存的易失性。一般情况下,我们都会选择将user表中的数据和索引存储在磁盘这种外围设备中。

但是和内存相比,从磁盘中读取数据的速度会慢上百倍千倍甚至万倍,所以,我们应当尽量减少从磁盘中读取数据的次数。 另外,从磁盘中读取数据时,都是按照磁盘块来读取的,并不是一条一条的读。

如果我们能把尽量多的数据放进磁盘块中,那一次磁盘读取操作就会读取更多数据,那我们查找数据的时间也会大幅度降低。

如果我们用树这种数据结构作为索引的数据结构,那我们每查找一次数据就需要从磁盘中读取一个节点,也就是我们说的一个磁盘块,我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。

那说明什么?

说明每个磁盘块仅仅存储一个键值和数据!

那如果我们要存储海量的数据呢?

可以想象到二叉树的节点将会非常多,高度也会及其高,我们查找数据时也会进行很多次磁盘IO,我们查找数据的效率将会极低!

为了解决平衡二叉树的这个弊端,我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的B树。

B树(Balance Tree)即为平衡树的意思,下图即是一颗B树。

图中的p节点为指向子节点的指针,二叉查找树和平衡二叉树其实也有,因为图的美观性,被省略了。- 图中的每个节点称为页,页就是我们上面说的磁盘块,在mysql中数据读取的基本单位都是页,所以我们这里叫做页更符合mysql中索引的底层数据结构。

从上图可以看出,B树相对于平衡二叉树,每个节点存储了更多的键值(key)和数据(data),并且每个节点拥有更多的子节点,子节点的个数一般称为阶,上述图中的B树为3阶B树,高度也会很低。

基于这个特性,B树查找数据读取磁盘的次数将会很少,数据的查找效率也会比平衡二叉树高很多。

假如我们要查找id=28的用户信息,那么我们在上图B树中查找的流程如下:

  • \1. 先找到根节点也就是页1,判断28在键值17和35之间,我们那么我们根据页1中的指针p2找到页3。

  • \2. 将28和页3中的键值相比较,28在26和30之间,我们根据页3中的指针p2找到页8。

  • \3. 将28和页8中的键值相比较,发现有匹配的键值28,键值28对应的用户信息为(28,bv)。

B+树

B+树是对B树的进一步优化。让我们先来看下B+树的结构图:

根据上图我们来看下B+树和B树有什么不同。

\1. B+树非叶子节点上是不存储数据的,仅存储键值,而B树节点中不仅存储键值,也会存储数据。之所以这么做是因为在数据库中页的大小是固定的,innodb中页的默认大小是16KB。如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的IO次数有会再次减少,数据查询的效率也会更快。另外,B+树的阶数是等于键值的数量的,如果我们的B+树一个节点可以存储1000个键值,那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的,所以一般我们查找10亿数据,只需要2次磁盘IO。

\2. 因为B+树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的。那么B+树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点,要实现这一点是很不容易的。

有心的读者可能还发现上图B+树中各个页之间是通过双向链表连接的,叶子节点中的数据是通过单向链表连接的。

其实上面的B树我们也可以对各个节点加上链表。其实这些不是它们之前的区别,是因为在mysql的innodb存储引擎中,索引就是这样存储的。也就是说上图中的B+树索引就是innodb中B+树索引真正的实现方式,准确的说应该是聚集索引(聚集索引和非聚集索引下面会讲到)。

通过上图可以看到,在innodb中,我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

MyISAM中的B+树索引实现与innodb中的略有不同。在MyISAM中,B+树索引的叶子节点并不存储数据,而是存储数据的文件地址。

聚集索引 VS 非聚集索引

在上节介绍B+树索引的时候,我们提到了图中的索引其实是聚集索引的实现方式。那什么是聚集索引呢?

在MySQL中,B+树索引按照存储方式的不同分为聚集索引非聚集索引

这里我们着重介绍innodb中的聚集索引和非聚集索引。

\1. 聚集索引(聚簇索引):以innodb作为存储引擎的表,表中的数据都会有一个主键,即使你不创建主键,系统也会帮你创建一个隐式的主键。这是因为innodb是把数据存放在B+树中的,而B+树的键值就是主键,在B+树的叶子节点中,存储了表中所有的数据。这种以主键作为B+树索引的键值而构建的B+树索引,我们称之为聚集索引

\2. 非聚集索引(非聚簇索引):以主键以外的列值作为键值构建的B+树索引,我们称之为非聚集索引。非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据,而是存储该列对应的主键,想要查找数据我们还需要根据主键再去聚集索引中进行查找,这个再根据聚集索引查找数据的过程,我们称为回表

明白了聚集索引和非聚集索引的定义,我们应该明白这样一句话:数据即索引,索引即数据

利用聚集索引和非聚集索引查找数据

前面我们讲解B+树索引的时候并没有去说怎么在B+树中进行数据的查找,主要就是因为还没有引出聚集索引和非聚集索引的概念。下面我们通过讲解如何通过聚集索引以及非聚集索引查找数据表中数据的方式介绍一下B+树索引查找数据方法。

利用聚集索引查找数据

还是这张B+树索引图,现在我们应该知道这就是聚集索引,表中的数据存储在其中。现在假设我们要查找id>=18并且id<40的用户数据。对应的sql语句为select * from user where id>=18 and id <40,其中id为主键。具体的查找过程如下:

  • \1. 一般根节点都是常驻内存的,也就是说页1已经在内存中了,此时不需要到磁盘中读取数据,直接从内存中读取即可。

    从内存中读取到页1,要查找这个id>=18 and id <40或者范围值,我们首先需要找到id=18的键值。

    从页1中我们可以找到键值18,此时我们需要根据指针p2,定位到页3。

  • \2. 要从页3中查找数据,我们就需要拿着p2指针去磁盘中进行读取页3。

    从磁盘中读取页3后将页3放入内存中,然后进行查找,我们可以找到键值18,然后再拿到页3中的指针p1,定位到页8。

  • \3. 同样的页8页不在内存中,我们需要再去磁盘中将页8读取到内存中。

    将页8读取到内存中后。

    因为页中的数据是链表进行连接的,而且键值是按照顺序存放的,此时可以根据二分查找法定位到键值18。

    此时因为已经到数据页了,此时我们已经找到一条满足条件的数据了,就是键值18对应的数据。

    因为是范围查找,而且此时所有的数据又都存在叶子节点,并且是有序排列的,那么我们就可以对页8中的键值依次进行遍历查找并匹配满足条件的数据。

    我们可以一直找到键值为22的数据,然后页8中就没有数据了,此时我们需要拿着页8中的p指针去读取页9中的数据。

  • \4. 因为页9不在内存中,就又会加载页9到内存中,并通过和页8中一样的方式进行数据的查找,直到将页12加载到内存中,发现41大于40,此时不满足条件。

    那么查找到此终止。

    最终我们找到满足条件的所有数据为:

    (18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt)。

    总共12条记录。

下面看下具体的查找流程图:

利用非聚集索引查找数据

读者看到这张图的时候可能会蒙,这是啥东西啊?怎么都是数字。

如果有这种感觉,请仔细看下图中红字的解释。什么?还看不懂?那我再来解释下吧。首先,这个非聚集索引表示的是用户幸运数字的索引(为什么是幸运数字?一时兴起想起来的:-)),此时表结构是这样的。

在叶子节点中,不在存储所有的数据了,存储的是键值和主键。

对于叶子节点中的x-y,比如1-1。左边的1表示的是索引的键值,右边的1表示的是主键值。如果我们要找到幸运数字为33的用户信息,对应的sql语句为select * from user where luckNum=33。

查找的流程跟聚集索引一样,这里就不详细介绍了。我们最终会找到主键值47,找到主键后我们需要再到聚集索引中查找具体对应的数据信息,此时又回到了聚集索引的查找流程。

在MyISAM中,聚集索引和非聚集索引的叶子节点都会存储数据的文件地址。

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

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

相关文章

动态盘转换为基本盘

问题描述 不小心将磁盘0&#xff08;C和D是基本盘&#xff0c;蓝颜色&#xff09;改成了动态盘&#xff08;C和D是动态盘&#xff0c;橘黄色&#xff09;&#xff1f;如何修改回来呢&#xff1f; 解决方案&#xff1a; 使用DiskGenius将动态磁盘转换为基本磁盘 操作之前一定…

风电光伏混合储能功率小波包分解、平抑前后波动性分析、容量配置、频谱分析、并网功率波动分析(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

【java|golang】多字段排序以及排序规则

奖励最顶尖的 K 名学生 给你两个字符串数组 positive_feedback 和 negative_feedback &#xff0c;分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。 一开始&#xff0c;每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分&#xff0c;每个负面的词…

智慧空开让用电更安全、管理更智能——电脑APP远程控制开合闸

安科瑞 崔丽洁 01 什么是低压断路器&#xff1f;低压断路器的定义是&#xff1a;能够接通、承载及分断正常电路条件下的电流&#xff0c;也能在规定的非正常电路条件&#xff08;过载、短路、特别是短路&#xff09;下接通、承载一定时间和分断电流的开关电器。 断路器的分类&…

拼多多商品品牌数据接口,拼多多商品详情数据接口,拼多多优惠券数据接口,拼多多API接口

拼多多商品品牌数据采集方法如下&#xff1a; 手动数据采集。直接在拼多多平台上搜索并手动复制商品数据&#xff0c;适合采集小批量的商品数据&#xff0c;但不适用于大规模数据采集。手动采集需要手动输入搜索词&#xff0c;进行筛选后再复制所需的数据&#xff0c;该方法需…

白银做期货还是做现货?

现货白银和期货白银都是保证金交易品种&#xff0c;都具有一定的资金杠杆&#xff0c;新手投资者在它们之间进行选择的时候&#xff0c;可能会遇到一定的困难&#xff0c;但是只要投资者真正了解过它们的区别&#xff0c;在选择时思路就会更加清晰&#xff0c;能够根据自己的实…

Stable Diffusion XL搭建

本文参考&#xff1a;Stable Diffusion XL1.0正式发布了&#xff0c;赶紧来尝鲜吧-云海天教程 Stable Diffision最新模型SDXL 1.0使用全教程 - 知乎 1、SDXL与SD的区别 &#xff08;1&#xff09;分辨率得到了提升 原先使用SD生成图片&#xff0c;一般都是生成512*512&…

VMWare配置桥接

一、设置网络模式 二、编辑网卡配置 ip配置的子网掩码和默认网关保持和宿主机一致&#xff0c;ip局域网内不冲突。 # cd /etc/sysconfig/network-scriptslsvim ifcfg-ens160 TYPEEthernet PROXY_METHODnone BROWSER_ONLYno BOOTPROTOnone DEFROUTEyes IPV4_FAILURE_FATALno IP…

hive 之select 中文乱码

此处的中文乱码和mysql的库表 编码 latin utf 无关。 直接上案例。 有时候我们需要自定义一列&#xff0c;有时是汉字有时是字母&#xff0c;结果遇到这种情况了。 说实话看到这真是糟心。这谁受得了。 单独select 没有任何问题。 这是怎么回事呢&#xff1f; 经过一番检查&…

C++11新特性(lambda,可变参数模板,包装器,bind)

lambda表达式是什么&#xff1f;包装器又是什么&#xff1f;有什么作用&#xff1f;莫急&#xff0c;此篇文章将详细带你探讨它们的作用。很多同学在学习时害怕这些东西&#xff0c;其实都是方便使用的工具&#xff0c;很多情况下我们学这些新的东西觉得麻烦&#xff0c;累赘&a…

服务器数据恢复-DS5300存储raid5硬盘出现坏道离线的数据恢复案例

服务器数据恢复环境&#xff1a; 某单位一台DS5300存储&#xff0c;1个主机4个扩展柜&#xff0c;组建了2组RAID5&#xff08;一组27块硬盘&#xff0c;一组23块盘&#xff09;。27块盘的那组RAID5阵列存放Oracle数据库文件&#xff0c;存储系统一共分了11个卷。 服务器故障&a…

linux C++ vscode连接mysql

1.linux使用Ubuntu 2.Ubuntu安装vscode 2.1 安装的是snap版本,直接打开命令行执行 sudo snap install --classic code 3.vscode配置C 3.1 直接在扩展中搜索C安装即可 我安装了C, Chinese, code runner, 安装都是同理 4.安装mysql sudo apt update sudo apt install mysql-…

MySQL 安装+启动+报错的解决方案

目录 一、安装准备 1.1 下载 1.2 版本说明 二、安装步骤 2.1 解压缩 2.2 配置环境变量 2.3 配置文件 2.4 安装 2.5 启动/停止服务 三、使用说明 3.1 用户名密码登录 3.1 设置用户名密码 四、卸载步骤 4.1 卸载服务 五、安装问题 六、启动问题 6.1 提示【服务无…

Docker部署gitlab_ce(避坑版---社区版)

1 下载docker 2 下载gitlab镜像 3 运行 4 进入容器内部修改 5 在浏览器里访问 6 修改root密码&#xff08;如果忘记请修改&#xff09; 1 下载docker # 安装依赖 yum install -y yum-utils device-mapper-persistent-data lvm2# 设置yum源 yum-config-manager --add-repo https…

国内ITSM发展的趋势

多年来&#xff0c;随着客户业务需求、工作文化、技术创新的不断变化以及新的IT环境的出现&#xff0c; IT支持也出现了新的变化&#xff0c;由单一的IT帮助台&#xff08; IT help desk&#xff09;逐渐转变为了综合性的IT服务台&#xff08; IT service desk&#xff09;&…

Vulnhub系列靶机---Raven: 2

文章目录 信息收集主机发现端口扫描目录扫描用户枚举 漏洞发现漏洞利用UDF脚本MySQL提权SUID提权 靶机文档&#xff1a;Raven: 2 下载地址&#xff1a;Download (Mirror) 信息收集 靶机MAC地址&#xff1a;00:0C:29:15:7F:17 主机发现 sudo nmap -sn 192.168.8.0/24sudo arp…

大数据NoSQL数据库HBase集群部署

目录 1. 简介 2. 安装 1. HBase依赖Zookeeper、JDK、Hadoop&#xff08;HDFS&#xff09;&#xff0c;请确保已经完成前面 2. 【node1执行】下载HBase安装包 3. 【node1执行】&#xff0c;修改配置文件&#xff0c;修改conf/hbase-env.sh文件 4. 【node1执行】&#xf…

Pymol做B因子图

分子动力学模拟结束后&#xff0c;获得蛋白的平均结构&#xff0c; 比如获得的平均结构为WT-average.pdb 然后将平均结构导入到Pymol 中&#xff0c;可以得到B因子图。 gmx rmsf -f md_0_100_noPBC.xtc -s md_0_100.tpr -o rmsf-per-residue.xvg -ox average.pdb -oq bfactors…

【TES720D】基于复旦微的FMQL20S400全国产化ARM核心模块

TES720D是一款基于上海复旦微电子FMQL20S400的全国产化核心模块。该核心模块将复旦微的FMQL20S400&#xff08;兼容FMQL10S400&#xff09;的最小系统集成在了一个50*70mm的核心板上&#xff0c;可以作为一个核心模块&#xff0c;进行功能性扩展&#xff0c;特别是用在控制领域…

2、vscode c++ 项目配置调试及运行

文章目录 1、项目布局2、多项目管理2.1 先是一个总的CMakeLists.txt2.2 每个项目2.3 多版本OPENCV 3、调试和运行 接上一篇文章&#xff0c;vscode和cmake的c环境配置好以后&#xff0c;我们要写项目&#xff0c;再写对应的CMakeLists.txt 1、项目布局 . ├── bin ├── bu…