我的编程空间,编程开发者的网络收藏夹
学习永远不晚

MySQL中B+树索引的作用是什么

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

MySQL中B+树索引的作用是什么

本篇文章给大家分享的是有关MySQL中B+树索引的作用是什么,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

树的简介

树的简介

树跟数组、链表、堆栈一样,是一种数据结构。它由有限个节点,组成具有层次关系的集合。因为它看起来像一棵树,所以得其名。一颗普通的树如下:

MySQL中B+树索引的作用是什么

树是包含n(n为整数,大于0)个结点, n-1条边的有穷集,它有以下特点:

  • 每个结点或者无子结点或者只有有限个子结点;

  • 有一个特殊的结点,它没有父结点,称为根结点;

  • 每一个非根节点有且只有一个父节点;

  • 树里面没有环路

一些有关于树的概念:

  • 结点的度:一个结点含有的子结点个数称为该结点的度;

  • 树的度:一棵树中,最大结点的度称为树的度;

  • 父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点;

  • 深度:对于任意结点n,n的深度为从根到n的唯一路径长,根结点的深度为0;

  • 高度:对于任意结点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;

树的种类

MySQL中B+树索引的作用是什么

按照有序性,可以分为有序树和无序树:

  • 无序树:树中任意节点的子结点之间没有顺序关系

  • 有序树:树中任意节点的子结点之间有顺序关系

按照节点包含子树个数,可以分为B树和二叉树,二叉树可以分为以下几种:

  • 二叉树:每个节点最多含有两个子树的树称为二叉树;

  • 二叉查找树:首先它是一颗二叉树,若左子树不空,则左子树上所有结点的值均小于它的根结点的值;若右子树不空,则右子树上所有结点的值均大于它的根结点的值;左、右子树也分别为二叉排序树;

  • 满二叉树:叶节点除外的所有节点均含有两个子树的树被称为满二叉树;

  • 完全二叉树:如果一颗二叉树除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布

  • 霍夫曼树:带权路径最短的二叉树。

  • 红黑树:红黑树是一颗特殊的二叉查找树,每个节点都是黑色或者红色,根节点、叶子节点是黑色。如果一个节点是红色的,则它的子节点必须是黑色的。

  • 平衡二叉树(AVL):一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树

B-树、B+树简介

B-树简介

B-树,也称为B树,是一种平衡的多叉树(可以对比一下平衡二叉查找树),它比较适用于对外查找。看下这几个概念哈:

  • 阶数:一个节点最多有多少个孩子节点。(一般用字母m表示)

  • 关键字:节点上的数值就是关键字

  • 度:一个节点拥有的子节点的数量。

一颗m阶的B-树,有以下特征:

  • 根结点至少有两个子女;

  • 每个非根节点所包含的关键字个数 j 满足:&lceil;m/2&rceil; - 1 <= j <= m - 1.(&lceil;&rceil;表示向上取整)

  • 有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。

  • 所有的叶子结点都位于同一层。

一棵简单的B-树如下:

MySQL中B+树索引的作用是什么

B+ 树简介

B+树是B-树的变体,也是一颗多路搜索树。一棵m阶的B+树主要有这些特点:

  • 每个结点至多有m个子女;

  • 非根节点关键值个数范围:&lceil;m/2&rceil; - 1 <= k <= m-1

  • 相邻叶子节点是通过指针连起来的,并且是关键字大小排序的。

一颗3阶的B+树如下:

MySQL中B+树索引的作用是什么

B+树和B-树的主要区别如下:

  • B-树内部节点是保存数据的;而B+树内部节点是不保存数据的,只作索引作用,它的叶子节点才保存数据。

  • B+树相邻的叶子节点之间是通过链表指针连起来的,B-树却不是。

  • 查找过程中,B-树在找到具体的数值以后就结束,而B+树则需要通过索引找到叶子结点中的数据才结束

  • B-树中任何一个关键字出现且只出现在一个结点中,而B+树可以出现多次。

B+树的插入

