Bottom-up B+ Tree Construction Algorithm

1. The records in the sorted input file are arranged into buckets (leaf nodes) which are 70% full.

2. Create the first node of the parent-of-leaf level in memory. Read in the first sorted leaf. Put the address of this leaf in the parent in memory.

3. Read in another sorted leaf. Put its lowest key value in the node at the lowest level which is not yet 70% full. If all nodes in the index are 70% full, create a new root. Put the key value from the current leaf node in the new root.

4. If the current index entry is above the parent-of-leaf level, create new nodes on all levels between the one where the entry is being placed and the leaf level. Put the address of each new node in the node above it. Put the address

of the leaf node in its parent. While creating the B+ tree, the memory may fill, but for the sake of this homework you can assume that all index nodes (except the leaves) fit in memory.

5. Repeat steps 3 and 4 until the sorted leaves are exhausted.

6. Clean up. At the end, there may be sparse nodes on the right-most position in any level. Adjust the tree structure. Flush all the nodes to the disk.