What an index actually is: B-trees, hashes and GIN

An index is a data structure. Which one it is determines what it can do, and every rule in the next lesson — why order matters, why LIKE '%x' cannot use an index, why you cannot index email and get case-insensitive lookups — falls straight out of the structure.

So: one lesson on the structures. It is the cheapest investment in this module.

The B-tree, which is 95% of indexes

CREATE INDEX with no options gives you a B-tree. It is the default because it is good at almost everything.

A B-tree is a sorted, balanced, shallow tree. Here is a real one — the primary key of a 500,000-row table:

level 2:       1 root page,      5 children
level 1:       5 internal pages, ~274 children each
level 0:    1367 leaf pages,     ~367 entries each

Check the arithmetic: 5 × 274 = 1370 leaf pages, and 1367 × 367 = 501,689 entries. It fits.

The tree is three levels deep. To find any one of 500,000 rows: read the root, read one internal page, read one leaf page. Three page reads, then one more to fetch the row.

That is the whole trick, and the reason is fanout. Each page is 8 KB, and a bigint key plus a row pointer is about 16 bytes, so a few hundred children fit in one page. Depth grows as log base 300:

A B-tree stays shallow at any size you will ever have. A thousand-fold increase in data costs you one extra page read. This is why databases scale at all.

What the leaves hold, and one surprise

Leaf entries are (key, pointer-to-row), in sorted order, and the leaves are linked to their neighbours. Which gives you:

• Equality — WHERE id = 42. Descend and read.
• Ranges — WHERE id BETWEEN 100 AND 200. Descend to 100, walk the leaves.
• Sorted output — ORDER BY id with no sort step at all.
• min and max — read the first or last leaf.
• Prefix matching — WHERE tag LIKE 'tag17%', because 'tag17…' is a contiguous range. LIKE '%tag17' is not a range anywhere in the sort order, so no index can help — that is not a limitation of PostgreSQL, it is what sorted means.

Except that prefix matching has a trap, and I walked into it while writing this lesson. On a database created with a normal locale — mine reports en_US.utf8 — an ordinary text B-tree will not be used for LIKE 'tag17%' at all:

 Gather
   Workers Planned: 2
   ->  Parallel Seq Scan on big
         Filter: (tag ~~ 'tag17%'::text)

The reason: a locale-aware collation does not sort byte by byte, so LIKE prefixes are not contiguous in the index's order. You need an index built with the pattern operator class:

CREATE INDEX idx_big_tag_pat ON big (tag text_pattern_ops);

 Bitmap Heap Scan on big
   ->  Bitmap Index Scan on idx_big_tag_pat
         Index Cond: ((tag ~>=~ 'tag17'::text) AND (tag ~<~ 'tag18'::text))

Look at what the planner did with it: it rewrote the LIKE into >= 'tag17' AND < 'tag18' — a genuine range, which is exactly the argument above. text_pattern_ops sorts by byte value, which is what makes the rewrite valid.

The cost is that this index is useless for ordinary comparisons and ORDER BY, because its order is not the collation's order. If you need both, you need both indexes. (A database created with LC_COLLATE=C sorts by byte anyway, so there the default index does prefix matching — which is why this trap is invisible to some people and baffling to others.)

The surprise: the index on member_id in the same table, which has 1000 distinct values across 500,000 rows, averages 10 entries per leaf page rather than 367. It has not gone wrong — PostgreSQL deduplicates repeated keys, storing each value once with a posting list of all its row pointers. One "entry" holds hundreds of pointers. That is why the index is 3.5 MB where the unique primary key is 11 MB, and it is a free win on any low-cardinality column.

Where it goes wrong: writes

Every insert must be placed in its correct sorted position. If the page is full, it splits — half the entries move to a new page, and the parent gets a new entry, possibly splitting in turn.

This is why indexes cost writes, and it is not small. On that same table, inserting 200,000 rows:

About 8× slower. Every index you add is a tax on every write.

An id from a sequence always appends to the right-hand edge, which is the cheap case. A uuid v4 index inserts at random positions all over the tree, splitting pages everywhere and touching far more of the index — which is the real argument against random UUID primary keys, and why UUIDv7, which is time-ordered, exists. PostgreSQL 18 has uuidv7() built in.

GIN, for "is this inside that"

A B-tree indexes a value. GIN indexes the things inside a value — the words in a document, the keys in a JSON object, the elements of an array.

It is an inverted index: for each element, a sorted list of the rows containing it. Exactly like the index at the back of a book.

CREATE INDEX idx_books_search ON books USING gin (to_tsvector('english', title));
SELECT * FROM books WHERE to_tsvector('english', title) @@ to_tsquery('english', 'monsoon');

CREATE INDEX idx_events_data ON events USING gin (data jsonb_path_ops);
SELECT * FROM events WHERE data @> '{"status": "failed"}';

CREATE INDEX idx_books_tags ON books USING gin (tags);
SELECT * FROM books WHERE tags @> ARRAY['fiction'];

Use GIN for full-text search, jsonb containment, and array containment. It is what makes the "you do not need Elasticsearch yet" advice in module 11 true.

The costs: GIN is slow to update — each new row touches one posting list per element — and it cannot do ranges or ordering. The pending-list mechanism (fastupdate) batches updates to soften the write cost, at the price of slower reads until it is flushed.

jsonb_path_ops is worth knowing: smaller and faster than the default, but it only supports @>-style containment, not "does this key exist".

GiST, for overlap

GiST handles things where "equal" and "less than" are the wrong questions — geometry, ranges, nearest-neighbour.

