we refer to this count as the / complexity of the algorithms involved some inefficient external-memory dictionaries let us first consider the simple dictionary implementations that us list to store entries if the list is implemented as an unsorteddoubly linked listthen insert and remove can be performed with ( transfers eachbut removals and searching require transfers in the worst casesince each link hop we perform could access different block this search time can be improved to ( /btransfers (see exercise - )where denotes the number of nodes of the list that can fit into blockbut this is still poor performance we could alternately implement the sequence using sorted array in this casea search performs (log ntransfersvia binary searchwhich is nice improvement but this solution requires ( /btransfers to implement an insert or remove operation in the worst casefor we may have to access all blocks to move elements up or down thuslist-based dictionary implementations are not efficient in external memory since these simple implementations are / inefficientwe should consider the logarithmic-time internal-memory strategies that use balanced binary trees (for exampleavl trees or red-black treesor other search structures with logarithmic average-case query and update times (for exampleskip lists or splay treesthese methods store the dictionary items at the nodes of binary tree or of graph typicallyeach node accessed for query or update in one of these structures will be in different block thusthese methods all require (log ntransfers in the worst case to perform query or update operation this performance is goodbut we can do better in particularwe can perform dictionary queries and updates using only (log no(logn/logbtransfers ( ,btrees to reduce the importance of the performance difference between internal-memory accesses and external-memory accesses for searchingwe can represent our dictionary using multi-way search tree (section this approach gives rise to generalization of the ( , tree data structure known as the ( ,btree an (abtree is multi-way search tree such that each node has between and children and stores between and entries the algorithms for searchinginsertingand removing entries in an (abtree are straightforward generalizations of the corresponding ones for ( , trees the advantage of generalizing ( , trees to ( ,btrees is that generalized class of trees provides flexible search structurewhere the size of the nodes and the running time of the various dictionary operations depends on the parameters and by setting the parameters and appropriately with respect to the size of disk blockswe can derive data structure that achieves good external-memory performance