SQL 109 🛢️ Specialized Index Structures: GiST, GIN, BRIN, and R-Trees - KandZ

⏱️ Estimated read: 14 min | |

A B-tree index answers one question well: does this value fall within this ordered range? It is the correct index for equality and range predicates on scalar columns, and it is the default because most queries ask exactly that question. But a query that asks “which documents contain the word ‘index'” or “which geometric shapes overlap this rectangle” or “which rows in this billion-row log table fall within this date range” is not asking a range question. A B-tree can answer it, but only by scanning more entries than it should. The specialized index structures exist for the queries where the shape of the predicate is not a simple ordered comparison. GiST is a framework for geometric and range types, GIN is an inverted index for composite values, and BRIN is a block-range summarizer for physically correlated data. The R-tree is the historical ancestor of GiST, and it is no longer a separate index type in PostgreSQL.

Key point: GiST is an extensible framework for geometric, range, and nearest-neighbor queries. GIN is an inverted index for arrays, JSONB, and full-text search. BRIN is a tiny block-range summary for very large, physically correlated tables. The R-tree is not a distinct index type in current PostgreSQL; its functionality is subsumed by GiST.

Why B-trees are not enough

The composite-value problem. A B-tree index on an array column indexes the entire array as a single value. A query that asks “which rows contain the element ‘python'” cannot use the B-tree, because the B-tree compares whole arrays. The GIN index solves this by inverting the relationship: it stores one entry per element, and each entry points to the rows that contain that element . A query for a single element becomes a lookup in the inverted index, which is exactly what the predicate needs.

The geometric problem. A B-tree on a point column can order points by x-coordinate, but a query that asks “which points fall inside this rectangle” needs to filter on both x and y. A B-tree can filter on x, but it cannot filter on y without a separate index. GiST solves this by indexing the bounding boxes of the geometric objects, so a query can prune the search space by excluding the boxes that do not overlap the query rectangle . The GiST index is a balanced tree of bounding boxes, and the search descends only into the boxes that can contain a match.

The huge-table problem. A B-tree index on a billion-row table is large, and maintaining it on every insert is expensive. If the table is append-only and the indexed column is correlated with the physical order—a timestamp column in a log table, for example—the B-tree is doing more work than the query needs. BRIN solves this by storing a single summary per block range—typically the minimum and maximum value—so the index is orders of magnitude smaller than a B-tree, and the query skips the block ranges whose summary cannot match .

The extensibility problem. The number of data types and query operators is unbounded. A new type—a custom geometric type, a range type, a full-text search vector—needs an index that understands its operators. GiST and GIN are frameworks, not fixed index types: they accept operator classes that define how the type is indexed and how the operators are evaluated . This is why a single GiST index can support PostGIS geometries, range types, and full-text search with different operator classes.

a. GiST: the generalized search tree

GiST is not a single index structure. It is a template for building balanced trees over arbitrary data types, where the tree’s internal nodes store a “consistent” predicate that summarizes the subtree. For geometric types, the predicate is the bounding box; for range types, it is the range itself; for nearest-neighbor searches, the predicate is a distance function .

The standard distribution includes GiST operator classes for geometric types (points, boxes, polygons) and for range types. A GiST index on a box column supports the overlap operator &&, the contains operator @>, and the nearest-neighbor operator <-> . The nearest-neighbor form is the one that a B-tree cannot express at all:

-- A GiST index on a point column
-- The index supports the <-> distance operator for nearest-neighbor search
CREATE INDEX idx_places_location ON places USING GiST (location);

-- Find the ten places closest to a target point
-- The ORDER BY with <-> is satisfied by the GiST index
-- without a full scan and sort
SELECT name, location
FROM places
ORDER BY location <-> point '(101, 456)'
LIMIT 10;

The btree_gist extension is the bridge between GiST and the scalar types. It provides GiST operator classes that implement B-tree-equivalent behavior for integers, timestamps, text, and other scalar types, with one crucial addition: it supports the <> (not equals) operator and the EXCLUDE constraint . An exclusion constraint is a uniqueness constraint over a range: two rows cannot have overlapping ranges in the same column.

