( ,btrees to reduce the number of external-memory accesses when searchingwe can represent our map using multiway search tree (section this approach gives rise to generalization of the ( tree data structure known as the (abtree an (abtree is multiway search tree such that each node has between and children and stores between and entries the algorithms for searchinginsertingand removing entries in an (abtree are straightforward generalizations of the corresponding ones for ( trees the advantage of generalizing ( trees to (abtrees is that generalized class of trees provides flexible search structurewhere the size of the nodes and the running time of the various map operations depends on the parameters and by setting the parameters and appropriately with respect to the size of disk blockswe can derive data structure that achieves good external-memory performance definition of an ( ,btree an ( ,btreewhere parameters and are integers such that < <( )/ is multiway search tree with the following additional restrictionssize propertyeach internal node has at least childrenunless it is the rootand has at most children depth propertyall the external nodes have the same depth proposition the height of an (abtree storing entries is (log nlog band (log nlog ajustificationlet be an (abtree storing entriesand let be the height of we justify the proposition by establishing the following bounds on + log( < <log log log by the size and depth propertiesthe number of external nodes of is at least ah- and at most bh by proposition thus ah- < <bh taking the logarithm in base of each termwe get ( log <log( < log an algebraic manipulation of these inequalities completes the justification