Exercises

1. Consider that a secondary-level index with 10,400 blocks needs to be represented using multi-level linear indexing. The blocking factor is 52 entries per block, which is also the fan-out factor for multi-level indexing:

   • How many levels are required for indexing?

   • How many blocks are required at the second level?

   • What would be the minimum blocking factor to fit the dataset using a second-level linear index?

2. Write the code for deletion of an element from a 2-3 tree. Also, prove that the number of leaf nodes in a 2-3 tree with height h will be between 2^h-1 and 3^h-1.

3. Assume a computer system with disk blocks of 8,192, and that you want to store records with 16-byte keys and 64-byte fields. What will be the greatest number of records that can be stored in a file if a linear index of size 4 MB is used?Assume the records are sorted and packaged sequentially into the disk file.

4. In the balanced binary tree given in the figure that follows, how many nodes will become unbalanced when inserted as...