【你问我答】b+树跟b树的区别是什么?

问题描述:

b+树跟b树的区别是什么?

回答有奖:

选取一位认真回答问题的牛友,赠送200牛币!
▶回答尽量有自己的思考,不要单纯的只是复制粘贴定理定义,或者他人blog哦~

你问我答问题汇总:点击进入
关注你问我答栏目:点击关注

你问我答 - 答问题,成大佬,拿牛币!
你问我答是牛客新栏目,每周1期几个面试中真实遇到的问题,
牛友在问题贴下留下自己的知识,经验与见解,
帮助更多牛友了解更多技术相关知识!
#悬赏##Java##面试题目#
全部评论
就像我们小时候查过的新华字典,b+树是从目录查,b树是直接根据字典侧面字母的阴影翻。
4 回复 分享
发布于 2020-06-23 19:15
少个+号,经过我认真的思考
4 回复 分享
发布于 2020-06-23 11:36
结构上     B树中关键字集合分布在整棵树中,叶节点中不包含任何关键字信息,而B+树关键字集合分布在叶子结点中,非叶节点只是叶子结点中关键字的索引;     B树中任何一个关键字只出现在一个结点中,而B+树中的关键字必须出现在叶节点中,也可能在非叶结点中重复出现; 性能上(也即为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引?)     B+树的磁盘读写代价更低,因为B+树的所有非叶子节点只会存放索引信息,而真正的数据信息都只存放在叶子节点中,这样一来,每个非叶子节点存放的索引信息就更多,一次磁盘IO就可以读取更多的索引信息到内存中,可以减少磁盘IO的次数。     B+树的查询效率更加稳定,由于非叶子节点只存索引信息,而没有真正的数据信息,所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。     B+树更加适合在区间查询的情况,由于B+树的数据都存储在叶子结点中,非叶子结点均为索引,只需要扫一遍叶子结点即可得到所有数据信息,但是B树因为其非叶子结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引。
1 回复 分享
发布于 2020-06-23 14:01
1. B+树的中间节点不保存数据,是纯索引,但是B树的中间节点是保存数据和索引的,相对来说,B+树磁盘页能容纳更多节点元素,更“矮胖”; 2. B+树查询必须查找到叶子节点,B树只要匹配到即可而不用管元素位置,因此B+树查找更稳定(并不慢); 3. 对于范围查找来说,B+树只需遍历叶子节点链表即可,B树却需要重复地中序遍历,在项目中范围查找又是很常见的;
5 回复 分享
发布于 2020-06-23 11:44
1、B+树的层级更少:相较于B树B+每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;(单一节点存储更多的元素,使得查询的IO次数更少。) 2、B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;[O(logn)] 3、B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。 4、B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。 B树相对于B+树的优点是,如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比B+树快。
点赞 回复 分享
发布于 2020-06-23 12:41
B+树是B-树的变体,也是一种多路搜索平衡树,区别是B+树只有达到叶子结点才命中(B-树可以在 非叶子结点命中),B-树关键字集合分布在整颗树中(即包含内部节点),B+树所有关键字都在叶子结点出现
点赞 回复 分享
发布于 2020-06-23 11:37

相关推荐

我承认之前说话大声了点,没开摄像头也不算KPI,虽然二面还是没开摄像头,但至少约面了嘛开始就简单自我介绍,针对项目进行阐述,对答还算流畅,但是有的实际高并发场景细节并没有答上。八股部分就问了常见的redis八股,比如击穿、穿透、雪崩以及应对策略,最后雪崩的应对策略没答全,但也差不多了。算法题有点难第一个是,循环输出启动3个线程,分别循环打印1、2、3,并且要求输出顺序严格为"12312312.3."。让三个线程交替输出自己的内容,我准备的不大充分,之前遇到过,但看答案有接近一百行,写不出来。第二个是,对于一个含有n个元素的数组,可以划分为m个小数组使他们和相同,比如数组为{1,3,4,2,2}时,n=5,可以划分为m=1,{1,2,3,4,2}; 当m=2时 {1,2,3}和{2,4}各自和为6;当 m=3时{1,3}、{2,2}、{4}各自和为4;当m=4时不可划分,所以m最大为3。请你设计一个算法,对于任意输入的数组,求m最大值。类似leetcode40题组合2,但比那个复杂的多,因为target要自己一个个去尝试,并且元素不能重复使用,我事后花了一个晚上才写出来,幸好面试时没有死磕。第三题是,统计一个字符串中出现最多的字符,我直接用128位的int数组计数,面试官问我冗余空间,我说使用map会引入更多内存,且效率没数组高。最后还有一个开放性智力题,问我如何估算一个地区的奶茶店总数目。我本来想着直接美团上看附近的店家数据,但是这只能限定距离范围,无法覆盖全市。所以想着通过各个商家自己的微信小程序,计算前10个品牌(比如蜜雪、霸王、茶百道、瑞幸……)在该地区的总数目n,再在某个商圈进行抽样,找到这10家品牌占总共奶茶店的数目(比如占比70%),那么全地区的数目可以用n/70%来粗略估算。
点赞 评论 收藏
分享
评论
点赞
22
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务