trees figure -tree of order an example of -tree of order is shown in figure notice that all nonleaf nodes have between three and five children (and thus between two and four keys)the root could possibly have only two children herewe have it happens that and are the same in this examplebut this is not necessary since is each leaf has between three and five data items requiring nodes to be half full guarantees that the -tree does not degenerate into simple binary tree although there are various definitions of -trees that change this structuremostly in minor waysthis definition is one of the popular forms each node represents disk blockso we choose and on the basis of the size of the items that are being stored as an examplesuppose one block holds , bytes in our florida exampleeach key uses bytes in -tree of order mwe would have - keysfor total of bytesplus branches since each branch is essentially number of another disk blockwe can assume that branch is bytes thus the branches use bytes the total memory requirement for nonleaf node is thus - the largest value of for which this is no more than , is thus we would choose since each data record is byteswe would be able to fit records in block thus we would choose we are guaranteed that each leaf has between and data records and that each internal node (except the rootbranches in at least ways since there are , , recordsthere areat most , leaves consequentlyin the worst caseleaves would be on level in more concrete termsthe worst-case number of accesses is given by approximately logm/ ngive or take (for examplethe root and the next level could be cached in main memoryso that over the long rundisk accesses would be needed only for level and deeper the remaining issue is how to add and remove items from the -tree the ideas involved are sketched next note that many of the themes seen before recur we begin by examining insertion suppose we want to insert into the -tree in figure search down the tree reveals that it is not already in the tree we can add it to the leaf as fifth item note that we may have to reorganize all the data in the leaf to do this howeverthe cost of doing this is negligible when compared to that of the disk accesswhich in this case also includes disk write of coursethat was relatively painlessbecause the leaf was not already full suppose we now want to insert figure shows problemthe leaf where wants to go is already full the solution is simplesince we now have itemswe split them into two