themwhich at milliseconds per read and write requires more than five minutes to insert single entry this won' be satisfactory if you have thousands of new names to add to the phone book another problem with the sequential ordering is that it only works quickly for one key our file is arranged by last names but suppose you wanted to search for particular phone number you can' use binary searchbecause the data is ordered by name you would need to go through the entire fileblock by blockusing sequential access this would require reading an average of half the blockswhich would require about minutesvery poor performance for simple search it would be nice to have more efficient way to store disk data -trees how can the records of file be arranged to provide fast searchinsertionand deletion timeswe've seen that trees are good approach to organizing in-memory data will trees work with filesthey willbut different kind of tree must be used for external data than for in-memory data the appropriate tree is multiway tree somewhat like treebut with many more data items per nodeit' called -tree -trees were first conceived as appropriate structures for external storage by bayer and mccreight in one block per node why do we need so many items per nodewe've seen that disk access is most efficient when data is read or written one block at time in treethe entity containing data is node it makes sense then to store an entire block of data in each node of the tree this wayreading node accesses maximum amount of data in the shortest time how much data can be put in nodewhen we simply stored the -byte data records for our phone book examplewe could fit into , -byte block in treehoweverwe also need to store the links to other nodes (which means links to other blocksbecause node corresponds to blockin an in-memory treesuch as those we've discussed in previous these links are references (or pointersin languages like ++to nodes in other parts of memory for tree stored in disk filethe links are block numbers in file (from to , in our phone book examplefor block numbers we can use field of type inta -byte typewhich can point to more than billion possible blocksprobably enough for most files now we can no longer squeeze -byte records into blockbecause we need room for the links to child nodes we could reduce the number of records to to make room for the linksbut it' most efficient to have an even number of records per nodeso (after appropriate negotiation with managementwe reduce the record size to bytes there will be child links (one more than the number of data itemsso the links will require bytes ( this leaves room for -byte records with bytes left over ( , block in such treeand the corresponding node representationis shown in figure