they willbut different kind of tree must be used for external data than for inmemory 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 (strictly speaking - trees and trees are -trees of order and respectivelybut the term -tree is often taken to mean many more children per node 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 an , -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 blockswhich is probably enough for most files now we can no longer squeeze -byte records into block because 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 within each node the data is ordered sequentially by keyas in tree in factthe structure of -tree is similar to that of treeexcept that there are more data items per node and more links to children the order of -tree is the number of children each node can potentially have in our example this is so the tree is an order -tree searching search for record with specified key is carried out in much the same way it is in an in-memory tree firstthe block containing the root is read into memory the search algorithm then starts examining each of the records (orif it' not full