Hash-Based Indexing 111 Level=0, N=4 PRIMARY h 1 h0 PAGES Next=0 000 00 64 44 001 01 9 25 5 010 10 10 011 11 31 15 7 3 Figure 11.7 Figure forExercise 11.9 Answer 11.9 The answer to each question is given below. 1. The maximum number of entries that can be inserted without causing a split is 6 because there is space for a total of 6 records in all the pages. A split is caused whenever an entry is inserted into a full page. 2. See Fig 11.8 3. (a) Consider the list of insertions 63, 41, 73, 137 followed by 4 more entries which go into the same bucket, say 18, 34, 66, 130 which go into the 3rd bucket. The insertion of 63 causes the first bucket to be split. Insertion of 41, 73 causes the second bucket split leaving a full second bucket. Inserting 137 into it causes third bucket-split. At this point at least 4 more entries are required to split the fourth bucket. A minimum of 8 entries are required to cause the 4 splits. (b) Since all four buckets would have been split, that particular round comes to an end and the next round begins. So Next = 0 again. (c) There can be either one data page or two data pages in the fourth bucket nd after these insertions. If the 4 more elements inserted into the 2 bucket rd th after 3 bucket-splitting, then 4 bucket has 1 data page. th rd If the new 4 more elements inserted into the 4 bucket after 3 bucket- th spliting and all of them have 011 as its last three bits, then 4 bucket has 2 th data pages. Otherwise, if not all have 011 as its last three bits, then the 4 bucket has 1 data page.
