B树与B+树的对比

B树:

请添加图片描述
m阶B树的核心特性:

  1. 树中每个节点至多有m棵子树,即至多含有m-1个关键字
  2. 根节点的子树数属于[2, m],关键字数属于[1, m-1],其他节点的子树数属于 [ ⌈ m 2 ⌉ , m ] [\lceil \frac{m}{2}\rceil, m] [⌈2m,m],关键字数属于 [ ⌈ m 2 ⌉ − 1 , m − 1 ] [\lceil \frac{m}{2}\rceil-1, m-1] [⌈2m1,m1]
  3. 对任一节点,其所有子树高度都相同
  4. 关键字的值:子树0<关键字1<子树1<关键字2<…(类比二叉查找树 左<根<右)
  5. 所有叶节点都出现在同一层次上,且不带信息(可以视为外部节点或类似于折半查找判定树的查找失败节点,实际上这些节点不存在,指向这些节点的指针为空)

B+树

请添加图片描述
m阶B+树的核心特性:

  1. 通常在B+树上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点。因此可对B+树进行两种查找运算,一种是从最小关键字起顺序查找,另一种是从根节点开始,进行随机查找
  2. 树中每个节点至多有m棵子树;(节点的子树个数与关键字个数相等)
  3. 根节点的子树数属于[2, m],其他节点的子树数属于 [ ⌈ m 2 ⌉ , m ] [\lceil \frac{m}{2}\rceil, m] [⌈2m,m];(节点的子树个数与关键字个数相等)
  4. 所有叶节点包含全部关键字及指向相应记录的指针,叶节点中将关键字按大小顺序排列,并且相邻叶节点按大小顺序相互链接起来(支持顺序查找)
  5. 所有分支节点中仅包含它的各个子节点中关键字的最大值及指向其子节点的指针
  6. B+树中,无论查找成功与否,最终一定都要走到最下面一层节点(对比B树的查找,查找成功情况下,可能停在任何一层)
  7. B+树中,非叶节点不含有该关键字对应记录的存储地址,因此可以使一个磁盘块包含更多个关键字,使得B+树的阶更大,树高更矮,读磁盘次数更少,查找更快。典型应用如关系型数据库的“索引”(如MySQL)

二者对比

-B树B+树
关键字数与子树数节点中的n个关键字对应n+1棵子树节点中的n个关键字对应n棵子树
节点的关键字数范围根节点的关键字数:[1, m-1],其他节点的关键字数[ ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil 2m-1, m-1]根节点的关键字数:[1, m],其他节点的关键字数[ ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil 2m, m]
节点重复性各节点中包含的关键字是不重复的叶节点包含全部关键字,非叶节点中出现过的关键字也会出现在叶节点中
节点的作用B树的节点中都包含了关键字对应的记录的存储地址叶节点包含信息,所有非叶节点仅起索引作用,非叶节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针
来源m阶B树是二叉查找树的进化m阶B+树是分块查找的进化(进化为多级分块查找)
查找方式不支持顺序查找,查找成功时,可能停在任何一层节点,查找速度不稳定支持顺序查找,查找成功或失败都会到达最下一层节点,查找速度稳定

相同点:

  1. 除根节点外,都最少 ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil 2m个分叉(确保节点不要太空)
  2. 任何一个节点的子树都一样高(确保“绝对平衡”)
  3. 二者都是用于文件系统:
    • B树主要用作文件的索引,因此它的查找涉及外存的存取。具体来讲,在B树上进行查找包含两种基本操作:
      • 1)在B树中找节点:由于B树通常存储在磁盘上,因此查找操作1)是在磁盘上进行的
      • 2)在节点中找关键字:这一查找操作是在内存中进行的,即在磁盘上找到指针p所指节点后,先将节点中的信息读入内存,然后再利用顺序查找或折半查找查询等于K的关键字
      • 显然在磁盘上进行一次查找比在内存中进行一次查找耗费时间更多,因此在磁盘上进行查找的次数(即待查关键字所在节点在B树上的层次数)是决定B树查找效率的首要因素
    • B+树是应文件系统所需而出的一种B树的变型树

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

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

