within each node the data is ordered sequentially by keyas in tree in factthe structure of -tree is similar to that of treeexcept that there are more data items per node and more links to children the order of -tree is the number of children each node can potentially have in our example this is so the tree is an order btree searching search for record with specified key is carried out in much the same way it is in an in-memory tree firstthe block containing the root is read into memory the search algorithm then starts examining each of the records (orif it' not fullas many as the node actually holds)starting at when it finds record with greater keyit knows to go to the child whose link lies between this record and the preceding one this process continues until the correct node is found if leaf is reached without finding the specified keythe search is unsuccessful insertion the insertion process in -tree is somewhat different than it is in tree recall that in tree many nodes are not fulland in fact contain only one data item in particulara node split always produces two nodes with one item in each this is not an optimum approach in -tree in -tree it' important to keep the nodes as full as possible so that each disk accesswhich reads an entire nodecan acquire the maximum amount of data to help achieve this endthe insertion process differs from that of trees in three waysa node split divides the data items equallyhalf go to the newly created nodeand half remain in the old one node splits are performed from the bottom up rather than from the top down it' 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 fourthus the tree is an order -tree