2 阶 B 树是满二叉树吗？
Is a B-Tree of order 2 a full binary tree?
当我搜索上述问题时，我得到了答案 Yes。
满二叉树的定义如下：
A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.
但问题是，每次构造2阶B-Tree时，这个属性可能都不满足
例如：
Insert 10,17,45 in a B-Tree of order 2
我们得到的结构是
10
17
45
这不是一个完整的二叉树。
那么为什么说2阶B树是满二叉树呢？
术语 'order' 对 B 树的定义如此糟糕，以至于几乎没有用......每个人都以不同的方式使用该术语。
尽管如此，对于任何一种 B 树，节点中指针的数量都由该节点中键的数量决定。如果键的数量是 k 那么指针的数量是 k + 1，句点。关于指针的数量没有选择，因为在其他种类的树中可能有。一个节点中的所有指针都为零（单级 'tree' 中的根，叶子）或所有指针都有效，没有中间，没有混合。
其次，为了使 B 树发挥作用，需要选择键的数量。这意味着最小可能的 B 树节点是具有一个或两个键（因此具有两个或三个指针）的节点。这基本上是一个 (2,3)-tree，据报道这正是 B-trees 的发明方式 - 作为 (2,3)-trees 的概括。
将键 10、17 和 45 插入尽可能低阶的空 B 树将如下所示：
[]
[10]
[10 17]
[17]
[10] [45]
最后的结果确实很像一棵平衡二叉树。
但是，由于上述原因，在您似乎使用术语（每个节点最多两个指针）的意义上，不存在诸如 2 阶 B 树之类的东西。当向这样的退化 B 树中插入多个键时，将无法维护 B 树不变量。
注意：有无数的 B 树变体允许暂时甚至永久地违反经典 B 树的结构不变量，主要是为了实现性能目标、简化维护或实现特殊属性，如锁- 较少的并发操作。出于本次讨论的目的，这些不会被算作适当的 B 树，即使它们的名称中可能有 "B-tree"。
根据Fundamentals of Data Structure in C++ by Horowitz，提到2阶B树确实一定是满树。但是，并不是任何2阶的树（任意数量的节点）（with 1 or 2 children）都可以是B树，只有那些有2^k个节点的树才能形成2阶的B树。另一方面，它也提到对于order > 2的B树，任意数量的节点都可以组成order > 2的B树。也就是说，2 阶 B 树是 B 树的一种特例。
为了回答这个问题，我们先看一下Order m的B-Tree的定义：
- 根有两个children;
- 每个节点不小于ceil(m / 2) children;
- 叶子节点应该放在同一层。
- （隐含的东西）B-Tree 也是一个 m-way 搜索树
请注意，由于 B-Tree 也是一个 m-way 搜索树，因此具有 p 个内部节点的每个节点应不少于 p + 1 children。因此，由于2阶的B-tree要求每个节点不少于2个children且每个节点不超过2个children，m阶的B-Tree是一个完整的 BST。
当我搜索上述问题时，我得到了答案 Yes。
满二叉树的定义如下：
A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.
但问题是，每次构造2阶B-Tree时，这个属性可能都不满足
例如：
Insert 10,17,45 in a B-Tree of order 2
我们得到的结构是
10
17
45
这不是一个完整的二叉树。
那么为什么说2阶B树是满二叉树呢？
术语 'order' 对 B 树的定义如此糟糕，以至于几乎没有用......每个人都以不同的方式使用该术语。
尽管如此，对于任何一种 B 树，节点中指针的数量都由该节点中键的数量决定。如果键的数量是 k 那么指针的数量是 k + 1，句点。关于指针的数量没有选择，因为在其他种类的树中可能有。一个节点中的所有指针都为零（单级 'tree' 中的根，叶子）或所有指针都有效，没有中间，没有混合。
其次，为了使 B 树发挥作用，需要选择键的数量。这意味着最小可能的 B 树节点是具有一个或两个键（因此具有两个或三个指针）的节点。这基本上是一个 (2,3)-tree，据报道这正是 B-trees 的发明方式 - 作为 (2,3)-trees 的概括。
将键 10、17 和 45 插入尽可能低阶的空 B 树将如下所示：
[]
[10]
[10 17]
[17]
[10] [45]
最后的结果确实很像一棵平衡二叉树。
但是，由于上述原因，在您似乎使用术语（每个节点最多两个指针）的意义上，不存在诸如 2 阶 B 树之类的东西。当向这样的退化 B 树中插入多个键时，将无法维护 B 树不变量。
注意：有无数的 B 树变体允许暂时甚至永久地违反经典 B 树的结构不变量，主要是为了实现性能目标、简化维护或实现特殊属性，如锁- 较少的并发操作。出于本次讨论的目的，这些不会被算作适当的 B 树，即使它们的名称中可能有 "B-tree"。
根据Fundamentals of Data Structure in C++ by Horowitz，提到2阶B树确实一定是满树。但是，并不是任何2阶的树（任意数量的节点）（with 1 or 2 children）都可以是B树，只有那些有2^k个节点的树才能形成2阶的B树。另一方面，它也提到对于order > 2的B树，任意数量的节点都可以组成order > 2的B树。也就是说，2 阶 B 树是 B 树的一种特例。
为了回答这个问题，我们先看一下Order m的B-Tree的定义：
- 根有两个children;
- 每个节点不小于ceil(m / 2) children;
- 叶子节点应该放在同一层。
- （隐含的东西）B-Tree 也是一个 m-way 搜索树
请注意，由于 B-Tree 也是一个 m-way 搜索树，因此具有 p 个内部节点的每个节点应不少于 p + 1 children。因此，由于2阶的B-tree要求每个节点不少于2个children且每个节点不超过2个children，m阶的B-Tree是一个完整的 BST。