data-structures - 如何进行 B-Tree 插入

Question

我正在尝试将 3 个值插入到此 B 树中，即 60、61 和 62。我了解如何在节点已满且父节点为空时插入值，但如果父节点已满怎么办？

例如，当我插入 60 和 61 时，该节点现在将已满。我无法扩展父级或父级的父级（因为它们已满）。那么我可以改变父母的价值观吗？我在插入之前和之后提供了 B 树的图像。

尝试插入 60、61、62： 注意我将根中的 66 更改为 62，并将 62 添加到 <72 节点。这是正确的方法吗？

Answer 1

完成插入后，您将获得通常称为 B* 树的内容。在“纯”B树中，当根已满时插入需要将当前根分成两个节点，并在它们之上创建一个新的根节点（B树实现不要求根节点遵循相同的规则作为最小后代数量的其他节点，因此只允许有两个）。