end end deleteprocedure showtree (var wtexts writerppagelevelinteger)var iintegerbegin if nil then for : to level do texts write( xendfor : to - do texts writeint(wp [ikey endtexts writeln( )if then showtree(wp level+ endfor : to - do showtree(wp [iplevel+ end end end showtreeextensive analysis of -tree performance has been undertaken and is reported in the referenced article (bayer and mccreightin particularit includes treatment of the question of optimal page sizewhich strongly depends on the characteristics of the storage and computing system available variations of the -tree scheme are discussed in knuthvol pp - the one notable observation is that page splitting should be delayed in the same way that page merging is delayedby first attempting to balance neighboring pages apart from thisthe suggested improvements seem to yield marginal gains comprehensive survey of -trees may be found in [ - binary -trees the species of -trees that seems to be least interesting is the first order -tree ( but sometimes it is worthwhile to pay attention to the exceptional case it is plainhoweverthat first-order -trees are not useful in representing largeorderedindexed data sets invoving secondary storesapproximately of all pages will contain single item only thereforewe shall forget secondary stores and again consider the problem of search trees involving one-level store only binary -tree (bb-treeconsists of nodes (pageswith either one or two items hencea page contains either two or three pointers to descendantsthis suggested the term - tree according to the definition of -treesall leaf pages appear at the same leveland all non-leaf pages of bb-trees have either two or three descendants (including the rootsince we now are dealing with primary store onlyan optimal economy of storage space is mandatoryand the representation of the items inside node in the form of an array appears unsuitable an alternative is the dynamiclinked allocationthat isinside each node there exists linked list of items of length or since each node has at most three descendants and thus needs to harbor only up to three pointersone is tempted to combine the pointers for descendants and pointers in the item list as shown in fig the -tree node thereby loses its actual identityand the items assume the role of nodes in regular binary tree it remains necessaryhoweverto distinguish between pointers to descendants (verticaland pointers to siblings on the same page (horizontalsince only the pointers to the right may be horizontala single bit is sufficient to record this distiction we therefore introduce the boolean field with the meaning horizontal the definition of tree node based on this representation is given below it was suggested and investigated by bayer [ - in and represents search tree organization guaranteeing *log(nas maximum path length type node pointer to record keyintegerleftrightnodehboolean (*right branch horizontal*