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

Question

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

编辑:为清楚起见，我要求 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