data-structures - 这个 B+ 树有效吗？

Question

在 B+ 树中，是否可以存在非叶节点以删除其键值？这意味着 B+ 树在其中间非叶节点中具有值，但在其任何叶节点中都没有。

考虑以下结构。我在研究 B+ 树时遇到了这个问题。在这个结构中，13 不是叶节点。但它是一个非叶子节点。（实际上在前面的说明中已删除。图片链接。在此链接中转到页面底部）

如果是，那么数据是如何被删除的？

这是一个错误还是我遗漏了什么？

Answer 1

您发布的图像是有效的。此树返回的唯一数据是您在最后一行中找到的数据。因为13已从树中删除，所以已从最后一行中删除。13存在于非叶节点中的事实对您的结果没有影响，它只是在遍历树时有一个可比较的值。在这种情况下，如果将13更改为 a 16（基于上述约定），树的行为将没有什么不同。

Douglas Fisher 做了一个关于 B+ 树的综合视频系列，比阅读文章更容易学习。第 1 部分可在此处找到。

---

编辑：我在评论中的回复太长了，所以我会放在这里。另外，这是有用的信息。

如果您正在搜索 a12并到达13，您将比较 IS12 < 13 或13 <= 12，左侧为真，因此您将向下遍历到左侧叶子。不管是不是，这都会发生13，16因为这也是事实12 < 16。

如果您正在搜索16并到达13您将比较 IS16 < 13或13 <= 16，则正确的表达式为真，因此您将向下遍历到右叶。然后你会发现16那里的价值。

如果您正在搜索13（不存在），您会问 IS13 < 13或13 <= 13，正确的表达式为真，因此您将向下遍历到右叶并发现那里不13存在，此时您将踢出13有没有价值。