examining the node at level the third branch is taken to the next level to arrive at the leaf node containing record with key value -tree insertion is generalization of - tree insertion the first step is to find the leaf node that should contain the key to be insertedspace permitting if there is room in this nodethen insert the key if there is notthen split the node into two and promote the middle key to the parent if the parent becomes fullthen it is split in turnand its middle key promoted note that this insertion process is guaranteed to keep all nodes at least half full for examplewhen we attempt to insert into full internal node of -tree of order fourthere will now be five children that must be dealt with the node is split into two nodes containing two keys eachthus retaining the -tree property the middle of the five children is promoted to its parent -trees the previous section mentioned that -trees are universally used to implement large-scale disk-based systems actuallythe -tree as described in the previous section is almost never implementednor is the - tree as described in section what is most commonly implemented is variant of the -treecalled the -tree when greater efficiency is requireda more complicated variant known as the -tree is used when data are staticit is an extremely efficient way to search the problem is those pesky inserts and deletes imagine that we want to keep the idea of storing sorted listbut make it more flexible by breaking the list into manageable chunks that are more easily updated how might we do thatfirstwe need to decide how big the chunks should be since the data are on diskit seems reasonable to store chunk that is the size of disk blockor small multiple of the disk block size we could insert new record with chunk that hasn' filled its block but what if the chunk fills up the entire block that contains itwe could just split it in half what if we want to delete recordwe could just take the deleted record out of the chunkbut we might not want lot of near-empty chunks so we could put adjacent chunks together if they have only small amount of data between them or we could shuffle data between adjacent chunks that together contain more data the big problem would be how to find the desired chunk when processing record with given key perhaps some sort of tree-like structure could be used to locate the appropriate chunk these ideas are exactly what motivate the -tree the -tree is essentially mechanism for managing list broken into chunks the most significant difference between the -tree and the bst or the - tree is that the -tree stores records only at the leaf nodes internal nodes store key