Consider the Extendible Hashing index shown in Figure 11.1. Answer the following questions about this index:

1. What can you say about the last entry that was inserted into the index?
2. What can you say about the last entry that was inserted into the index if you know that there have been no deletions from this index so far?
3. Suppose you are told that there have been no deletions from this index so far.
What can you say about the last entry whose insertion into the index caused a split?
4. Show the index after inserting an entry with hash value 68.
5. Show the index after inserting entries with hash values 17 and 69 into the original tree.
6. Show the index after deleting the entry with hash value 21 into the original tree. (Assume that the full deletion algorithm is used.)
7. Show the index after deleting the entry with hash value 10 into the original tree. Is a merge triggered by this deletion? If not, explain why. (Assume that the full deletion algorithm is used.)

Transcribed Image Text:

64 16Bucket A 2 Bucket B 1 5 21 001 010 011 100 101 110 Bucket C 10 Bucket D 15 7 51 DIRECTORY Bucket A2 4 12 20 36