站长之家- 问答 2020-09-09T16:10:20 +08:00

B+树是什么意思 B+树怎么理解

B+树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树,很多朋友还不理解什么是B+树,下面就来为大家分享一下B+树到底怎么理解。

1、B+树是一种树数据结构,通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入,这与二叉树恰好相反。

2、B+树在节点访问时间远远超过节点内部访问时间的时候,比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度,平衡操作不经常发生,而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。

3、B+背后的想法是内部节点可以有在预定范围内的可变量目的子节点。因此,B+ 树不需要像其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如,在 2-3 B 树(常简称为2-3树)中,每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。

4、B+树的创造者 Rudolf Bayer 没有解释B代表什么。最常见的观点是B代表平衡(balanced),因为所有的叶子节点在树中都在相同的级别上。B也可能代表Bayer,或者是波音(Boeing),因为他曾经工作于波音科学研究实验室。

5、在B+树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的阶数是m,则除了根之外的每个节点都包含最少[m/2]个元素最多[m-1]个元素,对于任意的结点有最多 m 个子指针。对于所有内部节点,子指针的数目总是比元素的数目多一个。所有叶子都在相同的高度上,叶结点本身按关键字大小从小到大链接。

推荐关键词

24小时热搜

查看更多内容

大家正在看

b树和b+树有什么不同 b树和b+树特点区别汇总

b树和b+树的区别是什么?b+树数据结构详细介绍

保准牛完成B+轮融资 招商局投资

诺基亚风光不再 B+评级沦为垃圾股行列

瑞幸咖啡完成1.5亿美元B+轮融资

汽车电商日报:百度一汽合作 康众获B+轮

资本寒冬跑出在线教育黑马 哒哒英语获B+轮融资

随手科技再获源码资本数千万美元B+轮投资