Build a B+ tree of order 4 (maximum 4 characters and minimum 2 characters for each node) with 3 levels to sort this list.

.A database file is stored on the harddrive. It is a linked-list structure. To go through all the records (rows) of a database table, it would have to follow all the links (pointors) into harddrive locations to get data, which is not acceptable as harddrive accesses are slow. Building B' trees will help a lot. The leaves of a B tree from left to right defines an order in the database table, while records in the databse table do not have to be stored in any order on the harddrive. Each leave keeps a value of relevant attributes. For example, we can build two B' trees, one on the order of jt and another tree on lastName and firstName for the student table. These two B' trees will make query processing more efficieny for relevant queries on these orders. The tree depth is the maxium number of harddrive accesses for locating a particular record. Keeping one or two levels of a B' tree in the memery will eliminate harddrive accesses to tree nodes at these levels. At least the tree root should be in the memory and limit the tree to at most 3 levels. Building a B' tree is a process of inserting nodes (representing database records by keeping value(s) of relevant attributes in these nodes). When a record is removed from a table, its corresponding node will also be removed from the B' tree Consider the following list of characters as keys: NIKMEMSAOHDBUQLAC Build a B+tree of order 4 (maximum 4 characters and minimum 2 characters for each node) with 3 levels to sort this list. The sorted list will be in the leaf nodes of the tree in the alphabetic order reading from left to right. For each character (key value), there is a pointer (address) pointing to a harddrive location where the row of table with this key value is kept. Start with an empty tree. Then insert this sequence of characters (as key values) one after another. After each insertion, show the tree. After the sequence of insertions is done, do deletions for this same sequence of characters (key values). At the end, the tree should be empty Do not skip a step unless it is clear from the context