The idea: one table, five index types
An index in PostgreSQL is a separate file that points into the table (the heap). Each pointer is a TID, (block, line pointer): which 8 KB heap page, and which slot on it. PostgreSQL has several index access methods. They differ in what they store for each row, which operators they can answer, and how big they get. The page builds one index at a time on the same 16-row table and runs a query that suits it.
CREATE TABLE places (id int, city text, tags text[], pos point, day int); -- 16 rows in 4 heap blocks; day = id, and rows were inserted in day order
Every lookup has the same shape: read some index pages, get TIDs (or block numbers), then read those heap blocks. The heap step is never skipped: the index does not know which row versions are visible to your transaction (MVCC), so the executor checks each row in the heap. The size panel shows rough sizes for a 1-million-row version of the same table.
B-tree and deduplication
The default index. Keys are kept in sorted order, so a B-tree answers =, <, BETWEEN, ORDER BY and LIKE 'abc%'. Since PostgreSQL 13, equal keys are stored once with a posting list: a sorted array of all their heap TIDs. With 4 cities and 16 rows the index holds 4 tuples, which fit on one page. With deduplicate_items = off it holds 16 tuples on 3 pages, and the heap TID becomes part of the key, so the Oslo tuples are split across two leaves (Demo: B-tree, posting lists vs no dedup). On many duplicates this makes the index about 3 times smaller. The tree itself (splits, the root, the levels) is the subject of B+ Tree and Database Index.
Hash
A hash index stores a 4-byte hash code and a TID per row, in bucket code mod number_of_buckets. It does not store the key, so different keys can share a bucket (Oslo and Lima here) and the heap row is always rechecked. It only answers =: hash order is not key order, so a range query cannot use it and the planner falls back to a Seq Scan (Demo: Hash, equality yes, range no). Hash indexes are crash-safe since PostgreSQL 10, and they can be smaller than a B-tree on long unique keys (a URL is reduced to 4 bytes). On a column with few distinct values they are a poor choice: every row with the same key lands in the same bucket and its chain of overflow pages.
GIN and the pending list
GIN (Generalized Inverted Index) is for values that contain several keys: array elements, the words of a tsvector for full-text search, the keys and values of a jsonb document. It is an inverted index: a B-tree of keys (the entry tree), each with a posting list of the rows that contain it; a long list becomes its own tree (a posting tree). tags @> '{red,blue}' looks up both keys and keeps the TIDs that are in both lists. GIN only produces a bitmap, never rows in order, so the plan is always a Bitmap Heap Scan.
Inserting one row means updating one posting list per key, which is slow. With fastupdate = on (the default) new entries are appended to an unsorted pending list instead. Every search must read the whole pending list, so it is merged into the entry tree in bulk by VACUUM, autovacuum's analyze, gin_clean_pending_list(), or when it grows past gin_pending_list_limit (4 MB) (Demo: GIN, contains and the pending list).
GiST and overlapping boxes
GiST (Generalized Search Tree) is a balanced tree whose inner entries are predicates that cover everything below them. For geometry (point, box, PostGIS) and ranges (tsrange, int4range) the predicate is a bounding box or bounding range. It answers "overlaps", "contained in", "nearest to" (ORDER BY pos <-> point) and powers exclusion constraints. Unlike a B-tree, sibling boxes may overlap. A search must then go down every child whose box meets the query box, and may read a leaf that has no match (Demo: GiST, overlapping bounding boxes). How well the inserts split the boxes decides how fast the index is.
BRIN and correlation
BRIN (Block Range INdex) stores one small summary per range of heap blocks: for minmax, the smallest and largest value. A range is pages_per_range = 128 blocks by default (1 MB of table); the page scales it down to one block per range. A table of 100 MB needs about 100 summaries, which fit on one page: the index is a few tens of kilobytes. The price: it is lossy. A matching range is read whole and every row in it is rechecked. It only helps when the column follows the physical order of the table, like an append-only created_at or id (Demo: BRIN, day order vs random order).
Which one to pick
| Index | Stores | Good for | Size (1M rows here) |
|---|---|---|---|
| B-tree | sorted keys + TIDs (posting lists) | =, ranges, ORDER BY, unique constraints | ≈ 7 MB (22 MB without dedup) |
| Hash | 4-byte hash code + TID | = only, on long values | ≈ 20 MB |
| GIN | element → posting list | arrays, jsonb, full-text search | ≈ 2 MB |
| GiST | bounding boxes / ranges | geometry, ranges, nearest neighbour, exclusion constraints | ≈ 40 MB |
| BRIN | min/max per block range | huge tables whose column follows the insert order | 24 kB |
The sizes are rough, for this table's shape; measure your own with pg_relation_size('index_name'). Which index the planner actually uses for a query is a cost decision: see Query Planner. For the rest of the engine (heap, WAL, MVCC) see PostgreSQL and PostgreSQL heap page.
GIN is an inverted index; see how posting lists are built and intersected for AND queries.
What the page leaves out
Metapages, the BRIN revmap and GIN posting trees are not drawn, and toy pages hold 8 tuples instead of hundreds. Real lookups by B-tree, hash and GiST often use a bitmap scan too, chosen by cost. Not shown: SP-GiST (space-partitioned trees: quadtrees, k-d trees, radix tries), Bloom indexes (contrib), multicolumn, partial and expression indexes, covering indexes (INCLUDE), index-only scans with the visibility map, B-tree bottom-up deletion, and BRIN's bloom and minmax-multi operator classes.