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 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 -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 example items would go into each child noderather than the 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 - howeverthe next item to be inserted does cause splitin fact it causes two of them the second node child is fullso it' splitas shown in figure - howeverthe promoted from this splithas no place to go because the root is full thereforethe root must be split as wellresulting in the arrangement of figure - notice that throughout the insertion process no node (except the rootis ever less than half fulland many are more than half full as we notedthis promotes efficiency because file access that reads node always acquires substantial amount of data efficiency of -trees because there are so many records per nodeand so many nodes per leveloperations on -trees are very fastconsidering that the data is stored on disk in our phone book example there are , records all the nodes in the -tree are at least half fullso they contain at least records and links to children the height of the tree is thus somewhat less than log (logarithm to the base of )where is , this is so there will be about levels in the tree thususing -treeonly six disk accesses are necessary to find any record in file of , records at milliseconds per accessthis takes about millisecondsor / of second this is dramatically faster than the binary search of sequentially ordered file the more records there are in nodethe fewer levels there are in the tree we've seen that there are levels in our -treeeven though the nodes hold only records in