B+树插入要记住这几个步骤:

  • 1.B+树插入都是在叶子结点进行的,就是插入前,需要先找到要插入的叶子结点。

  • 2.如果被插入关键字的叶子节点,当前含有的关键字数量是小于阶数m,则直接插入。

  • 3.如果插入关键字后,叶子节点当前含有的关键字数目等于阶数m,则插,该节点开始「分裂」为两个新的节点,一个节点包含&lfloor;m/2&rfloor;  个关键字,另外一个关键字包含&lceil;m/2&rceil;个关键值。(&lfloor;m/2&rfloor;表示向下取整,&lceil;m/2&rceil;表示向上取整,如&lceil;3/2&rceil;=2)。

  • 4.分裂后,需要将第&lceil;m/2&rceil;的关键字上移到父结点。如果这时候父结点中包含的关键字个数小于m,则插入操作完成。

  • 5.分裂后,需要将&lceil;m/2&rceil;的关键字上移到父结点。如果父结点中包含的关键字个数等于m,则继续分裂父结点。

以一颗4阶的B+树为例子吧,4阶的话,关键值最多3(m-1)个。假设插入以下数据43,48,36,32,37,49,28.

1.在空树中插入43

MySQL中B+树索引的作用是什么

这时候根结点就一个关键值,此时它是根结点也是叶子结点。

2.依次插入48,36

MySQL中B+树索引的作用是什么

这时候跟节点拥有3个关键字,已经满了

3.继续插入 32,发现当前节点关键字已经不小于阶数4了,于是分裂 第&lceil;4/2&rceil;=2(下标0,1,2)个,也即43上移到父节点。

MySQL中B+树索引的作用是什么

4.继续插入37,49,前节点关键字都是还没满的,直接插入,如下:

MySQL中B+树索引的作用是什么

5.最后插入28,发现当前节点关键字也是不小于阶数4了,于是分裂,于是分裂, 第  &lceil;4/2&rceil;=2个,也就是36上移到父节点,因父子节点只有2个关键值,还是小于4的,所以不用继续分裂,插入完成

MySQL中B+树索引的作用是什么

B+树的查找

因为B+树的数据都是在叶子节点上的,内部节点只是指针索引的作用,因此,查找过程需要搜索到叶子节点上。还是以这颗B+树为例吧:

MySQL中B+树索引的作用是什么

B+ 树单值查询

假设我们要查的值为32.

第一次磁盘 I/O,查找磁盘块1,即根节点(36,43),因为32小于36,因此访问根节点的左边第一个孩子节点

MySQL中B+树索引的作用是什么

第二次磁盘 I/O, 查找磁盘块2,即根节点的第一个孩子节点,获得区间(28,32),遍历即可得32.

MySQL中B+树索引的作用是什么

动态图如下:

MySQL中B+树索引的作用是什么

B+ 树范围查询

假设我们要查找区间 [32,40]区间的值.

第一步先访问根节点,发现区间的左端点32小于36,则访问根节点的第一个左子树(28,32);

MySQL中B+树索引的作用是什么

第二步访问节点(28,32),找到32,于是开始遍历链表,把[32,40]区间值找出来,这也是B+树比B-树高效的地方。

MySQL中B+树索引的作用是什么

B+树的删除

B+树删除关键字,分这几种情况

  • 找到包含关键值的结点,如果关键字个数大于&lceil;m/2&rceil;-1,直接删除即可;

  • 找到包含关键值的结点,如果关键字个数大于&lceil;m/2&rceil;-1,并且关键值是当前节点的最大(小)值,并且该关键值存在父子节点中,那么删除该关键字,同时需要相应调整父节点的值。

  • 找到包含关键值的结点,如果删除该关键字后,关键字个数小于&lceil;m/2&rceil;,并且其兄弟结点有多余的关键字,则从其兄弟结点借用关键字

  • 找到包含关键值的结点,如果删除该关键字后,关键字个数小于&lceil;m/2&rceil;,并且其兄弟结点没有多余的关键字,则与兄弟结点合并。

如果关键字个数大于&lceil;m/2&rceil;,直接删除即可;

假设当前有这么一颗5阶的B+树

MySQL中B+树索引的作用是什么

