Description
1. Suppose that a page can contain at most four data values and that all data values are
integers. Using only B+ trees of order 2, give examples of each of the following:
a. A B+ tree whose height changes from 2 to 3 when the value 25 is inserted.
Show your structure before and after the insertion.
b. A B+ tree in which the deletion of the value 30 leads to a redistribution. Show
your structure before and after the deletion.
c. A B+ tree in which the deletion of the value 35 causes a merging of two nodes
but without altering the height of the tree.
2. Answer the following questions about Linear Hashing:
a. How does Linear Hashing provide an average-case search cost of only slightly
more than one disk I/O, given that overflow buckets are part of its data
structure?
b. Does Linear Hashing guarantee at most one disk access to retrieve a record
with a given key value?