Question 1: An ordered index was originally maintained as a sequential file. Suppose an ordered index is supported as a sequential file. In a sequential file, an index-entry needs to be inserted into an overflow block, when there is no space to insert the index-entry in the block, as it should follow the sorting order. (Refer to the slides 10.16-10.17 in ch10.pptx). However, an overflow block can be full as well. Thus, you may need to insert an index-entry in an overflow block of the overflow block concerned. Suppose that you need to insert 20 distinctive search key values into a sequential file, where a block can only keep 4 index-entries. Let the search key of the 20 records be the numbers from 1 to 20. Show a worst inserting order of the 20 search key values that will result in the largest number of block accesses when you need to access all the 20 index-entries following the search key order sequentially. (Hint: You do not need to consider buffering.) Question 2: Consider a relation s with one attribute A. Suppose you have to insert the following A = {10,60, 20, 8, 9, 15, 19, 18, 12, 7} into the relation s. Construct a B+-tree on the attribute A of s. Following the pseudo-code of B+- tree given in the textbook (or the slides in ch11.pptx), construct a B+-tree with n= 3. Assume that the B+-tree is initially empty. (1) Given A, insert the key values in such an order, and show the B+-tree after every insertion. (2) Given the B+-tree constructed in the step (1), show how the B+-tree is changed step-by-step following the pseudo-code when the key value 9 is deleted. (3) Given the B+-tree constructed in the step (2), show how the B+-tree is changed step-by-step following the ideas shown in pseudo-code when the key value 60 is deleted. Question 3: On the slide 11.48 in ch11.pptx, we discussed how to delete "Gold from the index, precisely, to delete it from the leave node in B+-tree. As shown in the slide, the search key value of "Gold remains in the non-leaf node. (1) The way to allow a search key value, which does not exist in any leaf node, in a non-leaf node is valid. Explain why it is valid. (2) Suppose that you need to modify the pseudo-code given in the textbook or in the lecture note to disallow a search key value, which does not exist in the leaf-node, in any non-leaf node. Do as follows. Explain when it will happen using examples to show its before/after B+-tree. Consider both merge and redistribution. Explain where it will possibly happen in B+-tree using examples. Note that such a non-existing key may appear in an ancestor node only the parent node) of the node being upd Show the main ideas how/where you modify the pseudo-code. Explain how you handle the deletion of "Gold on the slide 11.48 in ch11.pptx Give your pseudo-code. Discuss whether it is cost-effective doing it compared with the ap- proach given in the textbook. . Question 4: In the textbook, there are such details given on how to handle deletion by the extendable hashing. On the slide 11.23 in ch11-hash.pptx, it points out decreasing bucket address table size is also possible. (1) Show the case when the bucket address table size can be reduced using an example. (2) Give the steps how to reduce the bucket address table size. (3) Explain why it can be expensive. Gold Califieri, Einstein Kim lams Brandt 1- Kim Mozart T-Califieri Crick || -| Einstein||E1 Said|| - Gold|Katz| Califieri Einstein Gold Adams Brandt TH-Califieri Crick TH-Einstein El Said It-Katz Kim Mozart