A pruned trie is a trie in which the linear subtrees are “pruned” down to one character each. A pruned trie requires less space, but it may require examination of more than one bucket in order to determine which one is the desired one. In this paper, the average size of an index organized as a pruned trie is analyzed. The file is assumed to be sorted on all attributes. Attribute values are assumed to be uniformly distributed over all possible character strings of a specified length. The size of the index required for a pruned trie is determined and is shown to be less than that required for a B-tree.

The assumptions made in the analysis are clearly unrealistic. While simplifying assumptions are often made in order to analyze an algorithm, the impact of those assumptions should be considered. Unfortunately, this issue is not discussed in this paper.