英文:
How to delete a key from a B+ Tree such that this key exist in an internal node and has another copy from it in a leaf node?
问题
所有的在线教程都说，你应该删除叶节点中的副本，然后将内部节点中的另一个副本替换为该键的后继节点。我的问题是，我们如何确保这个后继节点在替换我们在内部节点中的键副本之前不存在于内部节点中，因为如果发生这种情况，那么该键（后继节点）的值将存在于多个内部节点中，而不止一次。我在在线教程中没有找到对这个问题的答案。
英文:
All the online tutorials said that you shall delete the copy in the leaf node then make the other copy in the internal node = (the successor of that key) , my question is that what guarantees for us that this successor wasn't existing in an internal node before replacing our key copy in the internal node by it , because if such a thing happened we will have the value of that key (successor) existing more than one time in more than one internal node.
I found no answers for that in the online tutorials
答案1
得分: 0
在回答您的问题之前，将内部节点的键视为实际的数据键是一个误解。它们只是索引键，实际上不需要属于树的数据集，尽管通常会更新它们以反映其相应子树中存在的最小键。
在评论中，您提到了这个文档以及删除键25的示例：
但请注意，不一定需要严格更新父节点中的键。同样的文档在开头提到：
- 步骤1 找到包含要删除的(key, pointer)条目的叶子节点L
- 步骤2 从L中删除条目
- 步骤2a 如果L满足“半满”条件，那么我们完成了。
删除键25的情况符合步骤2a的条件，也就是说，从叶子节点中删除后，“我们完成了”。这是真的。在这种情况下，祖先节点中的键的更新是可选的。
现在来回答您的主要问题：
什么能保证我们的这个后继在替换内部节点中的键副本之前不存在于内部节点中？
存在于内部节点中的键始终是下一级子树中键的下界。除非由于删除而导致该子树发生移动或合并，否则该子树中的最小键将成为以前不是该子树中的最小键的键。在示例中，28不是子树中的最小键，因为该子树中的最小键是25。因此，我们可以确定28不在内部节点中。
如果叶子节点恰好只有25作为键，情况就不同了，但然后我们就会进入移动或合并操作，这将导致多个键的更新。
英文:
Before getting to your question, it is a misconception to regard the keys of the internal nodes as actual data keys. They are merely index-keys, and don't really need to belong to the tree's data set, although it is common to have them updated to reflect the minimum key that is present in its corresponding subtree.
In comments you refer to this documentation and to the example of the deletion of the key 25:
But note that the update of the key in a parent node is not strictly necessary. The same documentation stated at the start:
> * STEP 1 Find leaf L containing (key,pointer) entry to delete
> * STEP 2 Remove entry from L
> * STEP 2a If L meets the "half full" criteria, then we're done.
The case where key 25 is removed, fits the condition of step 2a, i.e. after it has been removed from the leaf node, "we're done". This is actually true. In this case the update of the key in ancestor node(s) is optional.
Now to your main question:
> what guarantees for us that this successor wasn't existing in an internal node before replacing our key copy in the internal node by it
The keys that exist in internal nodes are always a lower bound for the keys in the next subtree below it. Unless that subtree will undergo shifts or merges due to the deletion, the least key in that subtree will become a key that previously was not the least key in that same subtree. In the example, 28 was not the least key in the subtree because that least key in that subtree was 25. So we can be sure 28 is not present in an internal node.
It is a different story if the leaf node happened to only have 25 as key, but then we get into a shift or merge operation, which will bring updates to multiple keys.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论