If 'select min(keycolumn) from footable' is relatively stable and keys are created ascending (databases do this, right?), a resizing slice (with 0-min() elided from the bottom) seems like a good alternative to a hashing structure.

If the key-space is relatively sparse, this will waste more memory than the hash, of course.