Homework S Time: November 11, 2018 Name: Banner ID (Tree-structured Indexing) Indexing methods are used to speed up access to desired data. Consider the B+ tree index of order P- 5 and 4 shown in the following figure, where P is the number of pointers (to children nodes) of a non- leaf node and R is the number of pointers (to buckets of records) of a leaf node. B-tree is an index fle so it is a separate file from the actual data. Therefore, if a value is already in the leaf node, the trece structure is not changing. The structure of each internal node should have fixed number of spaces for pointers and values. Each value in the leaf node should be associated with an asterisk, which denotes a pointer to actual data. Also, the leaf nodes need to be linked with a double-arrow-head, which denotes a double-pointer. The method to build a B'-tree should be consistency. For example, when splitting a node into two nodes, the first half values put into the left node and the remaining second half values put into the right node. When the splitting is taking place at the leaf node, we need to copy the first value in the right node to its parent. When it happens at the internal node, we need to move the first value in the right node to its parent. The following B+-Tree properties should hold at every step: . For an internal node with (nV, P: all data in the subtree to which the pointer Pi points are less than the value V. value V Each node should have at least half full, except the root node. All paths from the root of the tree to a leaf node are of the same length. On the other hand, all data in the subtree to which the pointer p: points are greater than or equal to the . . The structure of every internal node should have n pointers and (n-1) search-key values. . The values in a node should be in an ascending order. Note: Use the insertion and deletion algorithms given in the slide 2 and 13 of the PowerPoint (tiled) B.Irc Example, respectively Tasks