-- The zoo table uses an exclusion constraint
-- A cage can contain only one kind of animal
-- The constraint is enforced by a GiST index
CREATE TABLE zoo (
  cage   INTEGER,
  animal TEXT,
  EXCLUDE USING GiST (cage WITH =, animal WITH <>)
);

-- Insert a zebra into cage 123
INSERT INTO zoo VALUES (123, 'zebra');

-- Insert a lion into the same cage; the constraint rejects it
INSERT INTO zoo VALUES (123, 'lion');
-- ERROR: conflicting key value violates exclusion constraint

The EXCLUDE constraint is not expressible with a B-tree, because a B-tree can enforce equality but not the “not equals within the same group” rule. The GiST index provides the underlying search structure, and the constraint uses it to check for conflicts before inserting .

b. GIN: the inverted index

GIN is an inverted index. It stores one entry per element of a composite value—an array element, a JSONB key-value pair, a full-text lexeme—and each entry points to the rows that contain that element. The internal structure is a B-tree over the keys, with a posting list or posting tree for the row pointers .

-- A GIN index on a JSONB column
-- The index supports the containment operator @> and the key-existence operator ?
CREATE INDEX idx_products_meta ON products USING GIN (metadata);

-- Find products whose metadata contains the key-value pair
SELECT * FROM products WHERE metadata @> '{"color": "blue"}';

-- Find products that have the "stock" key
SELECT * FROM products WHERE metadata ? 'stock';

The containment operator @> is the one that GIN makes fast. Without the GIN index, the query scans every row and evaluates the containment predicate on each. With the GIN index, the query looks up the key-value pair in the inverted index and retrieves only the matching row pointers .

GIN’s weakness is update cost. Inserting one row into an indexed table can cause many insertions into the GIN index, one per extracted key. PostgreSQL mitigates this with a pending list: new entries go into an unsorted list, and the list is merged into the main structure during vacuum or when it exceeds gin_pending_list_limit . The trade-off is that searches must scan the pending list as well as the main index, so a large pending list slows searches. The fastupdate storage parameter can be turned off to disable the pending list when consistent response time matters more than update speed .

The pg_trgm extension is the other common GIN use case. It indexes trigrams—three-character substrings—which makes LIKE '%pattern%' queries indexable. A query for name LIKE '%smith%' cannot use a B-tree, but it can use a GIN index on the trigram operator class .

c. BRIN and the R-tree

BRIN is the index for very large tables where the indexed column is physically correlated with the row order. It stores one summary per block range—typically the minimum and maximum value—and the index is tiny compared to a B-tree . The query scans the index to find the block ranges that can contain matching rows, then reads those ranges and rechecks the rows. The recheck is necessary because the summary is lossy: a block range whose min-max interval overlaps the query range may still contain rows that do not match.

-- A BRIN index on a timestamp column in a log table
-- The pages_per_range parameter controls the summary granularity
CREATE INDEX idx_logs_created ON logs USING BRIN (created_at) WITH (pages_per_range = 128);

-- A range query on the correlated column
-- The BRIN index skips the block ranges that cannot match
SELECT * FROM logs WHERE created_at >= '2026-10-01' AND created_at < '2026-10-02';

The pages_per_range parameter is the trade-off. A smaller value produces a larger index with more precise summaries, which skips more blocks. A larger value produces a smaller index with coarser summaries, which skips fewer blocks. The default is 128 pages per range . The index is most effective when the table is append-only and the indexed column increases monotonically—a timestamp, an auto-increment ID, or a sequence number. If the data is not physically ordered, BRIN provides no benefit because every block range’s summary overlaps the query.

The R-tree is the historical note. PostgreSQL had an R-tree access method in older versions, but it was removed. The GiST index is the generalized successor: it can implement R-tree-like behavior for geometric types, and it is the index that PostGIS and the built-in geometric operator classes use . The R-tree is not a separate USING option in current PostgreSQL; the USING GiST index with a geometric operator class is the equivalent.

Complete Example Session

