back along the search path the general structure of the program will therefore be similar to balanced tree insertionalthough the details are different first of alla definition of the page structure has to be formulated we choose to represent the items in the form of an array type page pointer to pagedescriptoritem record keyintegerppagecountinteger (*data*endpagedescriptor record minteger( * pageearray * of item end againthe item component count stands for all kinds of other information that may be associated with each itembut it plays no role in the actual search process note that each page offers space for items the field indicates the actual number of items on the page as > (except for the root page) storage utilization of least is guaranteed the algorithm of -tree search and insertion is formulated below as procedure called search its main structure is straightforward and similar to that for the balanced binary tree searchwith the exception that the branching decision is not binary choice insteadthe "within-page searchis represented as binary search on the array of elements the insertion algorithm is formulated as separate procedure merely for clarity it is activated after search has indicated that an item is to be passed up on the tree (in the direction toward the rootthis fact is indicated by the boolean result parameter hit assumes similar role as in the algorithm for balanced tree insertionwhere indicates that the subtree had grown if is truethe second result parameterurepresents the item being passed up note that insertions start in hypothetical pagesnamelythe "special nodesof fig the new item is immediately handed up via the parameter to the leaf page for actual insertion the scheme is sketched hereprocedure search (xintegerapagevar hbooleanvar uitem)begin if nil then (* not in treeinsert*assign to item uste to trueindicating that an item is passed up in the tree else binary search for in array eif found then process data else search(xdescendanthu)if then (*an item was passed up*if no of items on page then insert on page aand set to false else split page and pass middle item up end end end end end search if the paramerter is true after the call of search in the main programa split of the root page is requested since the root page plays an exceptional rolethis process has to be programmed separately it consists merely of the allocation of new root page and the insertion of the single item given by the paramerter