algorithm - 创建 B 树

Question

我明天要复习考试，但被困在一个问题上。我必须绘制一个有效的 B 树，其中 M = 4 和 L = 3 包含值 1-25。问题是我无法让我的树看起来像答案。答案树如下所示：

             9            14             22
            /       |             |        \
         4 7       12           17 20        24
        / | \     /  \         /  |  \      /  \
       1  4  7   9   12      14  17  20   22   24
       2  5  8   10  13      15  18  21   23   25
       3  6      11          16  19  21  

抱歉，如果这很难阅读。也许我把答案复制错了，但任何人都可以确认这是否是正确的答案？如果是这样，这个答案是如何得出的？

Answer 1

看起来您在谈论 B+ 树而不是 BTree，并且有一个小错字：您在叶子 [20,21,21] 中重复了键 21。正如你所说，订单是4。

答案是一棵有效的 B+ 树，但不是通过按顺序添加值 1-25 得到的树。问题是否给出了添加密钥的特定顺序，或者是尝试自己确定的问题？除了漫长的试错过程之外，我不确定您将如何确定序列，但您可以使用此处的演示页面进行尝试：

http://goneill.co.nz/btree-demo.php

如果您想尝试各种插入序列，最好下载离线版本并编辑 Hardcoded() 函数：

http://goneill.co.nz/btree.php

这一切都在 JavaScript 中，但可能对您没有用处。