The following session creates a GiST index for nearest-neighbor search, a GIN index for JSONB containment, and a BRIN index for a timestamp column, then shows the query plans.

-- ============================================
-- PART 1: THE GIST INDEX
-- ============================================
-- The places table has a point column
CREATE TABLE places (id serial, name text, location point);
CREATE INDEX idx_places_location ON places USING GiST (location);

-- The nearest-neighbor query uses the GiST index
EXPLAIN ANALYZE
SELECT name FROM places ORDER BY location <-> point '(101, 456)' LIMIT 10;
-- Index Scan using idx_places_location

-- ============================================
-- PART 2: THE GIN INDEX
-- ============================================
-- The products table has a JSONB column
CREATE TABLE products (id serial, name text, metadata jsonb);
CREATE INDEX idx_products_meta ON products USING GIN (metadata);

-- The containment query uses the GIN index
EXPLAIN ANALYZE
SELECT * FROM products WHERE metadata @> '{"color": "blue"}';
-- Bitmap Index Scan on idx_products_meta

-- ============================================
-- PART 3: THE BRIN INDEX
-- ============================================
-- The logs table is large and append-only
CREATE TABLE logs (id bigserial, created_at timestamptz, message text);
CREATE INDEX idx_logs_created ON logs USING BRIN (created_at) WITH (pages_per_range = 128);

-- The range query uses the BRIN index
EXPLAIN ANALYZE
SELECT * FROM logs WHERE created_at >= '2026-10-01' AND created_at < '2026-10-02';
-- Bitmap Index Scan on idx_logs_created

The three parts cover the GiST, GIN, and BRIN indexes with their respective query plans. What the session demonstrates is that each index type is chosen for a different predicate shape, and the EXPLAIN output shows the index scan that the planner selected.

Quick Reference

Index Type Comparison

Index	Best For	Operators	Size
GiST	Geometry, ranges, nearest-neighbor	`&&`, `@>`, `<->`	Medium
GIN	Arrays, JSONB, full-text	`@>`, `?`, `@@`	Large
BRIN	Huge, correlated tables	`<`, `<=`, `=`, `>=`, `>`	Tiny

When to Use

Query Pattern	Index
`column @> '{...}'` (JSONB)	GIN
`column ? 'key'` (JSONB)	GIN
`array @> ARRAY[...]`	GIN
`tsvector @@ tsquery`	GIN
`geometry && geometry`	GiST
`point <-> point ORDER BY LIMIT`	GiST
`range && range`	GiST
`timestamp > x` on ordered data	BRIN

Maintenance Parameters

Parameter	Index	Effect
`fastupdate`	GIN	Enable/disable pending list
`gin_pending_list_limit`	GIN	Pending list size
`pages_per_range`	BRIN	Summary granularity
`autosummarize`	BRIN	Auto-summarize new ranges

Best Practices

✅ Do This:

-- Use GIN for JSONB containment
CREATE INDEX ON products USING GIN (metadata);

-- Use GiST for nearest-neighbor
CREATE INDEX ON places USING GiST (location);

-- Use BRIN for huge, ordered tables
CREATE INDEX ON logs USING BRIN (created_at);

❌ Don’t Do This:

-- Use a B-tree on a JSONB column for containment
CREATE INDEX ON products (metadata); -- cannot answer @>

-- Use BRIN on unordered data
CREATE INDEX ON random_data USING BRIN (value); -- no correlation

-- Use GIN for a simple equality query
CREATE INDEX ON users USING GIN (email); -- B-tree is better

Common Pitfalls

Pitfall	Why It Happens	Fix
GIN index slow to update	Inverted index inserts per key	Tune `fastupdate` and vacuum
BRIN index not used	Data not physically correlated	Use B-tree
GiST index not used	Operator not in the class	Check the operator class
GIN pending list grows	Autovacuum not running	Tune autovacuum

Real-World Examples

1. JSONB containment

CREATE INDEX ON t USING GIN (j);
SELECT * FROM t WHERE j @> '{"a": 1}';

2. Full-text search

CREATE INDEX ON docs USING GIN (to_tsvector('english', body));

3. Array containment

