Chapter 7

These are the solutions to the .

1. It takes one I/O to load each block. There are N/B blocks, which in this case is:

   ​	10000 data elements / 500 block size = 2000 blocks

   And so, we have to perform 2,000 I/Os.

2. After inserting the 180, 85, 91, and 117, the B-tree will appear like this:

   

3. Inserting a 30, 40, and 50 will cause the tree to grow another level and end up like this:

   

4. Searching a B-tree takes O(log_{B + 1} N) I/Os in a worst-case scenario. When a B-tree node has nodes that hold 20 values, this means that the variable B is 20 since a B-tree’s node size matches the computer’s block size.

   In our case, we have log₂₁ 100,000 I/Os, which computes to about 3.781520977582. Therefore, we can find anything in this B-tree with a maximum of 4 I/Os.