It seems like storing the refs in a trie would be a relatively easy change, though backwards compatibility would be annoying.

Alternatively the names of the refs could be sorted.