tree rotation in red-black tree corresponds to changing between the two possible orientations (slantswhen transforming -node the height of tree is less than log search times are proportional to the height the tree wastes space because many nodes are not even half full 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 hash tables overview hash table is data structure that offers very fast insertion and searching when you first hear about themhash tables sound almost too good to be true no matter how many data items there areinsertion and searching (and sometimes deletioncan take close to constant timeo( in big notation in practice this is just few machine instructions for human user of hash table this is essentially instantaneous it' so fast that computer programs typically use hash tables when they need to look up tens of thousands of items in less than second (as in spelling checkershash tables are significantly faster than treeswhichas we learned in the preceding operate in relatively fast (logntime not only are they fasthash tables are relatively easy to program hash tables do have several disadvantages they're based on arraysand arrays are difficult to expand once they've been created for some kinds of hash tablesperformance may degrade catastrophically when the table becomes too fullso the programmer needs to have fairly accurate idea of how many data items will need to be stored (or be prepared to periodically transfer data to larger hash tablea timeconsuming processalsothere' no convenient way to visit the items in hash table in any kind of order