Introduction

In this project, you will implement a B+-tree in which each node contain entries of the form [key, ptr] and some required header information. In the leaf node, ptr is the pointer pointing to the record id of a data record with search key value, and in the non-leaf node(index node), ptr is the pointer pointing to the child node which may be index or leaf node. Since we are not implementing data file layer in this project, we will keep all leaf node pointers NULL. You must implement the full search and insert algorithms as discussed in class. In particular, your insert routine must be capable of dealing with overflows (at any level of the tree) by splitting pages. Keys should be stored in sorted order. Deletes will be handled by simply deleting the key and pushing the remaining keys in the node. You do not need to implement merging of nodes on deletes. But, you do need to keep all nodes updated without any holes when records are deleted(i.e, when you delete a key