Both a database and a hash will do the trick. Which one is better for your application depends on a lot of things. Up to a certain number of keys, a hash will be faster. But if the number of keys grows, Perl will use more and more memory, and at a certain point, it will start trashing, and eventually run out of memory. Somewhere along the way, it's going to be more efficient to use a database, specially if the database is on another box. But where that point is depends on the number of keys, the number of inserts, the number of queries, and the amount of memory your program has available.
It's something only you can test.