An m-ary tree is a data structure employed to improve external sorting in which for every node in the tree there are no more than m child nodes. Binary trees are a specific implementation of an m-ary tree where there are m = 2 child nodes for every node on the tree. This type of data tree is particularly important when in certain computing scenarios sorting must be done with the majority of the data remaining on auxiliary storage devices. An external sorting strategy, called the Hillsort, in combination with the m-ary tree architecture allowed the development of the Ternary Hillsort. This combinational sorting method is superior in its performance over the pure external sorting and the pure ternary tree since it executes faster and the parent-child and sibling relationships are easily calculated.

A tree is a type of organizational structuring of classes of elements, databases, or directory files that has a type of generalization or hierarchical architecture. This type of structure looks like a tree with its different branches and nodes. Also there is a unique path between any pair of nodes on the tree. The top of the file structure is called the root node and each entry on a different branch is called a child node of the parent. An m-ary tree is a particular type of tree where there are no more than m child nodes for every node in the tree. When m = 2 the tree is called a binary tree. This means that for each node on the tree that there are exactly two links to two other trees or subtrees where the two subtrees are often referred to as the left and right subtrees. This particular type of m-ary tree is the most commonly used type of tree data structure. If there are exactly m or zero child nodes for each node in the tree then the tree is called a full binary tree.

There is a simple formula for counting the number of nodes of an m-ary tree. If an m-ary tree has depth n and m > 1 then the number of nodes is given by:

• ⁰_k=0m^k = (mⁿ⁺¹-1)/(m-1).