-trees version of the (abtree data structurewhich is the best-known method for maintaining map in external memoryis called the " -tree (see figure -tree of order is an (abtree with / and since we discussed the standard map query and update methods for (abtrees abovewe 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 fit compactly 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 map search or update operation on -tree requires only (logd/ )that iso(log nlog )disk transfers for examplean insert operation proceeds down the -tree 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 (logb nlevels likewiseif remove operation results in node underflow (to have / children)then we move references from sibling node with at least / children or we perform fusion 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 (logb nlevels 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 (logb nfor search or update operationand uses ( /bblockswhere is the size of block