在 B 树中查找第 k 个键的算法？

Question

我想了解我应该如何考虑在 B 树中获取第 k 个 key/element。即使它是步骤而不是代码，它仍然会有很大帮助。谢谢

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

Answer 1

没有使用标准 B 树的有效方法。一般来说，我看到 2 个选项：

将 B 树转换为 order statistic tree 以允许在 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, i.e. 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] 的左边。

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

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

执行 in-order traversal 直到您看到 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] (i.e. 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 时）但会使 space 成本加倍。

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

我知道这可能看起来有点奇怪，但这是我想出的，谢天谢地它有效。可能有一种方法可以使这段代码更清晰，也可能更高效，但我希望它足以帮助其他可能遇到与我相同的障碍的人。

在 B 树中查找第 k 个键的算法？

Algorithm to find k-th key in a B-tree?

c

algorithm

b-tree