Hash Indexing

In certain situations, we require an index to efficiently search for information, but using a B-tree index can be overly complex and redundant. In such cases, a hash index can be a more suitable alternative.

A hash index is a type of database index that uses a hash function to map indexed values to locations in a hash table.
In this index type, the target column values are hashed, meaning they are transformed into a fixed-size value or hash code, which is then used as the index to retrieve data rows.

How does it work?

In a hash index, the hashing process involves transforming an index key value into a hash code using a hash function. This hash code is then used to determine the location, or bucket, where the corresponding data is stored in the index.

You can find more information about hashing in the Algorithms and Data Structures Overview course.

Let's consider a hash index for a library catalog system where each book title is indexed by its ISBN (International Standard Book Number).

In this example, we utilize a hash function to convert the ISBN of a book into a hexadecimal hash code, such as 0x7FA4, using a series of mathematical operations on the ISBN digits.
This hash code serves as a unique identifier, determining the slot within the hash table where there is a link to the corresponding line in the table, containing all the information about that particular book.

Key features

1. Fast Lookup: Hash indexes provide fast lookups for equality comparisons. When searching for a specific value, PostgreSQL calculates the hash of the value and then directly accesses the corresponding location in the index, making retrieval very efficient;
2. Limited Operator Support: Unlike B-tree indexes, hash indexes support only equality comparisons (=), not range queries (<, >, <=, >=) or sorting. This limitation makes hash indexes less versatile compared to B-tree indexes;
3. Faster for Some Use Cases: In scenarios where the workload involves a high volume of equality lookups, such as primary key or unique constraint enforcement, hash indexes can outperform B-tree indexes. However, their performance advantage diminishes for range queries or data that doesn't fit well with the hashing algorithm.

Implementation

We can implement hash index in SQL using the following statement:

As a result, values of the column_name1, column_name2,... will be hashed and the hash table will be created. This will enable faster retrieval of the required data rows.