That is a good point. However as soon as the indexes are not entirely held in memory you get a performance dropoff. And the relational database itself already is a performance decrease over a straight hash.
TANSTAAFL. Pick the trade-off which is most appropriate for what you're doing.