some nodes contain itemsome and some if we estimate that the average is search times will be proportional to *log this is small constant number that can be ignored in big notation thusfor trees the increased number of items per node tends to cancel out the decreased height of the tree the search times for tree and for balanced binary tree such as red-black tree are approximately equaland are both (lognstorage requirements each node in tree contains storage for three references to data items and four references to its children this space may be in the form of arraysas shown in tree javaor of individual variables not all this storage is used node with only one data item will waste two thirds of the space for data and half the space for children node with two data items will waste one third of the space for data and one quarter of the space for childrento put it another wayit will use / of the available space if we take two data items per node as the average utilizationabout / of the available storage is wasted one might imagine using linked lists instead of arrays to hold the child and data referencesbut the overhead of the linked list compared with an arrayfor only or itemswould probably not make this worthwhile approach because they're balancedred-black trees contain few nodes that have only one childso almost all the storage for child references is used alsoevery node contains the maximum number of data itemswhich is this makes red-black trees more efficient than trees in terms of memory usage in javawhich stores references to objects instead of the objects themselvesthis difference in storage between trees and red-black trees may not be importantand the programming is certainly simpler for trees howeverin languages that don' use references this waythe difference in storage efficiency between red-black trees and trees may be significant external storage trees are an example of multiway treeswhich have more than two children and more than one data item another kind of multiway treethe -treeis useful when data resides in external storage external storage typically refers to some kind of disk systemsuch as the hard disk found in most desktop computers or servers in this section we'll begin by describing various aspects of external file handling we'll talk about simple approach to organizing external datasequential ordering finally we'll discuss -trees and explain why they work so well with disk files we'll finish with another approach to external storageindexingwhich can be used alone or with -tree we'll also touch on other aspects of external storagesuch as searching techniques in the next we'll mention different approach to external storagehashing the details of external storage techniques are dependent on the operating systemlanguageand even the hardware used in particular installation as consequenceour discussion in this section will be considerably more general than for most topics in this book accessing external data