Check out the docs for Berkeley DB, (perldoc DB_File). Aside from being one of the faster DBM formats, it has support for duplicate keys, and partial key matches. I've only tinkered with this briefly, but it may do what you need.

/\/\averick