深入了解 B-Tree 和 B+Tree 的区别

深入了解 B-Tree 和 B+Tree 的区别

大家好,又见面了,我是全栈君。

深入了解 B-Tree 和 B+Tree 的区别

B-Tree

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。

系统从磁盘读取数据到内存时是以磁盘块(block)为基本单位的,位于同一个磁盘块中的数据会被一次性读取出来,而不是需要什么取什么。

InnoDB 存储引擎中有页(Page)的概念,页是其磁盘管理的最小单位。InnoDB 存储引擎中默认每个页的大小为16KB,可通过参数 innodb_page_size 将页的大小设置为 4K、8K、16K,在 MySQL 中可通过如下命令查看页的大小:show variables like 'innodb_page_size';

而系统一个磁盘块的存储空间往往没有这么大,因此 InnoDB 每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小 16KB。InnoDB 在把磁盘数据读入到磁盘时会以页为基本单位,在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置,这将会减少磁盘I/O次数,提高查询效率。

B-Tree 结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述 B-Tree,首先定义一条记录为一个二元组[key, data] ,key为记录的键值,对应表中的主键值,data 为一行记录中除主键外的数据。对于不同的记录,key值互不相同。

一棵m阶的B-Tree有如下特性:

  1. 每个节点最多有m个孩子

  2. 除了根节点和叶子节点外,其它每个节点至少有Ceil(m/2)个孩子。

  3. 若根节点不是叶子节点,则至少有2个孩子

  4. 所有叶子节点都在同一层,且不包含其它关键字信息

  5. 每个非终端节点包含n个关键字信息(P0,P1,…Pn, k1,…kn)

  6. 关键字的个数n满足:ceil(m/2)-1 <= n <= m-1

  7. ki(i=1,…n)为关键字,且关键字升序排序

  8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki,但都大于k(i-1)

B-Tree 中的每个节点根据实际情况可以包含大量的关键字信息和分支,如下图所示为一个 3 阶的 B-Tree:

深入了解 B-Tree 和 B+Tree 的区别

图片:DobbinSoong

每个节点占用一个盘块的磁盘空间,一个节点上有两个升序排序的关键字和三个指向子树根节点的指针,指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例,关键字为17和35,P1指针指向的子树的数据范围为小于17,P2指针指向的子树的数据范围为17~35,P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程:

  1. 根据根节点找到磁盘块1,读入内存。【磁盘I/O操作第1次】

  2. 比较关键字29在区间(17,35),找到磁盘块1的指针P2。

  3. 根据P2指针找到磁盘块3,读入内存。【磁盘I/O操作第2次】

  4. 比较关键字29在区间(26,30),找到磁盘块3的指针P2。

  5. 根据P2指针找到磁盘块8,读入内存。【磁盘I/O操作第3次】

  6. 在磁盘块8中的关键字列表中找到关键字29。

分析上面过程,发现需要3次磁盘I/O操作,和3次内存查找操作。由于内存中的关键字是一个有序表结构,可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数,使每次磁盘I/O取到内存的数据都发挥了作用,从而提高了查询效率。

B+Tree

B+Tree 是在 B-Tree 基础上的一种优化,使其更适合实现外存储索引结构,InnoDB 存储引擎就是用 B+Tree 实现其索引结构。

从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小,当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。在B+Tree中,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,而非叶子节点上只存储key值信息,这样可以大大加大每个节点存储的key值数量,降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同:

  1. 非叶子节点只存储键值信息;

  2. 所有叶子节点之间都有一个链指针;

  3. 数据记录都存放在叶子节点中

将上一节中的B-Tree优化,由于B+Tree的非叶子节点只存储键值信息,假设每个磁盘块能存储4个键值及指针信息,则变成B+Tree后其结构如下图所示:深入了解 B-Tree 和 B+Tree 的区别

通常在B+Tree上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有叶子节点(即数据节点)之间是一种链式环结构。因此可以对B+Tree进行两种查找运算:一种是对于主键的范围查找和分页查找,另一种是从根节点开始,进行随机查找。

可能上面例子中只有22条数据记录,看不出B+Tree的优点,下面做一个推算:

InnoDB存储引擎中页的大小为16KB,一般表的主键类型为INT(占用4个字节)或BIGINT(占用8个字节),指针类型也一般为4或8个字节,也就是说一个页(B+Tree中的一个节点)中大概存储16KB/(8B+8B)=1K个键值(因为是估值,为方便计算,这里的K取值为10^3)。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。

实际情况中每个节点可能不能填充满,因此在数据库中,B+Tree的高度一般都在2-4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的,也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

