fig binary tree subdivided into pages the saving in the number of disk accesses -each page access now involves disk access -can be considerable assume that we choose to place nodes on page (this is reasonable figure)then the million item search tree will on the average require only log ( ( about page accesses instead of butof courseif the tree is left to grow at randomthen the worst case may still be as large as it is plain that scheme for controlled growth is almost mandatory in the case of multiway trees multiway -trees if one is looking for controlled growth criterionthe one requiring perfect balance is quickly eliminated because it involves too much balancing overhead the rules must clearly be somewhat relaxed very sensible criterion was postulated by bayer and mccreight [ in every page (except onecontains between and nodes for given constant hencein tree with items and maximum page size of nodes per pagethe worst case requires lognn page accessesand page accesses clearly dominate the entire search effort moreoverthe important factor of store utilization is at least since pages are always at least half full with all these advantagesthe scheme involves comparatively simple algorithms for searchinsertionand deletion we will subsequently study them in detail the underlying data structures are called -treesand have the following characteristicsn is said to be the order of the -tree every page contains at most items (keys every pageexcept the root pagecontains at least items every page is either leaf pagei has no descendantsor it has + descendantswhere is its number of keys on this page all leaf pages appear at the same level fig -tree of order figure shows -tree of order with levels all pages contain or itemsthe exception is the root which is allowed to contain single item only all leaf pages appear at level the keys appear in