Beyond B-tree, where it matters

B-tree answers “equal to”, “greater than”, “between”, and “in this order” on a value the type system can sort. That covers the great majority of production queries, and this lesson is deliberately short on the alternatives, because reaching for an exotic index type when a B-tree would do is a more common mistake than missing one.

Four cases where B-tree genuinely cannot serve.

GIN: searching inside a value

When one row contains many searchable items — array elements, JSON keys, words in a document — B-tree cannot help, because it indexes the value as a whole.

CREATE INDEX ON documents USING gin (tags);              -- array containment
CREATE INDEX ON events USING gin (payload);              -- jsonb ? and @>
CREATE INDEX ON events USING gin (payload jsonb_path_ops);  -- @> only, smaller
CREATE INDEX ON articles USING gin (to_tsvector('english', body));

jsonb_path_ops supports only the containment operator @> but produces a substantially smaller index. If your queries only use @>, it is the better choice.

$ psql -U postgres -c "EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF, SUMMARY ON) SELECT count(*) FROM ts WHERE tags @> '{\"n\": 5}'"

 ->  Parallel Bitmap Heap Scan on ts (actual rows=128205.33 loops=3)
     Heap Blocks: exact=19096
     Buffers: shared hit=1357 read=55616 written=8404

GIN identified the rows correctly and the plan still read most of the table, because 7.7% selectivity on a 435 MB table is simply too many rows for an index to save much. An index cannot rescue a query that genuinely needs most of the data.

GiST: overlap, containment and nearest-neighbour

GiST is a framework rather than one algorithm. The operational cases:

-- exclusion constraint: no two bookings for one room may overlap
CREATE EXTENSION IF NOT EXISTS btree_gist;
ALTER TABLE bookings ADD CONSTRAINT no_double_booking
  EXCLUDE USING gist (room_id WITH =, during WITH &&);

-- geometric and geographic, via PostGIS
CREATE INDEX ON places USING gist (location);

-- nearest-neighbour ordering, which no B-tree can do
SELECT * FROM places ORDER BY location <-> point(51.5, -0.12) LIMIT 10;

The exclusion constraint is the case worth knowing even if you never touch spatial data. It enforces “these must not overlap” at the database level, which is the correct answer to the write-skew problem from lesson VII-04 whenever the rule can be expressed this way — no isolation level and no retry logic required.

BRIN: enormous, naturally ordered tables

BRIN stores a summary — typically min and max — for each range of pages, by default 128 pages. It does not identify rows; it identifies page ranges that might contain them.

$ psql -U postgres -c "SELECT indexrelname, pg_size_pretty(pg_relation_size(indexrelid)) AS size FROM pg_stat_user_indexes WHERE relname='ts' ORDER BY pg_relation_size(indexrelid) DESC"

 indexrelname |  size
--------------+--------
ts_at_btree  | 107 MB
ts_pkey      | 107 MB
ts_tags_gin  | 28 MB
ts_at_brin   | 32 kB

-- heap: 435 MB

32 kB against 107 MB. A factor of about 3,400 for the same column.

$ psql -U postgres -c "EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF, SUMMARY ON) SELECT count(*) FROM ts WHERE at BETWEEN now()-interval '80 minutes' AND now()-interval '20 minutes'"

-- B-tree
->  Index Only Scan using ts_at_btree on ts (actual rows=3600.00 loops=1)
     Buffers: shared hit=3 read=10
Execution Time: 0.204 ms

-- BRIN
->  Bitmap Heap Scan on ts (actual rows=3600.00 loops=1)
     Recheck Cond: ((at >= …) AND (at <= …))
     Rows Removed by Index Recheck: 2140
     Heap Blocks: lossy=64
     Buffers: shared hit=73
     ->  Bitmap Index Scan on ts_at_brin (actual rows=640.00 loops=1)
Execution Time: 0.475 ms

73 buffers against 13, and 0.475 ms against 0.204 ms — about 2.3 times slower — for one three-thousandth of the storage.

Rows Removed by Index Recheck: 2140 and Heap Blocks: lossy=64 are the mechanism made visible: BRIN returned candidate page ranges, the heap was rechecked, and 2,140 rows were read and discarded.

Hash: equality only

CREATE INDEX ON sessions USING hash (session_token);

Serves = and nothing else. No ranges, no ordering, no multi-column form, and no unique constraints.

It became crash-safe and WAL-logged in PostgreSQL 10, so the old advice never to use it is obsolete. It can be smaller than a B-tree on long keys, because it stores a 32-bit hash rather than the value.

It remains a narrow tool. B-tree serves equality perfectly well and serves everything else too, so hash pays only where the keys are long, the workload is equality-only, and the size difference has been measured and matters.

Choosing

The default answer is B-tree. Reach past it when the query shape requires it or when a measurement — not an expectation — says otherwise.

What to take from this

• B-tree is the default and usually the answer. The alternatives serve query shapes it cannot.
• GIN for searching inside composite values; watch the pending list and fastupdate if latency is erratic.
• GiST for overlap, nearest-neighbour and exclusion constraints — the last of which solves a class of concurrency problem outright.
• BRIN needs physical correlation above about 0.9 and fails silently without it. Measured: 32 kB against 107 MB, 2.3× slower.
• Hash is crash-safe since 10 and still narrow.
• An index unused for no visible reason is often an operator class mismatch, text_pattern_ops being the classic case.

Cross-course references

• Observability for Production Sysadmins — Part LIX (Database observability) covers measuring whether a specialised index type is actually being chosen, rather than assuming the planner agrees with the decision to build it.
• Linux for Production Sysadmins — Part XLI (Storage Performance) covers the build cost, which for these types is materially higher than for a B-tree.

Quiz