DB2 - WS 2015/16 - Assignment 4 (Minimal B+Tree) ================================================ 1) Download. Download the file 'assignment4.zip' and unpack it. Rename nnnnnnn_4.py to matrikel_4.py, such that if your matrikel number is 1234567 the file is named 1234567_4.py In subdirectory 'test' we provided simple test cases for you to evaluate your solutions. 'in.txt' stores a sequence of consecutive numbers from 1 to 10. Each file 'out_mX.txt' stores the correct output for specific number of pointers X. You may test your code by calling cat in.txt | python nnnnnnn_4.py M where M is the number of pointers in a node and 'in.txt' stores the keys. ATTENTION: Please stick to the naming convention because your assignments are fetched, processed, and verified automatically. If the file name is incorrect we may miss your assignment and you may not pass. 2) Assignment description. In this assignment we implement a procedure of building a minimal B+Tree for a given set of keys and the number of pointers M. By minimal, we understand the minimal number of levels in a tree. The program reads the keys from the standard input and sorts. Building the B+Tree is a two-step process. Step 1: The input keys are partitioned to leaf nodes, the nodes are created and appended to a list of all nodes. Step 2: The inner-node levels of the tree are created in a loop. The loop terminates when the root node is created. For level k (root is level 1) the pointers to nodes from level k+1 are partitioned to the nodes on level k. The keys are looked up in the leaf nodes by following the pointers. Data structures: - All nodes of our tree are stored in a list. - Each node is also a list storing the node ID and its keys and pointers (all being integer numbers). - The node IDs are consecutive integer numbers assigned in the order of node creation. The first created node has ID=0, the last one (root) has ID equal to the number of nodes in the tree minus 1. - Example structure of a node: [ID, p1, k1, p2, k2, p3, ... , kn-1, pn], where ID is the node's ID, pi (1<=i