data-structures - B树可以采用二叉树的形式吗

Question

在数据库系统的 CS 考试中，有人问了一个问题，使用 B-tree 进行索引，在给定系统中查找记录的最大块访问数是多少。B树的顺序是4，最大条目数是当所有内部节点都半满时（因为如果它们小于半满，它们将与邻居合并）。因此，当每个节点有 2 个子树指针（并且最大访问次数等于树的深度）时，树处于其最高深度。但这将有效地为树提供与二叉树相同的结构，因为每个节点只保存一个数据和两个指针。

所以问题是这样的：

使用插入和删除策略，物理上是否可以按顺序插入和删除节点以允许树采用这种形式，或者它是否总是合并并减少树的深度？

标签： data-structuresbinary-treeb-tree

Answer 1

当然这是可能的。

仅通过插入来实现这样的二叉树是不可能的，但是一旦您在 4 度 b-tree 中插入了一堆键（数据元素），您就可以从叶子中删除键，以便以二叉树形状为目标.

您将为二叉树设定特定的树高度，因此首先进行足够的插入以获得具有该高度的 B 树。然后消除键，以减少非二元节点的程度，从树的顶层开始，一路向下。

一个例子

假设您要创建高度为 3 的树。为此，我们将值 1 到 13 插入到空树中。这将导致这棵树：

                    [9] 
     [3,     6]               [12] 
[1, 2] [4, 5] [7, 8]   [10, 11]  [13] 

现在，为了在我们目前拥有 [3, 6] 的地方只获得一个密钥，我们需要摆脱它的一个孩子。所以让我们删除 7 和 8：

删除 8 后，标准算法会将值 5 从 [4, 5] “旋转”到其父级，并将父键 (6) 注入我们删除 8 的子级：

               [9] 
     [3,  5]             [12] 
[1, 2] [4]  [6]   [10, 11]  [13] 

我们同一个节点的孩子还是太多了，所以我们继续删除6个。现在有一个叶子的合并，这会减少我们最初想要减少的节点：

             [9] 
     [3]               [12] 
[1, 2] [4, 5]   [10, 11]  [13] 

现在所有非二进制节点都在底层。我们现在可以删除键 2、5 和 11 来获得二叉树：

       [9] 
  [3]        [12] 
[1] [4]   [10]  [13] 

一般来说

同样的原理也适用于高度较高的树木。只需开始从非二进制的内部节点的子树中删除键，直到它们是。在某些时候会发生合并，这将降低非二进制节点的程度，最终使它们成为二进制。

如果你从上到下这样做，你将逐层二进制，最后底层也将二进制。