external searching and -trees consider the problem of maintaining large collection of items that does not fit in main memorysuch as typical database in this contextwe refer to the secondarymemory blocks as disk blocks likewisewe refer to the transfer of block between secondary memory and primary memory as disk transfer recalling the great time difference that exists between main memory accesses and disk accessesthe main goal of maintaining such collection in external memory is to minimize the number of disk transfers needed to perform query or update we refer to this count as the / complexity of the algorithm involved some inefficient external-memory representations typical operation we would like to support is the search for key in map if we were to store items unordered in doubly linked listsearching for particular key within the list requires transfers in the worst casesince each link hop we perform on the linked list might access different block of memory we can reduce the number of block transfers by using an array-based sequence sequential search of an array can be performed using only ( /bblock transfers because of spatial locality of referencewhere denotes the number of elements that fit into block this is because the block transfer when accessing the first element of the array actually retrieves the first elementsand so on with each successive block it is worth noting that the bound of ( /btransfers is only achieved when using compact array representation (see section the standard python list class is referential containerand so even though the sequence of references are stored in an arraythe actual elements that must be examined during search are not generally stored sequentially in memoryresulting in transfers in the worst case we could alternately store sequence using sorted array in this casea search performs (log ntransfersvia binary searchwhich is nice improvement but we do not get significant benefit from block transfers because each query during binary search is likely in different block of the sequence as usualupdate operations are expensive for sorted array 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 treestypicallyeach 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 but we can do betterwe can perform map queries and updates using only (logb no(log nlog btransfers