trees and external storage - tree is similar to treeexcept that it can have only one or two data items and onetwoor three children insertion in - tree involves finding the appropriate leaf and then performing splits from the leaf upwarduntil non-full node is found external storage means storing data outside of main memoryusually on disk external storage is largercheaper (per byte)and slower than main memory data in external storage is typically transferred to and from main memory block at time data can be arranged in external storage in sequential key order this gives fast search times but slow insertion (and deletiontimes -tree is multiway tree in which each node may have dozens or hundreds of keys and children there is always one more child than there are keys in -tree node for the best performancea -tree is typically organized so that node holds one block of data if the search criteria involve many keysa sequential search of all the records in file may be the most practical approach questions these questions are intended as self-test for readers answers may be found in appendix tree is so named because node can have three children and four data items twothreeor four children two parentsthree childrenand four items two parentsthree itemsand four children tree is superior to binary search tree in that it is imagine parent node with data items and if one of its child nodes had items with values and it would be the child numbered true or falsedata items are located exclusively in leaf nodes