data-structures - 2阶B树是满二叉树吗？

Question

当我搜索上述问题时，我得到了答案是。

满二叉树的定义如下:

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 树是满二叉树呢？

Answer 1

对于 B 树来说，“顺序”这个术语的定义非常糟糕，几乎没有什么用处……每个人都以不同的方式使用这个术语。

尽管如此，对于任何类型的 B 树，节点中指针的数量由该节点中键的数量决定。如果键的数量为 k，则指针的数量为 k + 1。与其他类型的树一样，指针的数量无法选择。节点中的所有指针要么为零(单级“树”中的根，叶子)，要么全部有效，没有中间状态，没有混合。

其次，为了使 B 树发挥作用，需要选择键的数量。这意味着最小可能的 B 树节点是具有一个或两个键(因此具有两个或三个指针)的节点。这基本上是一棵 (2,3) 树，据报道这正是 B 树的发明方式 - 作为 (2,3) 树的推广。

将键 10、17 和 45 插入到尽可能最低顺序的空 B 树中将如下所示:

[]

[10]

[10 17]

   [17]
[10]  [45]

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

但是，由于上述原因，从您似乎使用该术语(每个节点最多有两个指针)的意义上来说，不存在 2 阶 B 树这样的东西。当向这种退化 B 树中插入多个键时，不可能维持 B 树不变量。

注意:有无数的 B 树变体，它们允许暂时甚至永久地违反经典 B 树的结构不变量，主要是为了实现性能目标、简化维护或实现无锁等特殊属性并发操作。出于本次讨论的目的，这些不会被算作正确的 B 树，即使它们的名称中可能包含“B 树”。