The trie doesn't require a limited set of words. Counts can easily be used or not. If you were to write the entire path to disk, you'd be optimizing the time co

The trie doesn't require a limited set of words. Counts can easily be used or not. If you were to write the entire path to disk, you'd be optimizing the time complexity while probably hammering the filesystem (and greatly increasing the (externalized/ignored) FS portion of the time complexity). If you do a left-biased traversal/generation of a trie in tiers, you get a merge-like sort and reduce the space cost of a normally distributed set of data. Your merge files should be offsets of the original file. Divide the offsets into an appropriate number of divisions (one for each of the characters in the set). Using the offsets, divided into sets of N starting characters, you'd get 256 (for first byte) or 64k (for two bytes) (sub)sets. You can continue the pattern, if appropriate, or just do the merge sort. Your first-pass cost is the generation of the first level sets, and then your additional costs are limited to the division of each set as you reach them. Create sets by the next character (an additional 256 files), and keep moving down. You're creating a tree structure on disk and creating/traversing it in tiers. Your worst case for this is a common prefix. In the most basic implementation, you'd end up with NM comparisons, in NM^2 space, across M files (N:words, M:prefix length). A reasonable implementation would delete the parent file, so you should stay near the 2NM space for disk. Your in-memory cost is almost zero though, since you're relying on M in the worst implementation and '1' in the best.