gpt4 book ai didi

algorithm - 从 B-Tree 中删除 - M=5

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:03:18 24 4
gpt4 key购买 nike

在非常具体的情况下,我正在处理 BTree 中的删除

M=5 - 即 - 节点中键的最大数量为 4,节点中键的最小数量为 2

现在当我使用防御方法(我必须使用这种方法)在 BTree 中删除时,当我接近一个节点时,我必须保证它比所需的最小值多一个键。

这是我的问题 - 假设我有一个带一把 key 的根和两个带两个 key 的 child 。当我接近这些 child 中的一个时,我将必须保证它至少有 3 个 key (因为 M=5)。

我有两种方法 - 向邻居借用或向父亲借用并合并。我不能从邻居那里借用,因为它至少有 2 个键,但是从父亲那里借用并合并创建了一个有 5 个键的节点 - 它超过了允许的键的最大值(因为 M = 5)。

遇到这种情况怎么办?更具体地说 - 处理这种情况的正确方法是什么

最佳答案

对于某些 d,经典 B 树将非根节点的键计数限制在 d 和 2d 之间。这意味着只有当下溢已经发生并且参与合并的其他节点占用最少时,才可能合并节点。连同从父节点提取的分隔键,这使得键计数为 (d - 1) + d + 1 = 2d,这是适合节点的最大值。 “以防万一”在下降的路上合并是不可能的。

关于algorithm - 从 B-Tree 中删除 - M=5,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30570227/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com