an ( ,btreewhere and are integerssuch 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 /log band (log /log ajustificationlet be an (abtree storing entriesand let be the height of we justify the proposition by establishing the following bounds on hby 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 ( )loga <log( <hlogb search and update operations we recall that in multi-way search tree teach node of holds secondary structure ( )which is itself dictionary (section if is an (abtreethen (vstores at most entries let (bdenote the time for performing search in (vdictionary the search algorithm in an (abtree is exactly like the one for multi-way search trees given in section hencesearching in an (abtree with entries takes ( ( )/logalogntime note that if is constant (and thus is also)then the search time is (lognthe main application of (abtrees is for dictionaries stored in external memory namelyto minimize disk accesseswe select the parameters and so that each tree node occupies single disk block (so that ( if we wish to simply count block transfersproviding the right and values in this context gives rise to data structure known as the -treewhich we will describe shortly before we