as consequencethe new root page contains single item only the details can be gathered from the program presented belowand fig shows the result of using the program to construct -tree with the following insertion sequence of keys the semicolons designate the positions of the snapshots taken upon each page allocation insertion of the last key causes two splits and the allocation of three new pages fig growth of -tree of order since each activation of search implies one page transfer to main storek logn(nrecursive calls are necessary at mostif the tree contains items hencewe must be capable of accommodating pages in main store this is one limiting factor on the page size in factwe need to accommodate even more than pagesbecause insertion may cause page splitting to occur corollary is that the root page is best allocated permanently in the primary storebecause each query proceeds necessarily through the root page another positive quality of the -tree organization is its suitability and economy in the case of purely sequential updating of the entire data base every page is fetched into primary store exactly once deletion of items from -tree is fairly straight-forward in principlebut it is complicated in the details we may distinguish two different circumstances the item to be deleted is on leaf pagehere its removal algorithm is plain and simple the item is not on leaf pageit must be replaced by one of the two lexicographically adjacent itemswhich happen to be on leaf pages and can easily be deleted in case finding the adjacent key is analogous to finding the one used in binary tree deletion we descend along the rightmost pointers down to the leaf page preplace the item to be deleted by the rightmost item on pand then reduce the size of by in any casereduction of size must be followed by check of the