Q.1 [36 pts, 12 pts each] Construct a B+ tree for each of the following parts...

 

Transcribed Image Text:

Q.1 [36 pts, 12 pts each] Construct a B+ tree for each of the following parts by inserting the following key values in the given order: 44, 20, 22, 32, 34, 46, 17, 38, 26, 18 You should use the insertion algorithm provided in the textbook. (a) The order of the tree (i.e., n) is 3 (i.e., cach node can hold 2 search key values). (b) The order of the tree is 1. (c) The order of the tree is 5. Q.2 [40 pts pts] Consider an extendable hash structure where buckets can hold 3 search key values. The entries with the key values listed below are inserted in the following order: 57, 28, 26, 98, 38, 79, 7, 109, 30 The hash function given is h(x)= x mod 16. The hash value of a search key is a 4-bit binary value. Use the most significant bit of the hash value during insertion. (a) [25 pts] Insertion of which key values leads to bucket splits? Which of those splits causes the bucket address table to double? (b) [15 pts] After inserting all key values, i. What is the global depth of the bucket address table? ii. What is the local depth of the bucket that contains 267 iii. What is the local depth of the bucket that contains 109? iv. What is the local depth of the bucket that contains 7? v. What is the local depth of the bucket that contains 79? Q.3 [24 pts] (a) [8 pts] If the size of a file is 5,000 pages, and the memory size is 50, what is the number of merge passes required to sort the file? (b) [16 pts] If the size of a file is 100,000, what is the minimum number of pages of memory required to sort the file in 2 merge passes? Q.1 [36 pts, 12 pts each] Construct a B+ tree for each of the following parts by inserting the following key values in the given order: 44, 20, 22, 32, 34, 46, 17, 38, 26, 18 You should use the insertion algorithm provided in the textbook. (a) The order of the tree (i.e., n) is 3 (i.e., cach node can hold 2 search key values). (b) The order of the tree is 1. (c) The order of the tree is 5. Q.2 [40 pts pts] Consider an extendable hash structure where buckets can hold 3 search key values. The entries with the key values listed below are inserted in the following order: 57, 28, 26, 98, 38, 79, 7, 109, 30 The hash function given is h(x)= x mod 16. The hash value of a search key is a 4-bit binary value. Use the most significant bit of the hash value during insertion. (a) [25 pts] Insertion of which key values leads to bucket splits? Which of those splits causes the bucket address table to double? (b) [15 pts] After inserting all key values, i. What is the global depth of the bucket address table? ii. What is the local depth of the bucket that contains 267 iii. What is the local depth of the bucket that contains 109? iv. What is the local depth of the bucket that contains 7? v. What is the local depth of the bucket that contains 79? Q.3 [24 pts] (a) [8 pts] If the size of a file is 5,000 pages, and the memory size is 50, what is the number of merge passes required to sort the file? (b) [16 pts] If the size of a file is 100,000, what is the minimum number of pages of memory required to sort the file in 2 merge passes?