Have you ever heard of Judy?
In a nutshell, Judy implements a sparse dynamic array. Consequently, it consumes memory only when it is populated. In fact, a Judy tree is more efficient on memory than any other tree.
This module is a Perl portion of Judy. You should notice its performance.