search and update operations we recall that in multiway search tree each node of holds secondary structure ( )which is itself map (section if is an (abtreethen (vstores at most entries let (bdenote the time for performing search in mapm(vthe search algorithm in an (abtree is exactly like the one for multiway search trees given in section hencesearching in an (abtree (bwith entries takes olog log ntime note that if is considered constant (and thus is also)then the search time is (log nthe main application of (abtrees is for maps 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 describe this structurehoweverlet us discuss how insertions and removals are handled in (abtrees the insertion algorithm for an (abtree is similar to that for ( tree an overflow occurs when an entry is inserted into -node wwhich becomes an illegal ( )-node (recall that node in multiway 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 (abtree 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 wdistinct 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 map realized with an (abtree operation running time [ko [kv del [ko (blog log (blog log (blog log table time bounds for an -entry map realized by an (abtree 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