内容

• 比较表
• B树的定义
• M阶B树的性质
• 二叉树的定义
• 遍历技术
• 结论

B树和二叉树是非线性数据结构的类型。尽管这些术语看起来很相似，但是在所有方面都不同。当记录或数据存储在RAM中而不是磁盘中时，将使用二叉树，因为RAM的访问速度远高于磁盘。另一方面，当数据存储在磁盘中时使用B树，它通过减小树的高度并增加节点中的分支来减少访问时间。

B树和二叉树之间的另一个区别是B树的所有子节点必须处于同一级别，而二叉树没有这种约束。一棵二叉树最多可以有2个子树或节点，而在B树中最多可以有M个子树或节点，其中M是B树的顺序。

1. 比较表
2. 定义
3. 关键差异
4. 结论

比较表

比较依据	B树	二叉树
基本约束	一个节点最多可以有M个子节点（其中M是树的顺序）。	一个节点最多可以有2个子树。
用过的	当数据存储在磁盘上时使用。	当记录和数据存储在RAM中时使用。
树的高度	日志中号 N（其中m是M路径树的阶数）	日志2 ñ
应用	许多DBMS中的代码索引数据结构。	代码优化，霍夫曼编码等

B树的定义

B树是平衡的M路树，也称为平衡排序树。它类似于二叉搜索树，其中节点是根据有序遍历进行组织的。 B树的空间复杂度为O（n）。插入和删除时间的复杂度为O（log n）。

对于B树，必须满足某些条件：

• 树的高度必须尽可能小。
• 在树的叶子上方，不应有任何空子树。
• 树的叶子必须处于同一水平。
• 除离开节点外，所有节点的子节点数最少。

M阶B树的性质

• 每个节点可以具有最多M个子代数和最小M / 2个子代数，或2到最大之间的任何数字。
• 每个节点的密钥少于具有最大M-1密钥的子密钥。
• 密钥的排列在节点内按某些特定顺序。密钥左侧存在的子树中的所有密钥都是该密钥的前身，而该密钥右侧存在的子树称为后继。
• 在插入完整节点时，树分为两部分，并且将具有中值的键插入到父节点。
• 当删除节点时，将发生合并操作。

二叉树的定义

二叉树是一个树结构，它的子节点最多可以有两个指针。这意味着一个节点可以具有的最高度是2，也可以是零或一度的节点。

二叉树的某些变体，例如严格的二叉树，完整的二叉树，扩展的二叉树等。

• 严格二叉树是其中每个非终端节点必须具有左子树和右子树的树。
• 满足以下条件的树称为完全二叉树： ^一世 每个级别的节点，其中i是级别。
• 线程二进制是一种二进制树，它由0个节点或2个节点组成。

遍历技术

树遍历是对树数据结构执行的最频繁的操作之一，在树数据结构中，每个节点都以系统的方式精确地访问了一次。

• 有序-在此树遍历中，递归访问左子树，然后访问根节点，最后访问右子树。
• Preorer-在此树遍历中，首先访问根节点，然后访问左子树，最后访问右子树。
• 后置顺序-此技术先访问左子树，然后访问右子树，再访问最后一个根节点。

1. 在B树中，非终端节点可以具有的最大子节点数为M，其中M是B树的顺序。另一方面，二叉树最多可以具有两个子树或子节点。
2. 当数据存储在磁盘中时使用B树，而当数据存储在RAM等快速存储器中时使用二叉树。
3. B树的另一个应用领域是DBMS中的代码索引数据结构，相比之下，二叉树则用于代码优化，霍夫曼编码等。
4. B树的最大高度为log_中号N（M是树的顺序）。相反，二叉树的最大高度为log₂N（N是节点数，基数是2，因为它是二进制数）。

结论

B树用于二进制和二进制搜索树，其背后的主要原因是内存层次结构，其中CPU通过高带宽通道连接到高速缓存，而CPU通过低带宽通道连接到磁盘。当记录存储在RAM中时（小而快）使用二叉树，当记录存储在磁盘中时（大而慢）使用B树。因此，由于分支因子高且树的高度降低，因此使用B树代替二叉树会大大减少访问时间。