如果删除22,因为关键字个数为3 > &lceil;5/2&rceil;-1=2, 直接删除(&lceil;&rceil;表示向上取整的意思)

MySQL中B+树索引的作用是什么

如果关键字个数大于&lceil;m/2&rceil;-1,并且删除的关键字存在于父子节点中,那么需要相应调整父子节点的值

MySQL中B+树索引的作用是什么

如果删除20,因为关键字个数为3 > &lceil;5/2&rceil;-1=2,并且20是当前节点的边界值,且存在父子节点中,所以删除后,其父子节点也要响应调整。

MySQL中B+树索引的作用是什么

如果删除该关键字后,关键字个数小于&lceil;m/2&rceil;-1,兄弟节点可以借用

以下这颗5阶的B+树,

MySQL中B+树索引的作用是什么

如果删除15,删除关键字的结点只剩1个关键字,小于&lceil;5/2&rceil;-1=2,不满足B+树特点,但是其兄弟节点拥有3个元素(7,8,9),可以借用9过来,如图:

MySQL中B+树索引的作用是什么

在删除关键字后,如果导致其结点中关键字个数不足,并且兄弟结点没有得借用的话,需要合并兄弟结点

以下这颗5阶的B+树:

MySQL中B+树索引的作用是什么

如果删除关键字7,删除关键字的结点只剩1个关键字,小于&lceil;5/2&rceil;-1=2,不满足B+树特点,并且兄弟结点没法借用,因此发生合并,如下:

MySQL中B+树索引的作用是什么

主要流程酱紫:

  • 因为7被删掉后,只剩一个8的关键字,不满足B+树特点(&lceil;m/2&rceil;-1<=关键字<=m-1)。

  • 并且没有兄弟结点关键字借用,因此8与前面的兄弟结点结合。

  • 被删关键字结点的父节点,7索引也被删掉了,只剩一个9,并且其右兄弟结点(18,20)只有两个关键字,也是没得借,因此在此合并。

  • 被删关键字结点的父子节点,也和其兄弟结点合并后,只剩一个子树分支,因此根节点(16)也下移了。

所以删除关键字7后的结果如下:

MySQL中B+树索引的作用是什么

B+树经典面试题

  • InnoDB一棵B+树可以存放多少行数据?

  • 为什么索引结构默认使用B+树,而不是hash,二叉树,红黑树,B-树?

  • B-树和B+树的区别

InnoDB一棵B+树可以存放多少行数据?

这个问题的简单回答是:约2千万行。

  • 在计算机中,磁盘存储数据最小单元是扇区,一个扇区的大小是512字节。

  • 文件系统中,最小单位是块,一个块大小就是4k;

  • InnoDB存储引擎最小储存单元是页,一页大小就是16k。

MySQL中B+树索引的作用是什么

因为B+树叶子存的是数据,内部节点存的是键值+指针。索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中,进而再去数据页中找到需要的数据;

MySQL中B+树索引的作用是什么

假设B+树的高度为2的话,即有一个根结点和若干个叶子结点。这棵B+树的存放总记录数为=根结点指针数*单个叶子节点记录行数。

  • 如果一行记录的数据大小为1k,那么单个叶子节点可以存的记录数 =16k/1k =16.

  • 非叶子节点内存放多少指针呢?我们假设主键ID为bigint类型,长度为8字节,而指针大小在InnoDB源码中设置为6字节,所以就是8+6=14字节,16k/14B  =16*1024B/14B = 1170

因此,一棵高度为2的B+树,能存放1170 * 16=18720条这样的数据记录。同理一棵高度为3的B+树,能存放1170 *1170 *16  =21902400,也就是说,可以存放两千万左右的记录。B+树高度一般为1-3层,已经满足千万级别的数据存储。

为什么索引结构默认使用B+树,而不是B-Tree,Hash哈希,二叉树,红黑树?

