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

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

编辑：为了清理，我要求B树中的第k个最小的键。

Answer 1

使用标准B树没有有效的方法。 从广义上讲，我看到两个选择：

• 将B树转换为订单统计树，以允许在O（log n）中执行此操作。

  也就是说，对于每个节点，保留一个变量，该变量表示以该节点为根的子树的大小（元素的数量）（该节点，其所有子节点，所有子节点的子节点等）。

  无论何时进行插入或删除，都要适当地更新此变量。 您只需更新已访问的节点，因此不会更改这些操作的复杂性。

  获得第k个元素将涉及将孩子的大小相加，直到我们到达k ，选择适当的孩子来访问并适当地减少k 。 伪代码：

   select(root, k) // initial call for root // returns the k'th element of the elements in node function select(node, k) for i = 0 to t.elementCount size = 0 if node.child[i] != null size = node.sizeOfChild[i] if k < size // element is in the child subtree return select(node.child[i], k) else if k == size // element is here && i != t.elementCount // only equal when k == elements in tree, ie k is not valid return t.element[i] else // k > size, element is to the right k -= size + 1 // child[i] subtree + t.element[i] return null // k > elements in tree 

  考虑child[i]直接位于element[i]的左侧。

  维基百科上提供的二叉搜索树（不是B树）的伪代码可以比上面更好地解释这里的基本概念。

  请注意，节点子树的大小应存储在其父节点中（请注意，我没有使用node.child[i].size ）。 将它存储在节点本身的效率要低得多，因为读取节点被认为是B树用例的非平凡或昂贵的操作（节点通常必须从磁盘读取），因此您希望最小化读取的节点数，即使这会使每个节点略大。

• 在你看到k元素之前进行有序遍历 – 这将需要O（n）。

  伪代码：

   select(root, *k) // initial call for root // returns the k'th element of the elements in node function select(node, *k) // pass k by pointer, allowing global update if node == null return null for i = 0 to t.elementCount element = select(node.child[i], k) // check if it's in the child's subtree if element != null // element was found return element if i != t.elementCount // exclude last iteration if k == 0 // element is here return t.element[i] (*k)-- // only decrease k for t.element[i] (ie by 1), // k is decreased for node.child[i] in the recursive call return null 

Answer 2

您可以使用新的平衡二叉搜索树（如Splay或仅使用std :: set）来记录B树中当前的元素。 这将允许每个操作在O（logn）中完成，并且它很容易实现（当使用std :: set时）但是会使空间成本加倍。

Answer 3

好吧，经过几个不眠时，我设法做到了，对于任何想知道怎么做的人来说，这里是伪代码（第一个元素为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 

我知道这可能看起来有点奇怪，但这是我想出来的，幸好它有效。 可能有一种方法可以使这些代码更清晰，并且可能更有效，但我希望它足以帮助那些可能像我一样陷入同样障碍的其他人。