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

Question

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

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

Answer 1

没有使用标准 B 树的有效方法。一般来说，我看到两种选择:

• 将 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