简单版回答如下:

  • Hash哈希,只适合等值查询,不适合范围查询。

  • 一般二叉树,可能会特殊化为一个链表,相当于全表扫描。

  • 红黑树,是一种特化的平衡二叉树,MySQL  数据量很大的时候,索引的体积也会很大,内存放不下的而从磁盘读取,树的层次太高的话,读取磁盘的次数就多了。

  • B-Tree,叶子节点和非叶子节点都保存数据,相同的数据量,B+树更矮壮,也是就说,相同的数据量,B+树数据结构,查询磁盘的次数会更少。

B-树和B+树的区别

  • B-树内部节点是保存数据的;而B+树内部节点是不保存数据的,只作索引作用,它的叶子节点才保存数据。

  • B+树相邻的叶子节点之间是通过链表指针连起来的,B-树却不是。

  • 查找过程中,B-树在找到具体的数值以后就结束,而B+树则需要通过索引找到叶子结点中的数据才结束

  • B-树中任何一个关键字出现且只出现在一个结点中,而B+树可以出现多次。

以上就是MySQL中B+树索引的作用是什么,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

MySQL中B+树索引的作用是什么

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

MySQL中B树索引和B+树索引的区别是什么

本文小编为大家详细介绍“MySQL中B树索引和B+树索引的区别是什么”,内容详细,步骤清晰,细节处理妥当,希望这篇“MySQL中B树索引和B+树索引的区别是什么”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。如果用
2023-06-29

B+树在数据库索引中的作用是什么

本篇文章给大家分享的是有关B+树在数据库索引中的作用是什么,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。一、B-树和B+树回顾1.B-树B-tree(多路搜索树)是一种常见的数
2023-06-19

mysql中B+Tree索引的作用是什么

本篇文章给大家分享的是有关mysql中B+Tree索引的作用是什么,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。1、概念B+Tree是在B-Tree基础上的一种优化,使其更适合
2023-06-15

为什么MySQL用B+树做索引

索引这个词,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述的很完整。本文就来从头到尾介绍下数据库的索引。 索引是一种数据结构,用于帮助我们在大量数据中快速定位到我们想要查找的数据
为什么MySQL用B+树做索引
2017-02-01

MySQL用B+树(而不是B树)做索引的原因

https://www.jianshu.com/p/7ce804f97967众所周知,MySQL的索引使用了B+树的数据结构。那么为什么不用B树呢?先看一下B树和B+树的区别。1.B树维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结
MySQL用B+树(而不是B树)做索引的原因
2020-03-03

MySQL用B+树作为索引结构有什么好处

前言在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决的问题以及面临的新问题,从而说明MySQL为什么选择B+树作为索引结构。 一
2022-05-18

聊聊为什么MySQL索引使用B+树

mysql的innodb默认会将数据文件以及索引文件放在表格空间中,不会为每一个单独的表保存一份数据文件,如果需要单独保存,那么要将 innodb_file_per_table 设置为on。

mysql索引数据结构要用B+树的原因是什么

这篇文章主要讲解了“mysql索引数据结构要用B+树的原因是什么”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“mysql索引数据结构要用B+树的原因是什么”吧!1. Hash表?No因考虑到
2023-06-30

MySQL索引-B+树是如何生长的

本次会先从一个数据页中如何存储和查询数据开始,拓展到多个数据页中查询数据,分析无索引查询时的低效率问题,然后通过页分裂过渡到主键目录以及索引页相关内容,见证一颗索引树是如何一步步生长起来的。

MySQL的B+树索引的具体使用

目录一、索引概述二、B+树索引三、B+树索引的原理四、B+树索引的优点五、B+树索引的缺点六、索引的创建七、索引的优化一、索引概述在mysql中,索引是一种数据结构,它可以帮助数据库系统更快地检索数据。索引可以比作一本书的目录,它可以让我
MySQL的B+树索引的具体使用
2024-08-27

MySQL-InnoDB为什么采用B+树结构实现索引

索引的作用是提高查询效率,其实现方式有很多种,常见的索引模型有哈希表、有序列表、搜索树等。 哈希表 一种以key-value键值对的方式存储数据的结构,通过指定的key可以找到对应的value。 哈希把值放在数组里,用一个哈希函数把key换算成一个确定位
MySQL-InnoDB为什么采用B+树结构实现索引
2018-07-22

编程热搜

目录