search treesbut may waste some spacesince nodes are not entirely full the lower and upper bounds on the number of child nodes are typically fixed for particular implementation notes -tree is kept balanced by requiring that all leaf nodes are at the same depth this depth will increase slowly as elements are added to the treebut an increase in the overall depth is infrequentand results in all leaf nodes being one more hop further removed from the root figure schema showing the -tree structure -trees are balanced trees that are optimized for situations when part or the entire tree must be maintained in secondary storage such as magnetic disk since disk accesses are expensive (time consumingoperationsa -tree tries to minimize the number of disk accesses examplea -tree with height of and branching factor of can store over one billion keys but requires at most two disk accesses to search for any node structure of -trees unlike binary-treeeach node of -tree may have variable number of keys and children the keys are stored in non-decreasing order each key has an associated child that is the root of subtree containing all nodes with keys less than or equal to the key but greater than the preceding key node also has an additional rightmost child that is the root for subtree containing all keys greater than any keys in the node -tree has minimum number of allowable children for each node known as the minimization factor if is this minimization factorevery node must have at least keys under certain circumstancesthe root node is allowed to violate this property by having fewer than keys every node may have at most keys orequivalently children since each node tends to have large branching factor ( large number of children)it is typically necessary to traverse relatively few nodes before locating the desired key if access to each node requires disk accessthen -tree will minimize the number of disk accesses required the minimization factor is usually chosen so that the total size of each node corresponds to multiple of the block size of the underlying storage device this choice simplifies and optimizes disk access consequentlya -tree is an ideal data structure for situations where all data cannot reside in primary storage and accesses to secondary storage are comparatively expensive (or time consuminglovely professional university