Any database engine worth its salt will use some kind of balanced tree structure (canonically, a B-tree or variant thereof, but since I'm on a project that isn'

Any database engine worth its salt will use some kind of balanced tree structure (canonically, a B-tree or variant thereof, but since I'm on a project that isn't using a B-tree, I'll be a little less restrictive). This is primarily, as said above, because trees speed up range queries, not just point queries (hash tables only improve point query speed), but also because you don't need to rehash everything whenever your data set grows beyond some size. Balanced trees get the nice property that, though their point queries are O(log n), everything else is O(log n) as well (updates, inserts, range queries, deletes), while hash tables suffer the penalty of being amortized (fast for almost everyone means slow for some). Besides, log is a very powerful function. Even if your database is extremely large (a million elements, say), the log factor is only going to give you about twenty seeks. Another problem with hash tables is that if your keys are large (varchars), you have to hash the entire string, or deal with more collisions. A reasonable balanced tree index on varchars just needs to call strncmp(3), which can terminate much sooner than a hash function. Of course, it's unlikely that your index, if it's large enough for you to care, is going to be CPU-bound, but it's important to remember that the constant inside the O(1) (amortized) hash table is probably going to be pretty large in this case.