Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

c - Algorithm to find k-th key in a B-tree?

I'm trying to understand how I should think about getting the k-th key/element in a B-tree. Even if it's steps instead of code, it will still help a lot. Thanks

Edit: To clear up, I'm asking for the k-th smallest key in the B-tree.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

There's no efficient way to do it using a standard B-tree. Broadly speaking, I see 2 options:

  • 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
    

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

2.1m questions

2.1m answers

60 comments

57.0k users

...