Algorithms
General n-ary trees

If we relax the restriction that each node can have only one key, we can reduce the height of the tree.
An m-way search tree
  1. is empty or
  2. consists of a root containing j (1<=j<m) keys, kj, and
    a set of sub-trees, Ti, (i = 0..j), such that
    1. if k is a key in T0, then k <= k1
    2. if k is a key in Ti (0<i<j), then ki <= k <= ki+1
    3. if k is a key in Tj, then k > kj and
    4. all Ti are nonempty m-way search trees or all Ti are empty
Or in plain English ..
  1. A node generally has m-1 keys and m children.
    Each node has alternating sub-tree pointers and keys:
    sub-tree | key | sub-tree | key | ... | key | sub_tree

    1. All keys in a sub-tree to the left of a key are smaller than it.
    2. All keys in the node between two keys are between those two keys.
    3. All keys in a sub-tree to the right of a key are greater than it.
    4. This is the "standard" recursive part of the definition.

The height of a complete m-ary tree with n nodes is ceiling(logmn).

Example applications include memory storage model used in GIS, distributed wireless self-healing networks and parallel biological modeling algorithms.

A B-tree of order m is an m-way tree in which

  1. all leaves are on the same level and
  2. all nodes except for the root and the leaves have at least m/2 children and at most m children. The root has at least 2 children and at most m children.

Developed by Ed McCreight, a Wooster alum and retired engineer at Adobe. This data structure has extensive applications and one example is its use in whole genome alignment.

A variation of the B-tree, known as a B+-tree considers all the keys in nodes except the leaves as dummies. All keys are duplicated in the leaves. This has the advantage that is all the leaves are linked together sequentially, the entire tree may be scanned without visiting the higher nodes at all.

Key terms

n-ary trees (or n-way trees)
Trees in which each node may have up to n children.
B-tree
Balanced variant of an n-way tree.
B+-tree
B-tree in which all the leaves are linked to facilitate fast in order traversal.