java - 如何创建 B+ 树数据结构

Question

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

按照这些步骤

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     |
----------------------------------------

此节点有 2 个值和三个分支。值 7 和 23 表示第二个和第三个分支中的最小值。第一个分支的最小值不在此级别表示。 (除非它是整棵树中的最小值，否则它会在更高的层次上。)

b=4 时，插入值的规则可以总结为:

• 找到值所属的桶(第一个值小于，下一个桶的第一个值大于我们要插入的值)
• 如果插入后桶中的项目数为4，则必须拆分桶
  • 分桶时，2个值留在原桶中，2个值移到新桶中
  • 将新桶的第一个值(值较大的)插入父桶/节点
  • 如果父节点变满(4个值)，它以相同的方式 split ，但插入其父节点的值从桶中移除

让我们考虑一棵数字为 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

当一个父节点 split 时，新节点的第一个值被发送给它的父节点。在这棵树中，新节点是 (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时，桶 split ，新桶的第一个值被发送给父(新根):

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

应该注意的是，叶节点中没有任何内容被删除。删除仅发生在 split 的父节点中。

值 3 可以毫无问题地插入其桶中(桶将变为 1,3,5)。但是，尝试插入数字 9 会使桶装满 (1,3,5,9) 并且它会 split 。新桶 (5) 的第一个值将被插入到父桶中。

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

值 2 和 12 在不 split 的情况下适合它们的桶，因此树是:

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

---

要了解当中间节点 split 时会发生什么，让我们考虑以下树:

                           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