sec -trees figure example of -tree of order four internal nodes must store between two and four children for this examplethe record size is assumed to be such that leaf nodes store between three and five records are found in the second subtree from the second child of the rootthe first branch is taken to reach the leaf node containing the actual record (or pointer to the actual recordwith key value here is pseudocode sketch of the -tree search algorithmprivate findhelp(bpnode rtkey kint currec binaryle(rt keys()rt numrecs() )if (rt isleaf()if ((((bpleaf)rtkeys())[currec=kreturn ((bpleaf)rtrecs(currec)else return nullelse return findhelp(((bpinternal)rtpointers(currec) ) -tree insertion is similar to -tree insertion firstthe leaf that should contain the record is found if is not fullthen the new record is addedand no other -tree nodes are affected if is already fullsplit it in two (dividing the records evenly among the two nodesand promote copy of the least-valued key in the newly formed right node as with the - treepromotion might cause the parent to split in turnperhaps eventually leading to splitting the root and causing the -tree to gain new level -tree insertion keeps all leaf nodes at equal depth figure illustrates the insertion process through several examples figure shows java-like pseudocode sketch of the -tree insert algorithm to delete record from the -treefirst locate the leaf that contains if is more than half fullthen we need only remove rleaving still at least half full this is demonstrated by figure if deleting record reduces the number of records in the node below the minimum threshold (called an underflow)then we must do something to keep the node sufficiently full the first choice is to look at the node' adjacent siblings to