$18.20
SOLVED CS443 Lab 5
Question 1:
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#.
Question 2:
Consider the following records of question 1:
2369, 3760, 4692, 4871, 5659, 1821, 1074, 7151, 1620
Load the records into expandable hash files based on extendible hashing. You can put two records per block. Show the directory at each step, and the global and local depths. Use the hash function h(k) = K mod 32 to find the bucket number. For example,
Record# K h(K) bucket number binary h(K)
record1 2369 1 00001
record2 3760 16 10000
record3 4692 20 10100
………. ……. ……. ………….
………. ……. ……. ………….
………. ……. ……. ………….
Question 3:
Insert the following into B-tree of order 4. Show your work step by step with proper illustration of pointers as shown in pages 20-29 in multi-way trees lecture
8, 2, 80, 25, 26, 27, 28, 55, 71, 15, 51, 20, 21, 22, 23, 24, 63, 90, 35
Question 4:
Insert the following into B+ tree of order 3. Show your work step by step with proper illustration of pointers as shown in pages 47-54 in multi-way trees lecture
90, 22, 27, 24, 28, 20, 51, 63, 8, 80, 15, 71, 35, 55
Question 5:
Consider the following B-tree.
a) Redraw the tree after deleting 14.
b) Again, redraw the tree after deleting 15.
c) Again, redraw the tree after deleting 25.
Question 6:
Consider the following B+ tree:
- Delete 29 and redraw the tree after that
- Next delete 10 and redraw the tree after that
- Next delete 26 and redraw the tree after that
- Next delete 24 and redraw the tree after that
- Next delete 9 and redraw the tree after that