handled in ( ,btrees the insertion algorithm for an (abtree is similar to that for ( , tree an overflow occurs when an entry is inserted into -node vwhich becomes an illegal ( )-node (recall that node in multi-way tree is -node if it has children to remedy an overflowwe split node by moving the median entry of into the parent of and replacing with ( )/ -node and ( )/ node we can now see the reason for requiring <( )/ in the definition of an ( ,btree note that as consequence of the splitwe need to build the secondary structures ( 'and ( ''removing an entry from an (abtree is similar to what was done for ( , trees an underflow occurs when key is removed from an -node vdistinct from the rootwhich causes to become an illegal ( )-node to remedy an underflowwe perform transfer with sibling of that is not an -node or we perform fusion of with sibling that is an -node the new node resulting from the fusion is ( )-nodewhich is another reason for requiring <=( )/ table shows the performance of dictionary realized with an (abtree table time bounds for an -entry dictionary realized by an ( ,btree we assume the secondary structure of the nodes of support search in (btimeand split and fusion operations in (btimefor some functions (band ( )which can be made to be ( when we are only counting disk transfers -trees version of the (abtree data structurewhich is the best known method for maintaining dictionary in external memoryis called the " -tree (see figure -tree of order is an (abtree with / and since we