相关文章

机器学习:攻击方法FGSM系列

任务 FGSM I-FGSM MI-FGSM Ensemble Attack 攻击评价指标 准确率越低表明攻击越好 数据 预训练模型 BaseLine 实践

Java、PHP、C语言经典项目源码合集推荐(一)

&#xff08;一&#xff09;.Java智慧校园系统源码、 智慧学校源码、 智慧校园平台源码、智慧校园电子班牌系统源码、中小学智慧校园系统源码、 原生微信小程序端源码、电子班牌系统源码 项目技术栈 1、使用springboot框架Javavue2 2、数据库MySQL5.7 3、移动端小程序使用小程…

UWB实时定位系统源码,历史活动轨迹显示,视频联动,电子围栏

UWB实时定位系统源码&#xff0c;工厂企业人员安全定位&#xff0c;UWB源码 行业背景 工业企业多存在很多有毒有害、高危高压等生产环境&#xff0c;带电设备众多&#xff0c;容易发生安全事故&#xff1b;人员只能凭记忆遵守各项生产安全规范&#xff0c;如某些危险区域范围、…

运维 | 浅谈云计算的相关概念和分类

关注&#xff1a;CodingTechWork 云计算 云计算的出现 云计算是采用的按需付费的方式&#xff0c;通过互联网访问云服务器上的服务器、数据库等服务。云计算为何会出现&#xff1f;  如果现在一个企业想要进行软件管理部署&#xff0c;首先需要服务器主机和网络规划&#…

手把手教你如何在Linux下写进度条小程序(附源码)

效果展示 录屏2023 一、建立文件 mkdir ProgressBar //在当前目录下&#xff0c;建立新的目录 cd ProgressBar //进入这个目录 touch main.c makefile progressbar.c progressbar.h //在ProgressBar这个目录建立这几个文件进入ProgressBar这个目录之后&#xff0c;使…

【开源】基于Vue和SpringBoot的食品生产管理系统

项目编号&#xff1a; S 044 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S044&#xff0c;文末获取源码。} 项目编号&#xff1a;S044&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 加工厂管理模块2.2 客户管理模块2.3…

过滤器的应用

