Queries on B -Trees

1. Suppose we want to find all records with a search key value of k.
   • Examine the root node and find the smallest search key value .
   • Follow pointer to another node.
   • If follow pointer .
   • Otherwise, find the appropriate pointer to follow.
   • Continue down through non-leaf nodes, looking for smallest search key value > k and following the corresponding pointer.
   • Eventually we arrive at a leaf node, where pointer will point to the desired record or bucket.
2. In processing a query, we traverse a path from the root to a leaf node. If there are K search key values in the file, this path is no longer than .

   This means that the path is not long, even in large files. For a 4k byte disk block with a search-key size of 12 bytes and a disk pointer of 8 bytes, n is around 200. If n =100, a look-up of 1 million search-key values may take nodes to be accessed. Since root is in usually in the buffer, so typically it takes only 3 or fewer disk reads.