如何创建B+树数据结构

Question

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

遵循这些步骤

1. 如果桶未满(插入后最多为b-1项)，则添加记录。
2. 否则，把水桶分开。
3. 分配新的叶子并将桶的一半元素移动到新的桶中。
4. 插入新叶的最小键并将地址插入父级。

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

使用20,15,5,1,3,9,2,12作为输入，我获得以下树：

                                   |1|5| |

                          |2|5| |          |9| | |


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

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

Answer 1

你的树不对。节点(而不是叶)中的每个值都应该是分支的断点.为了说明这一点，让我们考虑以下节点：

----------------------------------------
|            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，则必须拆分。
  • 当桶被拆分时，两个值留在原来的桶中，两个值移到一个新的桶中。
  • 新桶的第一个值(值较大的那个)插入到父桶/节点中。
  • 如果父节点已满(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，20)中删除14：

                           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