CS5481
Data Engineering Tutorial 4
1. a)
Given the following B+-tree, insert the search-key values 31, 41, 40 in order.
13
23
43
7
43
47
2
3
5
7
11
13
17
19
23
29
37
For the resultant B+-tree in a), show the form of the tree after deleting 7, 11, 43, 37 c) Re-create the resultant B+-tree in a), i.e., rebuild the tree from an empty tree, using
bottom-up B+-tree construction.
2. Consider a hash function on integer search keys i defined by h(i) = i2 mod B, where B
is the number of buckets. What is wrong with this hash function if B = 10?
3. A PARTS file with Part# as hash key includes records with the following Part# values: 2369, 3760, 4692, 4871, 5659, 1821, 1074, 7115, 1620, 2428, 3943, 4750, 6975, 4981, 9208. The file uses 8 buckets, numbered 0 to 7. Each bucket is one disk block and holds two records. Load these records into the file in the given order using the hash function h(K)=K mod 8. Calculate the average number of block accesses for a random retrieval on Part#.
b)
and 41 in order.