Index Access Methods

PostgreSQL implements several index access methods. An access method is a generic algorithm with a clean API that can be implemented for compatible data types. Each algorithm is well adapted to some use cases, which is why it’s interesting to maintain several access methods.

The PostgreSQL documentation covers index types in the “Indexes” chapter on the official documentation of PostgreSQL and tells us the following:

PostgreSQL provides several index types: B-Tree, Hash, GiST, SP-GiST, GIN, and BRIN. Each index type uses a different algorithm that is best suited to different types of queries. By default, the CREATE INDEX command creates B-Tree indexes which fit the most common situations.

Each index access method has been designed to solve a specific use case.

Balanced tree (B-Tree)

Balanced indexes are the most commonly used by a long shot because they are very efficient and provide an algorithm that applies to most cases. PostgreSQL implementation of the B-Tree index support is best in class and has been optimized to handle concurrent read and write operations.

We can read more about the PostgreSQL B-Tree algorithm and its theoretical background in the source code file: src/backend/access/nbtree/README.

Generalized search tree (GiST)

The GiST method implements a more general algorithm that again comes from research activities. The GiST Indexing Project from the University of California Berkeley is described in the following terms:

The GiST project studies the engineering and mathematics behind content-based indexing for massive amounts of complex content. Its implementation in PostgreSQL allows support for two-dimensional data types such as the geometry point or the ranges data types. Those data types don’t support a total order and, as a consequence, can’t be indexed properly in a B-Tree index.

Space-partitioned gist (SP-GiST)

SP-GiST indexes are the only PostgreSQL index access method implementation that supports nonbalanced disk-based data structures, such as quadtrees, k-d trees, and radix trees (tries). This is useful when we want to index two-dimensional data with very different densities.

Generalized inverted index (GIN)

When the items to be indexed are composite values, and the queries to be handled by the index need to search for element values that appear within the composite items, GIN is designed to handle the situation. For example, the items could be documents, and the queries could be searches for documents containing specific words.

GIN indexes are “inverted indexes,” which are appropriate for data values that contain multiple component values, such as arrays. An inverted index contains a separate entry for each component value. Such an index can efficiently handle queries that test for the presence of specific component values.

The GIN access method is the foundation for the PostgreSQL Full-Text Search support.

Block range indexes (BRIN)

BRIN indexes (a shorthand for block range indexes) store summaries about the values stored in consecutive physical block ranges of a table. Like GiST, SP-GiST, and GIN, BRIN can support many different indexing strategies, and the particular operators with which a BRIN index can be used vary depending on the indexing strategy. For data types that have a linear sort order, the indexed data corresponds to the minimum and maximum values of the values in the column for each block range.

Hash

Hash indexes can only handle simple equality comparisons. The query planner will consider using a hash index whenever an indexed column is involved in a comparison using the = operator.

Never use a hash index in PostgreSQL before version 10. In PostgreSQL 10 onward, hash indexes are crash-safe and may be used.

Bloom filters

A Bloom filter is a space-efficient data structure that is used to test whether an element is a member of a set. In the case of an index access method, it allows fast exclusion of nonmatching tuples via signatures whose size is determined at index creation.

This type of index is most useful when a table has many attributes and queries test arbitrary combinations of them. A traditional B-Tree index is faster than a Bloom index, but it can require many B-Tree indexes to support all possible queries where one needs only a single Bloom index.

Note: However, Bloom indexes only support equality queries, whereas B-Tree indexes can also perform inequality and range searches.

The Bloom filter index is implemented as a PostgreSQL extension starting in PostgreSQL 9.6, and so to be able to use this access method, it’s necessary to first create the bloom extension using the command create extension bloom.

Both Bloom indexes and BRIN indexes are mostly useful when covering multiple columns. In the case of Bloom indexes, they are useful when the queries themselves are referencing most or all of those columns in the equality comparisons.