如何创建B+树数据结构

Question

如何创建B+树数据结构

javaalgorithmdata-structurestreeapplet

3

我想了解如何创建一个分支因子为3，节点最大条目数为3的B+树。我搜索了很多小程序，但大部分都不能正常工作，而那个很好的似乎没有遵循维基百科上找到的步骤。

按照以下步骤：

如果桶未满（插入后最多b-1个条目），则添加记录。
否则，拆分桶。
分配新的叶子，并将桶的一半元素移动到新的桶中。
将新叶子的最小键和地址插入到父节点中。

我认为新值的插入应该在第四步之前进行。是否有更好描述这个算法的版本？

对于输入20,15,5,1,3,9,2,12，我得到了以下树：

                                   |1|5| |

                          |2|5| |          |9| | |


                 |1|2| |    |3|5| |     |9| | |      |15|20| |

这些步骤正确吗？有没有人能指出一个小程序来验证这个例子？

- Tanatos Daniel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DrV · Accepted Answer

您的树不正确。每个节点（非叶节点）中的值都应是分支的断点。为了说明这一点，让我们考虑以下节点：

----------------------------------------
|            7      |     23           |
----------------------------------------
| pointer to | pointer to | pointer to |
| branch with| branch with| branch with|
| values     | values     | values     |
|  < 7       | 7 <= x < 23|  >= 23     |
----------------------------------------

这个节点有两个值和三个分支。值7和23代表第二个和第三个分支中最小的值。第一个分支中最小的值在此级别上没有被表示。（除非它是整棵树中最小的值，否则它将在某个更高的级别上。）

当b=4时，插入值的规则可以总结如下：

找到值所属的桶（第一个值比要插入的值小，下一个桶的第一个值比要插入的值大）
如果插入后桶中的项目数为4，则必须拆分桶
- 当桶被拆分时，原始桶中留下2个值，2个值移动到新桶中
- 新桶的第一个值（具有较大值的那个）被插入到父桶/节点中
- 如果父节点变满（4个值），则以相同的方式进行拆分，但从桶中删除插入其父项的值

让我们考虑一个包含1..9数字的树：

        3,5,7
  |----------------|
1,2   3,4   5,6  7,8,9

如果我们现在将数字10插入树中，最右边的叶子节点变得太满了（7、8、9、10），因此它必须被分成两个叶子节点（1、8）和（9、10）。根据规则，数字9（上半部分桶的最小值）被发送到父节点：

        3,5,7,9
 |---------------------|
1,2   3,4   5,6  7,8  9,10

这将使父元素充满，需要进行分割：

    3,5       7,9
 |-------|   |---|
1,2 3,4 5,6 7,8 9,10

当父节点分裂时，新节点的第一个值会被发送到其父节点。在这个树中，新节点是(7,9)，因此要被移除并发送到父节点的值为7。由于没有这样的父节点，新的根节点被创建：

          7
     |---------|
    3,5        9
 |-------|   |---|
1,2 3,4 5,6 7,8 9,10

让我们构建一棵树，其中包含数字20、15、5、1、3、9、2、12和b=4。

前三个值适合放在一个叶节点中（该节点同时也是根节点）：

5,15,20

在插入数字1时，桶会分裂，新桶的第一个值会被发送到父级（新根）：

   15
 |-----|
1,5  15,20

需要注意的是，永远不会从叶子节点中删除任何内容。删除只发生在分裂的父节点中。

值3可以轻松插入到其存储桶中（存储桶将变为1, 3, 5）。然而，尝试插入数字9会使存储桶超载（1, 3, 5, 9），并且会分裂。新桶的第一个值（5）将被插入到父节点中。

    5,15
 |----------|
1,3  5,9  15,20

值2和12适合它们的桶而不需要分裂，因此树如下：

        5,15
  |--------------| 
1,2,3  5,9,12  15,20

为了看到中间节点分裂时会发生什么，让我们考虑以下树形结构：

                           26
              |-----------------------------|
           8,14,20                        30,34
  |--------------------------|        |-----------|
2,4,6  8,10,12  14,16,18  20,22,24  26,28 30,32 34,36

现在我们将把值13添加到树中。这将触发将桶（8,10,12,13）分成两个的操作：

                           26
             |-----------------------------------|
         8,12,14,20                            30,34
  |-------------------------------|       |-------------|
2,4,6  8,10  12,13  14,16,18  20,22,24  26,28  30,32  34,36

中间左节点（8、12、14、20）的子节点太多了，必须进行分裂：

                           26
         |---------------------------------------|
       8,12               14,20                30,34
  |-------------|       |---------|      |-------------|
2,4,6  8,10  12,13  14,16,18  20,22,24  26,28  30,32  34,36

当我们拆分一个父节点时，我们必须应用添加规则，即新桶的第一项必须插入父节点并从节点中删除，即14从（14,20）中被取走：

                           14,26
           |------------------------------------|
         8,12               20                30,34
  |-------------|       |---------|      |-------------|
2,4,6  8,10  12,13  14,16,18  20,22,24  26,28  30,32  34,36

树还可以用来说明这个规则：每个父节点携带每个子树中的最低值，除了第一个子树。

如果没有太多错误的话，问题中的示例应该如下所示：

         5 
   |----------|
   3          15
 |---|    |-------|
1,2  3  5,9,12  15,20