文档章节

B树和B+树的总结

浮躁的码农
 浮躁的码农
发布于 06/20 12:58
字数 1829
阅读 4
收藏 0
点赞 0
评论 0

B树

为什么要B树

磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

简介

这里的B树,也就是英文中的B-Tree,一个 m 阶的B树满足以下条件:

  1. 每个结点至多拥有m棵子树;
  2. 根结点至少拥有两颗子树(存在子树的情况下);
  3. 除了根结点以外,其余每个分支结点至少拥有 m/2 棵子树;
  4. 所有的叶结点都在同一层上;
  5. 有 k 棵子树的分支结点则存在 k-1 个关键码,关键码按照递增次序进行排列;
  6. 关键字数量需要满足ceil(m/2)-1 <= n <= m-1;

举个栗子:

B树上大部分的操作所需要的磁盘存取次数和B树的高度是成正比的,在B树中可以检查多个子结点,由于在一棵树中检查任意一个结点都需要一次磁盘访问,所以B树避免了大量的磁盘访问。

操作

 

既然是树,那么必不可少的操作就是插入和删除,这也是B树和其它数据结构不同的地方,当然了,还有必不可少的搜索,分享一个对B树的操作进行可视化的网址,它是由usfca提供的。

假定对高度为h的m阶B树进行操作。

插入

新结点一般插在第h层,通过搜索找到对应的结点进行插入,那么根据即将插入的结点的数量又分为下面几种情况。

  • 如果该结点的关键字个数没有到达m-1个,那么直接插入即可;
  • 如果该结点的关键字个数已经到达了m-1个,那么根据B树的性质显然无法满足,需要将其进行分裂。分裂的规则是该结点分成两半,将中间的关键字进行提升,加入到父亲结点中,但是这又可能存在父亲结点也满员的情况,则不得不向上进行回溯,甚至是要对根结点进行分裂,那么整棵树都加了一层。

其过程如下:

删除

同样的,我们需要先通过搜索找到相应的值,存在则进行删除,需要考虑删除以后的情况,

  • 如果该结点拥有关键字数量仍然满足B树性质,则不做任何处理;
  • 如果该结点在删除关键字以后不满足B树的性质(关键字没有到达ceil(m/2)-1的数量),则需要向兄弟结点借关键字,这有分为兄弟结点的关键字数量是否足够的情况。
    • 如果兄弟结点的关键字足够借给该结点,则过程为将父亲结点的关键字下移,兄弟结点的关键字上移;
    • 如果兄弟结点的关键字在借出去以后也无法满足情况,即之前兄弟结点的关键字的数量为ceil(m/2)-1,借的一方的关键字数量为ceil(m/2)-2的情况,那么我们可以将该结点合并到兄弟结点中,合并之后的子结点数量少了一个,则需要将父亲结点的关键字下放,如果父亲结点不满足性质,则向上回溯;
  • 其余情况参照BST中的删除。

其过程如下:

B+树

 

为什么要B+树

由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引,而B树则常用于文件索引。

简介

同样的,以一个m阶树为例:

  1. 根结点只有一个,分支数量范围为[2,m];
  2. 分支结点,每个结点包含分支数范围为[ceil(m/2), m];
  3. 分支结点的关键字数量等于其子分支的数量减一,关键字的数量范围为[ceil(m/2)-1, m-1],关键字顺序递增;
  4. 所有叶子结点都在同一层;

操作

其操作和B树的操作是类似的,不过需要注意的是,在增加值的时候,如果存在满员的情况,将选择结点中的值作为新的索引,还有在删除值的时候,索引中的关键字并不会删除,也不会存在父亲结点的关键字下沉的情况,因为那只是索引。

B树和B+树的区别

这都是由于B+树和B具有这不同的存储结构所造成的区别,以一个m阶树为例。

  1. 关键字的数量不同;B+树中分支结点有m个关键字,其叶子结点也有m个,其关键字只是起到了一个索引的作用,但是B树虽然也有m个子结点,但是其只拥有m-1个关键字。
  2. 存储的位置不同;B+树中的数据都存储在叶子结点上,也就是其所有叶子结点的数据组合起来就是完整的数据,但是B树的数据存储在每一个结点中,并不仅仅存储在叶子结点上。
  3. 分支结点的构造不同;B+树的分支结点仅仅存储着关键字信息和儿子的指针(这里的指针指的是磁盘块的偏移量),也就是说内部结点仅仅包含着索引信息。
  4. 查询不同;B树在找到具体的数值以后,则结束,而B+树则需要通过索引找到叶子结点中的数据才结束,也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

