figure -ary tree of nodes has only three levels we want to reduce the number of disk accesses to very small constantsuch as three or four we are willing to write complicated code to do thisbecause machine instructions are essentially freeas long as we are not ridiculously unreasonable it should probably be clear that binary search tree will not worksince the typical avl tree is close to optimal height we cannot go below log using binary search tree the solution is intuitively simpleif we have more branchingwe have less height thuswhile perfect binary tree of nodes has five levelsa -ary tree of nodes has only three levelsas shown in figure an -ary search tree allows -way branching as branching increasesthe depth decreases whereas complete binary tree has height that is roughly log na complete -ary tree has height that is roughly logm we can create an -ary search tree in much the same way as binary search tree in binary search treewe need one key to decide which of two branches to take in an -ary search treewe need keys to decide which branch to take to make this scheme efficient in the worst casewe need to ensure that the -ary search tree is balanced in some way otherwiselike binary search treeit could degenerate into linked list actuallywe want an even more restrictive balancing condition that iswe do not want an -ary search tree to degenerate to even binary search treebecause then we would be stuck with log accesses one way to implement this is to use -tree the basic -tree is described here many variations and improvements are knownand an implementation is somewhat complex because there are quite few cases howeverit is easy to see thatin principlea -tree guarantees only few disk accesses -tree of order is an -ary tree with the following properties: the data items are stored at leaves the nonleaf nodes store up to keys to guide the searchingkey represents the smallest key in subtree the root is either leaf or has between two and children all nonleaf nodes (except the roothave between  / and children all leaves are at the same depth and have between  / and data itemsfor some (the determination of is described shortly what is described is popularly known as btree rules and must be relaxed for the first insertions