CREATE INDEX ON t USING GIN (tags);
SELECT * FROM t WHERE tags @> ARRAY['sql'];

4. Geometric overlap

CREATE INDEX ON t USING GiST (geom);
SELECT * FROM t WHERE geom && box '((0,0),(1,1))';

5. Nearest neighbor

CREATE INDEX ON t USING GiST (p);
SELECT * FROM t ORDER BY p <-> point '(1,2)' LIMIT 10;

6. Range exclusion

CREATE TABLE t (r daterange, EXCLUDE USING GiST (r WITH &&));

7. BRIN for logs

CREATE INDEX ON logs USING BRIN (created_at);

8. BRIN pages per range

CREATE INDEX ON logs USING BRIN (created_at) WITH (pages_per_range = 64);

9. Trigram search

CREATE INDEX ON t USING GIN (name gin_trgm_ops);

10. Check index size

SELECT pg_size_pretty(pg_relation_size('idx'));

Visual

GiST Tree

┌──────────────────────────────────────────────┐
│  Root bounding box                           │
│         │                                    │
│    ┌────┴────┐                               │
│    ▼         ▼                               │
│  Box A    Box B                              │
│    │         │                               │
│  ┌─┴─┐     ┌─┴─┐                             │
│  ▼   ▼     ▼   ▼                             │
│  pt  pt    pt  pt                            │
└──────────────────────────────────────────────┘

GIN Inverted Index

┌──────────────────────────────────────────────┐
│  Key "blue" → posting list: rows 1, 4, 9     │
│  Key "red"  → posting list: rows 2, 7        │
│  Key "size" → posting list: rows 1, 2, 4     │
│                                              │
│  Query: metadata @> '{"color":"blue"}'       │
│  → lookup "blue" → rows 1, 4, 9              │
└──────────────────────────────────────────────┘

BRIN Block Ranges

┌──────────────────────────────────────────────┐
│  Pages 0-127: min=2026-01-01 max=2026-01-15  │
│  Pages 128-255: min=2026-01-15 max=2026-02-01│
│  Pages 256-383: min=2026-02-01 max=2026-02-15│
│                                              │
│  Query: created_at >= 2026-01-20             │
│  → skip pages 0-127, scan 128+               │
└──────────────────────────────────────────────┘

Summary

Item	Value
GiST	Extensible tree for geometry, ranges, NN
GIN	Inverted index for arrays, JSONB, FTS
BRIN	Block-range summary for huge tables
R-tree	Not a separate type; subsumed by GiST
GiST operators	`&&`, `@>`, `<->`
GIN operators	`@>`, `?`, `@@`
BRIN parameter	`pages_per_range`
GIN parameter	`fastupdate`

Key takeaways:

GiST is a framework, not a single index. It supports geometric types, range types, and nearest-neighbor searches through operator classes. The btree_gist extension adds exclusion constraints that a B-tree cannot express .
GIN is an inverted index. It stores one entry per element of a composite value, which makes JSONB containment, array membership, and full-text search indexable. The update cost is mitigated by a pending list that is merged during vacuum .
BRIN is for huge, physically correlated tables. It stores a summary per block range, so the index is tiny and the query skips the ranges that cannot match. The pages_per_range parameter controls the summary granularity .
The R-tree is historical. PostgreSQL’s old R-tree access method was removed; GiST is the generalized successor that implements R-tree-like behavior for geometric types .
The index type is determined by the predicate shape. A containment predicate needs GIN. A geometric overlap needs GiST. A range query on correlated data needs BRIN. A simple equality or ordered range needs B-tree .

Remember: The B-tree is the default because most queries ask an ordered-range question. The specialized indexes exist for the queries that ask a different question. GiST answers geometric and nearest-neighbor questions. GIN answers composite-value and inverted-index questions. BRIN answers huge-table, correlated-range questions. The index you choose is determined by the predicate, not by the column type alone.

Was this helpful?

Stop using slow, ad-bloated tool sites! 🤮

🔎 Search “KandZ Tools” on Google to use many professional utilities for free.

KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)

⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free

🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!