B Tree 和 B+Tree

作者 : 开心源码 本文共729个字,预计阅读时间需要2分钟 发布时间: 2022-05-14 共161人阅读

数据结构学习地址:
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

什么是B树?

B树,全名是平衡多路查找树,是对二叉查找树的改进,它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数,B树大量应用在数据库和文件系统当中。

为什么出现B树?而不是红黑树?

1、红黑树是二叉树,二B树是多叉的
2、根据计算机的局部性原理,B树将很多相近甚至连续的值存放在一个节点上,这样在获取数据时,B树可以一次获取更多的相关信息,二红黑树一次只能获取一个数据信息。
3、B树由于是多路的,相同数据量,就证实其高度要显著低于红黑树,在效率上也显著高于红黑树。

B Tree的结构

对于一棵m阶B tree:
1、每个结点至多可以拥有m个子结点。
2、根结点至少有2个子结点,除非根结点为叶子节点,根结点中关键字的个数为1~m-1。
3、非根结点至少有[m/2]([],向上取整)个子结点,相应的,关键字个数为[m/2]-1~m-1

B树节点信息

1、本结点所含关键字的个数;
2、指向父结点的指针;
3、关键字;
4、指向子结点的指针;

B树

什么是B+树?

B+树是B树的一个更新版,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳固,其速度完全接近于二分法查找。

B+树与B树的不同

1、在B+树种,非叶子节点值存数据的key和子节点指针信息,不存储数据的具体值data的指针,这使得B+树可以存储更多的key。B+树的所有数据data存储在叶子节点上。
2、在叶子节点上,每个叶子结点添加顺序指针,形成链表结构,便于区间查找和遍历,非叶子结点作为索引。(非叶子节点也有横向指针的叫做B*树)

B树B+树

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » B Tree 和 B+Tree

发表回复