Exercises

The following exercises provide you with the opportunity to practice with B-trees and external-memory algorithms. The solutions to these exercises are found in the section .

1. Let’s say that we have a file in the filesystem that contains one million unsorted integers, and we want to find the greatest integer. The computer’s block size is 500, and its RAM can hold a total of 10,000 values. How many I/Os will it take for us to find the greatest integer?

2. Take a look at this B-tree:

   

   What will the B-tree look like after inserting the following values in this order: 180, 85, 91, 117?

3. Here’s another B-tree:

   

   What will the B-tree look like after inserting the following values in this order: 30, 40, 50?

4. Say that we have a B-tree containing 100,000 values, and each node can hold a maximum of 20 values. What is the greatest number of I/Os it would take to find any value?