这个B+树有效吗？

Question

在B+树中，是否存在一个非叶节点，从而删除它的键值？这意味着B+树在它的中间非叶节点中有一个值，而在它的任何叶节点中没有值。

请考虑以下结构。我是在研究B+树的时候发现这个的。在此结构中，13不是叶节点。但它是一个非叶节点。(事实上，它在以前的指示中已被删除。图片链接。在这个链接中，转到页面底部)

​

​

如果是的话，为什么删除这些数据？

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

Answer 1

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

Douglas在B+树上做了一个全面的视频系列，这比阅读文章更容易学习。第1部分可以找到这里。

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

如果您正在搜索一个12，并到达13，您将比较是12 < 13或13 <= 12，左边是真，所以您将遍历到左边的叶子。无论13是否为16，都会发生这种情况，因为这也是真正的12 < 16。

如果您正在搜索16并到达您将比较的13是16 < 13或13 <= 16，则正确的表达式为真，因此您将遍历到右叶。然后，您将在那里找到16的值。

如果您搜索的是13 (并不存在)，您会问13 < 13或13 <= 13，正确的表达式是真的，所以您将遍历到右边的叶子，发现那里没有13，此时您会发现13没有任何价值。