// COURSE: Database II - Master of Computer Science // Please read carefully This assignment is about Extendible Hashing. For more information on this topic recall the lecture slides on Database Indexing and the readings on Disk Storage, Basic File Structures, and Hashing as well as on Indexing Structures for Files. In addition to your answer to a question also include all essential ideas and steps that are necessary to derive the solution. Write your solution in an understanding form or draw the respectively structure with some tool you might find fitting. You may need to format your files into .pdf! ------------------------------------------------------------------------------------------------- !! Before you start read this !! For the following tasks on Extendible Hashing we consider the last n bits of an element, when assigning it into a bucket. For example, consider the number 40 which can be converted in binary format as 101000. Assuming the global depth is 1,2,3,4,5 or 6, respectively, this number would be stored in the following bucket: 0, 00, 000, 1000, 01000 or 101000. In the following tasks, when you are asked to show a hash structure, make sure to include all information in your solution that is needed to obtain this hash structure using Extendible Hashing. Task 1: In this task you are asked to build a hash structure using Extendible Hashing. Assume the bucket size is 3. First we want to insert some elements into the hash structure, and afterwards delete some elements from it. If you are unsure in which bucket you should insert a converted number,read the hint on the bottom of the previous page again. (a) Start with globaldepth = 1 and an empty hash structure. Insert the following sequence of elements into it: 3, 5, 10, 12, 400, 90, 55, 555, 128, 130 Show your hash structure after each insertion! (b) Now you need to delete some elements from your hash structure in part (a). Delete the following sequence of elements: 130, 12, 55, 5