we restrict our discussion here to the / complexity of -trees figure -tree of order an important property of -trees is that we can choose so that the children references and the keys stored at node can all fit into single disk blockimplying that is proportional to this choice allows us to assume that and are also proportional to in the analysis of the search and update operations on (abtrees thusf(band (bare both ( )for each time we access node to perform search or an update operationwe need only perform single disk transfer as we have already observed aboveeach search or update requires that we examine at most ( nodes for each level of the tree thereforeany dictionary search or update operation on -tree requires only (log / )that iso(logn/logb)disk transfers for examplean insert operation proceeds down the btree to locate the node in which to insert the new entry if the node would overflow (to have childrenbecause of this additionthen this node is split into two nodes that have ( )/ and ( )/ childrenrespectively this process is then repeated at the next level upand will continue for at most (log nlevels likewiseif remove operation results in node underflow (to have / - children)then we move references from sibling node with at least / children or we need to perform afusion operation of this node with its sibling (and repeat this computation at the parentas with the insert operationthis will continue up the -tree for at most (logbnlevels the requirement that each internal node have at least / children implies that each disk block used to support -tree is at least half full thuswe have the followingproposition -tree with entries has / complexity (log nfor search or update operationand uses ( /bblockswhere is the size of block external-memory sorting in addition to data structuressuch as dictionariesthat need to be implemented in external memorythere are many algorithms that must also operate on input sets that