Suppose we wish to create a B tree on a computer with a block size of...

 

Transcribed Image Text:

Suppose we wish to create a B tree on a computer with a block size of 2048 bytes and pointers of 8 bytes. The records we wish to store in the tree are 200 bytes each, including keys of 12 bytes. (i) [3 marks] What is the maximum number of children for an index node that is not the root? What is the minimum number of children for an index node that is not the root? (ii) [2 marks] What are the minimum and maximum numbers of records that can be stored in a leaf node that is not the root? (iii) [1 mark] What is the minimum number of children for a root that is not a leaf node? [3 marks] Briefly explain why Big-O analysis is generally not meaningful for B trees. To measure efficiency for B trees, what should we count instead of using Big-O notation? c) [4 marks] Consider the following B-tree which has order M=3 and in which each leaf node can hold a maximum of L-3 records. Only the keys of the records are shown. Suppose that a record with key value 1 is inserted into this tree. Draw the resulting tree. 5 10 15 20 40 25 45 30 50 35 55 60 65 70 60 120 80 100 90 95 110 115 140 160 125 150 135 155 165 170 Suppose we wish to create a B tree on a computer with a block size of 2048 bytes and pointers of 8 bytes. The records we wish to store in the tree are 200 bytes each, including keys of 12 bytes. (i) [3 marks] What is the maximum number of children for an index node that is not the root? What is the minimum number of children for an index node that is not the root? (ii) [2 marks] What are the minimum and maximum numbers of records that can be stored in a leaf node that is not the root? (iii) [1 mark] What is the minimum number of children for a root that is not a leaf node? [3 marks] Briefly explain why Big-O analysis is generally not meaningful for B trees. To measure efficiency for B trees, what should we count instead of using Big-O notation? c) [4 marks] Consider the following B-tree which has order M=3 and in which each leaf node can hold a maximum of L-3 records. Only the keys of the records are shown. Suppose that a record with key value 1 is inserted into this tree. Draw the resulting tree. 5 10 15 20 40 25 45 30 50 35 55 60 65 70 60 120 80 100 90 95 110 115 140 160 125 150 135 155 165 170

Answer rating: 100% (QA)

Solution Given Block size of B tree 2048 bytes Block pointer size p 8 bytes Record sizer 200 bytes Key size k 12 bytes We know that B tree is a implem... View the full answer