This being Perl, you're not going to get much in the way of structure efficiency with or without hashes, and you haven't supplied us with some crucial information:

1) How many records does the database table have?
2) What's the average size of each field?
3) What's the ratio of updates to searches?
4) Do you need to support multiple simultaneous searches? If so, up to how many?
5) What are your memory limits?