againas in - treeit' not the middle item in node that' promoted upwardbut the middle item in the sequence formed from the items in the node plus the new item we'll demonstrate these features of the insertion process by building small -treeas shown in figure there isn' room to show realistic number of records per nodeso we'll show only fourthusthe tree is an order -tree figure shows root node that' already fullitems with keys and have already been inserted into the tree new data item with key of is insertedresulting in node split here' how the split is accomplished because it' the root that' being splittwo new nodes are created (as in tree) new root and new node to the right of the one being split to decide where the data items gothe insertion algorithm arranges their five keys in orderin an internal buffer four of these keys are from the node being splitand the fifth is from the new item being inserted in figure these five-item sequences are shown to the side of the tree in this first step the sequence is shown the center item in this sequence in this first stepis promoted to the new root node (in the figurean arrow indicates that the center item will go upward all the items to the left of center remain in the node being splitand all the items to the right go into the new right-hand node the result is shown in figure (in our phone book exampleeight items would go into each child noderather than the two shown in the figure in figure we insert two more items and they fill up the left childas shown in figure the next item to be inserted splits this left childwith the result shown in figure here the has been promoted upward into the root nextthree items-- and --are inserted into the tree the first two fill up the third childand the third splits itcausing the creation of new node and the promotion of the middle item to the root the result is shown in figure again three items-- and --are added to the tree the first two items fill up the second childand the third one splits itcausing the creation of new node and the promotion of the middle item to the rootas shown in figure now the root is full howeversubsequent insertions don' necessarily cause node splitbecause nodes are split only when new item is inserted into full nodenot when full node is encountered in the search down the tree thus and are inserted in the second child without causing any splitsas shown in figure