Hash Indexes: What they are and their limitations

Hash indexes are a type of database index used to speed up lookups by key.

They are commonly implemented using a hash table, which uses hash function to map keys to locations where their corresponding values or references can be found.

I wrote another blog going into more depth about hash maps and how they work. You can check it out here.

How hash indexes work?

Imagine you have a database containing users and their email addresses. If we want to find a user by their email, we could scan every record in the database until we find a match.

That would take O(n) time which is very slow for lookups, especially as our dataset grows.

Instead, we can use a hash index.

A hash function takes a key, such as an email address, and converts it into a hash value. This value helps us locate the corresponding entry in the hash table without scanning every record.

This gives hash indexes O(1) average-case lookup time (assuming a well-behaved hash function and a reasonable number of collisions, more on that on the hash map blog) which is pretty fast.

The problem with memory

Like all good things there's a catch. Hash indexes are typically maintained in memory because hash tables rely on fast access to their entries. If the hash table was stored in disk, they would distribute their keys in different areas of disk making it very hard to access different parts of the disk fast. Keeping the hash table in RAM allows lookups to happen much faster than repeatedly accessing random locations on disk.

However, RAM is expensive compared to disk, which makes it limited.

If we have a massive database, keeping the entire hash index in memory can become a problem. The index itself might be too large to fit in RAM, even if the actual data lives on disk. So hash indexes are better suited for smaller datasets that require frequent and fast access.

But RAM is volatile

If our server crashes, the in-memory hash table disappears. If that hash table was the only place where our index existed, we'd lose the index and have to rebuild it.

One solution is to use a write ahead log, or WAL.

Think of a WAL as a log of changes that have been made, or are about to be applied, to our data structure.

Whenever we perform a write or update, we first append the corresponding change to the log on disk before applying it to the in-memory index. This is the basic idea behind write ahead logging.

We store the log on disk because we need the changes to survive a crash. If the server goes down, we can use the log to recover the changes that were recorded, rather than losing everything when RAM is cleared.

Another neat thing about this is that WALs are written sequentially.

Instead of jumping around the disk to update lots of different locations, we can append changes to the end of a log. Sequential writes are generally much more efficient than random disk writes, especially on traditional hard drives.

The WAL doesn't magically make every operation faster though. It provides durability and supports recovery, while sequential appends can also make the write path more efficient.

No range queries

Hash indexes have one more major limitation: they don't support efficient range queries.

A range query is a query that retrieves records whose keys fall between two values.

For example:

SELECT *
FROM users
WHERE age BETWEEN 18 AND 25;

A hash function distributes keys according to their hash values, not their original order.

This means that even if the original keys are ordered, their corresponding hash values won't preserve that ordering.

If we want to find all keys within a particular range, we generally have to examine the entries and check which ones match. That can take O(n) time in a basic hash-table implementation.

This is where other index structures, such as B-tree indexes perform better.

So, basically

• Hash indexes are useful when we need fast exact-key, hash tables provide O(1) average-case reads and writes.
• Hashing doesn't preserve key order and are not good for ranged queries.
• Hash tables can consume a lot of RAM, so its better for smaller datasets.
• A write-ahead log helps recover changes after a crash.

Ultimately, choosing an index comes down to understanding the kind of queries your application needs to perform and the trade-offs you're willing to make.

That's it for my learnings on this topic, please correct me if I'm wrong