B+Tree性质

  1. 通过上面的分析,我们知道IO次数取决于b+数的高度h,假设当前数据表的数据为N,每个磁盘块的数据项的数量是m,则有h=㏒(m+1)N,当数据量N一定的情况下,m越大,h越小;而m = 磁盘块的大小 / 数据项的大小,磁盘块的大小也就是一个数据页的大小,是固定的,如果数据项占的空间越小,数据项的数量越多,树的高度越低。这就是为什么每个数据项,即索引字段要尽量的小,比如int占4字节,要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点,一旦放到内层节点,磁盘块的数据项会大幅度下降,导致树增高。当数据项等于1时将会退化成线性表。

  2. 当b+树的数据项是复合的数据结构,比如(name,age,sex)的时候,b+数是按照从左到右的顺序来建立搜索树的,比如当(张三,20,F)这样的数据来检索的时候,b+树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候,b+树就不知道下一步该查哪个节点,因为建立搜索树的时候name就是第一个比较因子,必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时,b+树可以用name来指定搜索方向,但下一个字段age的缺失,所以只能把名字等于张三的数据都找到,然后再匹配性别是F的数据了, 这个是非常重要的性质,即索引的最左匹配特性

深入了解 B-Tree 和 B+Tree 的区别

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/111643.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • php上传文件与图片到七牛的实例详解

    php上传文件与图片到七牛的实例详解

    2021年10月27日
  • Android 实现锚点定位

    Android 实现锚点定位

  • ffmpeg 入门_python入门笔记

    ffmpeg 入门_python入门笔记写在前面最近在读《FFmpeg从入门到精通》这本书,结合着雷神的博客,学习音视频的知识~在学习的过程中,也记录了一些摘要。因为是边看边记的,所以一些要点在看到后面的时候,需要反过来整理前面的。我用有道云笔记写的markdown没法加图片,所以就先把这部分发了出来。后续会针对内容和排版一步步的优化,如果你被这凌乱的内容辣到了眼睛,请谅解哈哈哈~2019.06.18第一章+第二章知识点(未…

  • 秒秒钟解决打开ps图片显示无法完成请求,因为程序错误「建议收藏」

    秒秒钟解决打开ps图片显示无法完成请求,因为程序错误「建议收藏」问题描述今天在做ps作业的时候做到一半,保存的时候卡了一下,我等了一会,不卡了,我以为我保存了就没什么事了,然后就关闭ps,软件关闭的时候也卡了一下,结果现在想接着做的时候打不开了,做了那么久那么多图层都在,我心态直接崩了,白做了。当我赶紧上网查怎么修复和解决。全特码是p话,一个有用的都没有,说什么右键ps属性,兼容性的运行,管理员打开,设置好后就可以直接打开了,我特么又不是兼容性的问题,之前一直用的好好的,还有打开ps清理暂存盘,缓存大小改大,我。。。。。。呵呵。还有说检查ps是否更新了,说什么确保系.

  • 罗技键盘怎么连台式电脑_罗技键盘蓝牙搜不到

    罗技键盘怎么连台式电脑_罗技键盘蓝牙搜不到罗技蓝牙键盘连接电脑需装入电池,打开电源开关,转动拨盘至【1】位置,然后长按【PC】键3秒进入【搜索】模式。打开电脑,前往【设置】-【设备】-【蓝牙和其他设备】,打开【蓝牙】,在蓝牙搜索列表中选中罗技蓝牙键盘的名称,确认配对即可完成连接。本文以惠普光影精灵6MAX,MacbookPro(分别连接K835有线键盘和K480蓝牙键盘);Windows10,macOSCatalina10.15.7…

    2022年10月16日
  • 电脑蓝屏错误代码0x000000ED_电脑蓝屏0*000000ed怎么解决

    电脑蓝屏错误代码0x000000ED_电脑蓝屏0*000000ed怎么解决电脑蓝屏的原因很多,不同的电脑蓝屏显示的代码不同,对应的解决方法也不同。最近就有网友说自己的电脑蓝屏代码0x000000ed怎么办,不知道0x000000ed是什么意思。今天小编就教下大家修复电脑蓝屏代码0x000000ed的解决方法。0x000000ed蓝屏原因:说明I/0子系统试图加载到引导卷时失败。一般因为不正常断电导致的硬盘故障,从而导致启动时不能正常加载。具体的解决方法如下:1、先开机按f8看能否进入安全模式,能够进入的话,打开运行/输入CMD,键入命令chkdsk/f/r回…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号