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 Ki > k.
• Follow pointer Pi to another node.
• If k < K1 follow pointer P1.
• 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 logdn=2e(K).

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 log50(1; 000; 000) = 4 nodes to be accessed. Since root is in usually in the bu er, so typically it takes only 3 or fewer disk reads.