c - 在B树中找到第k个 key 的算法？

我试图理解我应该如何考虑在b树中获取第k个键/元素。即使是步骤而不是代码，它仍然会有很大帮助。谢谢
编辑：为了澄清，我要的是B-树中第k个最小的键。

最佳答案

使用标准的b树是没有效率的。大体而言，我认为有两种选择：
将b树转换为order statistic tree以允许在o（log n）中执行此操作。
也就是说，对于每个节点，保留一个变量，该变量表示根在该节点（该节点、其所有子节点、其所有子节点等）的子树的大小（元素数）。
无论何时插入或删除，都会相应地更新此变量您只需要更新已经访问过的节点，这样就不会改变这些操作的复杂性。
要得到k-th元素，需要将孩子的大小相加，直到我们到达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

关于c - 在B树中找到第k个 key 的算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22414339/