在一个B中键

将B-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]的左边。

维基百科上提供的二叉搜索树（不是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] (i.e. by 1),
                // k is decreased for node.child[i] in the recursive call 
   return null