R Data Structures and Algorithms

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 ...