javaWeb三剑客: 1. Servlet:接收请求,处理请求(单例,也就是说&#xff0c;多个用户请求的的servlet是同一个对象) 2. Filter:拦截请求(单例->也就是说&#xff0c;多个用户请求的的filter是同一个对象) 3. Listem: 监听用户/服务器行为,javaWeb三剑客: 过滤器的实现 1&…

Arrays.asList() 与 Collections.singletonList()的恩怨情仇

1. 概述 列表是我们使用 Java 时常用的集合类型。 众所周知&#xff0c;我们可以轻松地用一行初始化一个List。例如&#xff0c;当我们想要初始化一个只有一个元素的List时&#xff0c;我们可以使用Arrays.asList()方法或Collections.singletonList()方法。 在本文中&#x…

HCIP-十、BGP基础

十、BGP基础 实验拓扑实验需求及解法1.R1 属于 AS100&#xff0c;R2/3/4 属于 AS200&#xff0c;R5 属于 AS3002.AS200 内运行 OSPF3.建立 IBGP 邻居4.建立 EBGP 邻居5.BGP 发布路由6.路由黑洞 实验拓扑 实验需求及解法 本实验模拟 ISP 网络拓扑&#xff0c;运行 BGP。如图所示…

【DevOps】基于 KubeSphere 的 Kubernetes 生产实践之旅(万字长文)

基于 KubeSphere 的 Kubernetes 生产实践 1.KubeSphere 简介1.1 全栈的 Kubernetes 容器云 PaaS 解决方案1.2 选型理由&#xff08;从运维的角度考虑&#xff09; 2.部署架构图3.节点规划3.1 软件版本3.2 规划说明3.2.1 K8s 集群规划3.2.2 存储集群3.2.3 中间件集群3.2.4 网络规…

kafka,RabbitMQ,RocketMQ,他们之间的区别,架构,如何保证消息的不丢失,保证不重复消费,保证消息的有序性

文章目录 Kafka、RabbitMQ、RocketMQ 之间的区别是什么&#xff1f;性能数据可靠性服务可用性功能 RabbitMQ如何保证消息不丢失&#xff1f;Kafka 的架构说一下&#xff1f;Kafka 怎么保证消息是有序的&#xff1f;Kafka 怎么解决重复消费&#xff1f;Kafka 怎么保证消息不丢失…

TCP/IP协议、三次握手、四次挥手

TCP/IP TCP/IP协议分层TCP头部三次握手TCP四次挥手常见问题1、什么是TCP网络分层2、TCP为什么是三次握手&#xff0c;不是两次或者四次&#xff1f;3、TCP为什么是四次挥手&#xff0c;为什么不能是三次挥手将第二次挥手和第三次挥手合并&#xff1f;4、四次挥手时为什么TIME_W…

spring boot整合Jasypt实现配置加密

文章目录 目录 文章目录 前言 一、Jasypt是什么&#xff1f; 二、使用步骤 1.引入 2.测试使用 3.结果 总结 前言 一、Jasypt是什么&#xff1f; Jasypt&#xff08;Java Simplified Encryption&#xff09;是一个Java库&#xff0c;提供了一种简单的加密解密方式&#xff0c…

web:[ZJCTF 2019]NiZhuanSiWei1

题目 点进题目&#xff0c;网页显示如下&#xff0c;需要代码审计 $_GET["text"]和$_GET["file"]来获取传入的两个参数text和file。使用isset()函数来检查$text变量是否已设置并且不为null。如果设置了并且不为null&#xff0c;则执行下面的逻辑。在下面的…

Qt4用子类化ProxyModel和子类化MainWindow实现全表筛选,中文排序和复制粘贴

目录 1 需求 2 子类化ProxyModel实现全表筛选 3 字符串列表实现中文排序 3.1 Qt5中文排序 3.2 Qt4排序 4 表格的复制粘贴 5 应用 1 需求 模型视图编程是Qt开发的基本功&#xff0c;其中有几个关键问题需要解决&#xff1a; 全表筛选&#xff0c;或者说多列搜索中文排序…

100元预算,轻松涨粉1000!腾讯运营面试秘籍大揭秘!

大家好啊&#xff01;小米在这里&#xff5e; 很高兴又有机会和大家见面啦&#xff01;最近小米参加了一场腾讯的运营面试&#xff0c;遇到了一个超有趣的问题&#xff1a;如果让你运营一个公众号&#xff0c;近期需要增加1000个关注&#xff0c;预算100元&#xff0c;怎么完成…

RocketMq 主题(TOPIC)生产级应用

RocketMq是阿里出品&#xff08;基于MetaQ&#xff09;的开源中间件&#xff0c;已捐赠给Apache基金会并成为Apache的顶级项目。基于java语言实现&#xff0c;十万级数据吞吐量&#xff0c;ms级处理速度&#xff0c;分布式架构&#xff0c;功能强大&#xff0c;扩展性强。 官方…

【C++初阶】STL详解(八)List的模拟实现

本专栏内容为&#xff1a;C学习专栏&#xff0c;分为初阶和进阶两部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握C。 &#x1f493;博主csdn个人主页&#xff1a;小小unicorn ⏩专栏分类&#xff1a;C &#x1f69a;代码仓库&#xff1a;小小unicorn的代码仓库&…

2018年2月16日 Go生态洞察:Go 1.10版本发布分析

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

Autosar MCAL-RH850P1HC-MCAL配置环境搭建

文章目录 前言下载安装包软件安装安装SIP包安装MCAL文件配置工程配置生成代码测试静态代码路径总结前言 对于RH850P1HC,官网有免费的MCAL,但官网的MCAL没有CAN模块(原厂反馈为Bosch IP,CAN Driver他们没有),也没有FEE模块。如果需要,可以找第三方软件公司,如ETAS.虽然M…