increasing order from left to right if the -tree is squeezed into single level by inserting the descendants in between the keys of their ancestor page this arrangement represents natural extension of binary search treesand it determines the method of searching an item with given key consider page of the form shown in fig and given search argument assuming that the page has been moved into the primary storewe may use conventional search methods among the keys km- if is sufficiently largeone may use binary searchif it is rather smallan ordinary sequential search will do (note that the time required for search in main store is probably negligible compared to the time it takes to move the page from secondary into primary store if the search is unsuccessfulwe are in one of the following situations ki ki+ for - the search continues on page pi km- the search continues on page pm- the search continues on page - - pm- km- pm- fig -tree page with keys if in some case the designated pointer is nili if there is no descendant pagethen there is no item with key in the whole treeand the search is terminated surprisinglyinsertion in -tree is comparatively simple too if an item is to be inserted in page with itemsthe insertion process remains constrained to that page it is only insertion into an already full page that has consequences upon the tree structure and may cause the allocation of new pages to understand what happens in this caserefer to fig which illustrates the insertion of key in -tree of order it proceeds in the following steps key is found to be missinginsertion in page is impossible because is already full page is split into two pages ( new page is allocated the + keys are equally distributed onto and dand the middle key is moved up one level into the ancestor page fig insertion of key in -tree this very elegant scheme preserves all the characteristic properties of -trees in particularthe split pages contain exactly items of coursethe insertion of an item in the ancestor page may again cause that page to overflowthereby causing the splitting to propagate in the extreme case it may propagate up to the root this isin factthe only way that the -tree may increase its height the -tree has thus strange manner of growingit grows from its leaves upward to the root we shall now develop detailed program from these sketchy descriptions it is already apparent that recursive formulation will be most convenient because of the property of the splitting process to propagate