A PARTS file with Part# as key field includes records with the following Part# values: 23, 65, 37, 60, 46, 92, 48, 71, 56, 59, 18, 21, 10, 74, 78, 15, 16, 20, 24, 28, 39, 43, 47, 50, 69, 75, 8, 49, 33, 38. Suppose the search field values are inserted in the given order in a B + -tree of order p=4 and p leaf =3; show how the tree will expand and what the final tree looks like.

Question

What will be an ideal response?

Answer 1

A B + -tree of order p=4 implies that each internal node in the tree (except possibly the root) should have at least 2 keys (3 pointers) and at most 4 pointers. For p leaf =3, leaf nodes must have at least 2 keys and at most 3 keys. The figure on page 50 shows how the tree progresses as the keys are inserted. We will only show a new tree when insertion causes a split of one of the leaf nodes, and then show how the split propagates up the tree.
Hence, step 1 below shows the tree after insertion of the first 3 keys 23, 65, and 37, and before inserting 60 which causes overflow and splitting. The trees given below show how the keys are inserted in order. Below, we give the keys inserted for each tree:
1 :23, 65, 37; 2:60; 3:46; 4:92; 5:48, 71; 6:56; 7:59, 18; 8:21; 9:10; 10:7 4 ;
11:78; 12:15; 13:16; 14:20; 15:24; 16:28, 39; 17:43, 47; 18:50, 69; 19:7 5 ;
20:8, 49, 33, 38;