本文转载自:https://www.cnblogs.com/George1994/p/7008732.html

共有 人打赏支持
浮躁的码农

浮躁的码农

粉丝 58
博文 717
码字总数 142223
作品 0
松江
程序员
B树、B-树、B+树、B*树 总结

学习Kafka时遇到B树,突然想起B树、B-树、B+树、B*树,概念有点模糊了,查找到一篇好的资料,学习一下 B树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存...

u012050154
2017/07/28
0
0
什么是B+Tree

B+Tree的定义 B+Tree是B树的变种,有着比B树更高的查询性能,来看下m阶B+Tree特征: 1、有m个子树的节点包含有m个元素(B-Tree中是m-1) 2、根节点和分支节点中不保存数据,只用于索引,所有...

xsster
2017/07/28
0
0
B树、B+树、B-树

1、多路查找树(mutil-way search tree)定义 多路查找树,其每一个节点的孩子数可以多于两个,且每一个节点处可以存储多个元素。 由于它是查找树,所以元素之间存在某种特定的排序关系。由于...

笨拙的小Q
2016/06/29
88
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
05/08
0
0
B树 B-树 B+树 B*树

B树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树; 如: ...

青夜之衫
2017/12/05
0
0
从B 树、B+ 树、B* 树谈到R 树

作者:July、weedge、Frankie。编程艺术室出品。 说明:本文从B树开始谈起,然后论述B+树、B树,最后谈到R 树。其中B树、B+树及B树部分由weedge完成,R 树部分由Frankie完成,全文最终由Jul...

布几岛
2014/06/27
0
0
B树,B+树,B*树学习笔记

B B+ 这两种处理索引的数据结构的不同之处: 1. B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中.而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有...

liujiest
2016/04/30
214
0
从B 树、B+ 树、B* 树谈到R 树

从B 树、B+ 树、B* 树谈到R 树 作者:July、weedge、Frankie。编程艺术室出品。 说明:本文从B树开始谈起,然后论述B+树、B树,最后谈到R 树。其中B树、B+树及B树部分由weedge完成,R 树部分...

vincent_y
2013/11/27
0
0
浅谈MySQL的B树索引与索引优化

MySQL的MyISAM、InnoDB引擎默认均使用B+树索引(查询时都显示为“BTREE”),本文讨论两个问题: 为什么MySQL等主流数据库选择B+树的索引结构? 如何基于索引结构,理解常见的MySQL索引优化思...

猴子007
03/26
0
0
zTree两棵树拖动中的删除图标显示问题

@zTree 你好,想跟你请教个问题: 描述:我有两棵zTree,分别是A和B,A设置showRemoveBtn为false,即鼠标移到A树上时不显示删除图标,B设置showRemoveBtn为true,即鼠标移动到B树上时显示删除...

JiYujie
2013/05/07
1K
8

没有更多内容

加载失败,请刷新页面

加载更多

下一页

SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
2
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
1
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
161
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0
python里求解物理学上的双弹簧质能系统

物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定。假定没有外力时,两个弹簧的长度为L1和L2。 由于两物体有重力,那么...

wangxuwei
昨天
0
0
apolloxlua 介绍

##项目介绍 apolloxlua 目前支持javascript到lua的翻译。可以在openresty和luajit里使用。这个工具分为两种模式, 一种是web模式,可以通过网页使用。另外一种是tool模式, 通常作为大规模翻...

钟元OSS
昨天
2
0
Mybatis入门

简介: 定义:Mybatis是一个支持普通SQL查询、存储过程和高级映射的持久层框架。 途径:MyBatis通过XML文件或者注解的形式配置映射,实现数据库查询。 特性:动态SQL语句。 文件结构:Mybat...

霍淇滨
昨天
2
0
开发技术瓶颈期,如何突破

前言 读书、学习的那些事情,以前我也陆续叨叨了不少,但总觉得 “学习方法” 就是一个永远在路上的话题。个人的能力、经验积累与习惯方法不尽相同,而且一篇文章甚至一本书都很难将学习方法...

_小迷糊
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部