CREATE INDEX idx_bookings_period ON bookings USING gist (period);
SELECT * FROM bookings WHERE period && tstzrange('2026-09-27', '2026-09-28');

This is the index behind the exclusion constraint from module 4:

CREATE EXTENSION btree_gist;          -- required, and easy to forget

ALTER TABLE bookings ADD CONSTRAINT no_double_booking
  EXCLUDE USING gist (room_id WITH =, period WITH &&);

Without that extension you get:

ERROR:  data type integer has no default operator class for access method "gist"

GiST has no built-in support for plain equality on an integer; btree_gist adds it. This is a two-minute mystery the first time, so it is worth recognising.

With it in place, the second overlapping insert fails:

ERROR:  conflicting key value violates exclusion constraint "bookings_room_id_period_excl"
DETAIL:  Key (room_id, period)=(7, ["2026-09-27 12:00:00+00","2026-09-29 00:00:00+00"))
         conflicts with existing key (room_id, period)=(7, ["2026-09-27 00:00:00+00","2026-09-28 00:00:00+00")).

"No two bookings for the same room may overlap in time", enforced by the database. A B-tree cannot express that, because overlap is not an ordering.

GiST is also what PostGIS uses for maps, and it does nearest-neighbour ordering (ORDER BY location <-> point(...)) using the index — "the ten nearest shops", which a B-tree cannot do at all.

Note that GiST is lossy: it can return false positives, which the executor rechecks. That is why a GiST plan shows a recheck step.

The two small ones

BRIN — block range index. It stores only the minimum and maximum value per group of pages. Absurdly small (kilobytes for a table of gigabytes) and only useful when the column correlates with physical row order — an append-only created_at on a log table being the perfect case. On shuffled data it is useless, because every block range covers the whole range of values.

Hash — equality only, no ranges, no ordering. Slightly smaller and faster than a B-tree for long keys where you only ever do =. It became crash-safe in PostgreSQL 10, so it is usable, but the B-tree does equality perfectly well and also does everything else. Reach for hash rarely.

Choosing

Check your work

The default index type. B-tree.

Three properties of a B-tree. Sorted, balanced, shallow.

How deep a B-tree on 500,000 rows is. Three levels.

Why it stays shallow. Fanout — a few hundred children per 8 KB page, so depth grows as log base 300.

Five things a B-tree can do. Equality, ranges, sorted output, min/max, prefix matching.

Why LIKE '%x' cannot use an index. A suffix is not a contiguous range in sort order.

What a prefix LIKE needs under a locale collation. An index built with text_pattern_ops, because locale order is not byte order. Its cost: useless for ORDER BY.

What an exclusion constraint on an integer column needs. The btree_gist extension.

What deduplication does. Stores a repeated key once with a posting list of row pointers, shrinking low-cardinality indexes.

Why writes get slower. Page splits — measured at about 8× for four indexes.

Why random UUID keys are worse than sequential ids. They insert all over the tree instead of appending at the right edge; UUIDv7 fixes it by being time-ordered.

What GIN indexes. The elements inside a value: words, jsonb keys, array items.

GIN's two costs. Slow updates, and no ranges or ordering.

What GiST is for. Overlap, geometry and nearest-neighbour — and it is the index behind exclusion constraints.

When BRIN works. When the column correlates with physical row order, such as an append-only timestamp.

Why hash is rarely worth it. A B-tree does equality well and everything else too.

Practice

1. Create a B-tree on a 100,000-row table and read its height with SELECT * FROM bt_metap('your_index') after CREATE EXTENSION pageinspect.
2. Work out the height for a billion rows at a fanout of 300.
3. Use one index for WHERE, ORDER BY and max() on the same column and check each plan.
4. Try LIKE 'abc%' and LIKE '%abc' with an ordinary index and compare the plans. Then add a text_pattern_ops index and try the prefix one again.
5. Check your database's collation with SELECT datcollate FROM pg_database WHERE datname = current_database(). Predict from it whether the default index will do prefix matching.
6. Compare pg_relation_size for an index on a unique column and one on a column with ten distinct values. Explain the difference.
7. Time 100,000 inserts with no indexes, then with four.
8. Insert 100,000 rows keyed by gen_random_uuid() and by a sequence. Compare the times and the index sizes.
9. Build a GIN index on to_tsvector('english', title) and search for a word.
10. Build a GIN index on a jsonb column and query with @>. Compare jsonb_path_ops with the default for size.
11. Time inserts into a table with a GIN index and one without.
12. Build a tstzrange column with a GiST index and query with &&.
13. Add an exclusion constraint preventing overlapping bookings without btree_gist first, read the error, then add the extension and try to violate the constraint.
14. Build a BRIN index on an append-only timestamp column. Compare its size with a B-tree's, then shuffle the table with CLUSTER on another column and re-check whether it is used.
15. Explain to somebody why a thousand-fold increase in rows costs one extra page read.

Official documentation

• PostgreSQL — Index types — The overview: which operators each type supports.
• PostgreSQL — B-tree indexes — Including the deduplication section.
• PostgreSQL — GIN indexes — Implementation, fastupdate, and the operator classes.
• PostgreSQL — GiST indexes — And its nearest-neighbour support.
• PostgreSQL — BRIN indexes — When correlation makes it work.
• PostgreSQL — Constraints: exclusion — The GiST-backed constraint.
• PostgreSQL — Operator classes — text_pattern_ops and why a locale collation needs it.
• Use the Index, Luke — Not official. The best free explanation of B-tree indexing anywhere, and worth reading end to end.

Next: creating them, and the rules that follow from the structure.