required (because there is less empty space in the disk fileand in more efficient processing (fewer blocks on average will be read into memory because the amount of information in each block is greaterbecause -trees have become so popularmany algorithm designers have tried to improve -tree performance one method for doing so is to use the -tree variant known as the -tree the -tree is identical to the -treeexcept for the rules used to split and merge nodes instead of splitting node in half when it overflowsthe -tree gives some records to its neighboring siblingif possible if the sibling is also fullthen these two nodes split into three similarlywhen node underflowsit is combined with its two siblingsand the total reduced to two nodes thusthe nodes are always at least two thirds full -tree analysis the asymptotic cost of searchinsertionand deletion of records from -treesb-treesand -trees is th(log nwhere is the total number of records in the tree howeverthe base of the log is the (averagebranching factor of the tree typical database applications use extremely high branching factorsperhaps or more thusin practice the -tree and its variants are extremely shallow as an illustrationconsider -tree of order and leaf nodes that contain up to records one-level -tree can have at most records two-level -tree must have at least records ( leaves with records eachit has at most , records ( leaves with records eacha three-level -tree must have at least records (two second-level nodes with children containing records eachand at most one million records ( second-level nodes with full children eacha four-level -tree must have at least , records and at most million records thusit would require an extremely large database to generate -tree of more than four levels we can reduce the number of disk fetches required for the -tree even more by using the following methods firstthe upper levels of the tree can be stored in main memory at all times because the tree branches so quicklythe top two levels (levels and require relatively little space if the -tree is only four levels deepthen at most two disk fetches (internal nodes at level two and leaves at level threeare required to reach the pointer to any given record this concept can be extended further if higher space utilization is required howeverthe update routines become much more complicated once worked on project where we implemented -for- node split and merge routines this gave better performance than the -for- node split and merge routines of the -tree howeverthe spitting and merging routines were so complicated that even their author could no longer understand them once they were completed