一尘不染

在B树中找到第k个密钥的算法?

algorithm

我试图了解如何考虑如何在B树中获取第k个键/元素。即使它是步骤而不是代码,它仍然会有所帮助。谢谢

编辑:要清理,我要求B树中的第k个最小键。


阅读 241

收藏
2020-07-28

共1个答案

一尘不染

好的,经过几个小时的不眠不休,我设法做到了,对于任何想知道如何做的人,这里都是伪代码(第一个元素k = 0):

get_k-th(current, k):

for i = 0 to current.number_of_children_nodes
    int size = size_of_B-tree(current.child[i])
    if(k <= size-1)
        return get_k-th(current.child[i], k)
    else if(k == size && i < current.number_of_children_nodes)
        return current.key[i]
    else if (is_leaf_node(current) && k < current.number_of_children_nodes)
        return node.key[k]
    k = k - size - 1;

return null

我知道这可能看起来有些奇怪,但这是我想出的,而且幸运的是它可以工作。可能有一种方法可以使此代码更清晰,也可能更有效,但是我希望它能很好地帮助其他可能遇到与我相同的障碍的人。

2020-07-28