# CS443– Lab 5 solution

\$25.00

Original Work ?

## Description

5/5 - (1 vote)

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.

1. a) Redraw the tree after deleting 14.
2. b) Again, redraw the tree after deleting 15.
3. c) Again, redraw the tree after deleting 25.

Question 6:

Consider the following B+ tree:

1. Delete 29 and redraw the tree after that
2. Next delete 10 and redraw the tree after that
3. Next delete 26 and redraw the tree after that
4. Next delete 24 and redraw the tree after that
5. Next delete 9 and redraw the tree after that