问2阶B树是一个完整的二叉树吗？

EN

“顺序”这个词对B树的定义太差了，几乎毫无用处.每个人都以不同的方式使用这个词。

无论如何，对于任何类型的B树，节点中的指针数都由该节点中的键数决定。如果键数为k，则指针数为k+ 1，句号。对于指针的数量没有选择，就像在其他类型的树中一样。节点中的所有指针都是零(根位于单层的“树”中，叶子)，或者都是有效的，没有中间的，没有混合的。

其次，B树要想发挥作用，就需要在键的数量上做出选择。这意味着最小的B树节点是一个有一个或两个键(因此有两个或三个指针)的节点。这基本上是一个(2,3)-tree，据报道B树正是这样发明的--作为(2,3)-trees的一个推广。

将键10、17和45插入最低顺序的空B树，如下所示：

[]

[10]

[10 17]

   [17]
[10]  [45]

最后的结果确实看起来像一棵平衡的二叉树。

但是，由于上述原因，没有B树的第2顺序，因为您似乎在使用该术语(最多每个节点两个指针)。在这样一个退化的B树中插入多个密钥时，不可能维护B树不变量。

注意:有大量的B树变体允许暂时甚至永久地违反经典B树的结构不变量，主要是为了达到性能目标、简化维护或实现诸如无锁并发操作之类的特殊属性。尽管它们的名字中可能有“B-树”，但为了这次讨论的目的，这些树将不算适当的B-树。

根据Fundamentals of Data Structure in C++ by Horowitz，它提到2阶B树确实必须是一棵完整的树。但是，没有任何2阶树(有1或2个子节点)可以是B树，只有具有2^k节点的树才能形成2阶B树，另一方面，它也提到了对于order > 2 B树，任何节点都可以形成order > 2的B树。也就是说，2阶B树是B树的一种特例。

为了回答这个问题，让我们看一看B树的定义：

1. 根有两个孩子；
2. 每个节点应有不少于ceil(m / 2)的子代；
3. 叶节应放在同一水平上。
4. B树也是m-way搜索树

注意，由于B树也是m路搜索树，每个具有p内部节点的节点都应该有不少于p+1的子节点。因此，由于2阶B树要求每个节点不少于2个子节点，而每个节点不超过2个子节点，B阶树m是一个完整的BST树。