Database Indexing Deep Dive
Demo Creator
@seed-creator · muallif
How B-Tree Indexes Work
A B-tree is the default index type and the one you reach for ninety percent of the time. It stores keys in sorted order across a balanced tree of pages. A lookup starts at the root, follows a few pointers down to the leaf that holds the key, and then follows a heap pointer to the actual row. Because the tree stays balanced, that traversal is O(log n) — a lookup in a billion-row table touches only a handful of pages.
Sorted order is what makes a B-tree versatile. The same index that answers an equality lookup also answers range queries (created_at > $1), sorted scans (ORDER BY created_at), and prefix matches on text (LIKE 'term%'). This is why one B-tree often serves several query shapes at once, and why it is almost always the right first index to add.
Sorted order is also its limitation. A B-tree cannot help with a leading wildcard (LIKE '%term'), because the value you are searching for could sit anywhere in the ordering, so there is no subtree to prune. For those queries you need a different index structure entirely.
An index is a bet that you will read this column more often than you write it. Take that bet deliberately.
GIN Indexes for Arrays and Full-Text
A GIN (Generalized Inverted Index) is built for columns that hold many values per row: arrays, jsonb, and the tsvector documents used for full-text search. Instead of one key per row, it stores a posting list — for each element, the set of rows that contain it. That inverted structure is exactly what a B-tree cannot do, and it makes membership queries like tags = ANY($1) or a full-text match fast even across millions of rows.
A GIN index is the difference between full-text search that returns in milliseconds and a sequential scan that reads every document on every keystroke. For a category or tag column stored as text[], it turns an otherwise unindexable "does this array contain X" predicate into an index lookup.
GIN indexes are slower to build and update than B-tree, because a single row touches many posting lists. The fastupdate option buffers changes to soften write cost; for heavy write traffic, plan a periodic reindex to keep them lean.
BRIN Indexes for Sequential Data
A BRIN (Block Range INdex) stores only a min/max summary for each block range of the table rather than an entry per row, which makes it astonishingly small — often a few pages for a table of hundreds of millions of rows. The catch is that it only works when the column value correlates with physical row order.
That correlation is exactly what you get with an append-only timestamp: rows are inserted in time order, so a query for a date range can skip whole block ranges whose summary falls outside the window. For a large events or logs table queried by time, a BRIN index gives most of the benefit of a B-tree at a tiny fraction of the size and write cost. If rows are updated out of order, though, the correlation breaks and BRIN degrades toward a full scan.
Hash and GiST
Two specialized types round out the toolbox. A hash index serves pure equality slightly faster than a B-tree but supports nothing else, so it is rarely worth the loss of range and sort. A GiST index is the extensible one: it powers geometric and geographic queries (PostGIS), nearest-neighbor search, and range-overlap operators — anything where "close to" or "overlaps" matters more than "equals".