th key in a B

Convert the B-tree to an order statistic tree to allow for this operation in O(log n).

That is, for each node, keep a variable representing the size (number of elements) of the subtree rooted at that node (that node, all its children, all its children's children, etc.).

Whenever you do an insertion or deletion, you update this variable appropriately. You will only need to update nodes already being visited, so it won't change the complexity of those operations.

Getting the k -th element would involve adding up the sizes of the children until we get to k , picking the appropriate child to visit and decreasing k appropriately. Pseudo-code:

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

Consider child[i] to be directly to the left of element[i] .

The pseudo-code for the binary search tree (not B-tree) provided on Wikipedia may explain the basic concept here better than the above.

Note that the size of a node's subtree should be store in its parent (note that I didn't use node.child[i].size above). Storing it in the node itself will be much less efficient, as reading nodes is considered a non-trivial or expensive operation for B-tree use cases (nodes must often be read from disk), thus you want to minimise the number of nodes read, even if that would make each node slightly bigger.

Do an in-order traversal until you've seen k elements - this will take O(n).

Pseudo-code:

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