Back to All Articles
Databases

PostgreSQL Indexing Masterclass: B-Tree vs BRIN vs GIN vs GiST (Speed Up Queries 100x Without Adding RAM)

Most developers default to standard B-Tree indexes on every column, unaware that append-only log tables can save 99% disk space with BRIN, and JSONB document queries require GIN. Here is a definitive, production-tested deep dive into PostgreSQL index architectures, EXPLAIN ANALYZE buffer mechanics, index maintenance overhead, and how to optimize high-scale database workloads without throwing expensive hardware at the problem.

Pathubs Engineering
Pathubs Engineering
Database & Systems Architecture
Published Nov 7, 2026Updated Nov 7, 20268 min read
Cinematic developer workstation displaying PostgreSQL query execution plans with EXPLAIN ANALYZE, contrasting B-Tree balanced branching with compact BRIN block range index memory layouts.

<div className="callout callout-tip"> <div className="callout-title"> <span>πŸ’‘ The Golden Rule of Database Performance</span> </div> <p> The fastest query is the one that never touches the disk. While scaling engineering teams instinctively spend thousands of dollars upgrading AWS RDS instance classes or adding memory to Redis caches, over 80% of database bottlenecks can be solved permanently by selecting the correct index data structure. Defaulting blindly to <code>CREATE INDEX</code> (B-Tree) on every column wastes gigabytes of RAM and cripples write throughput. </p> </div>

---

1. Executive Summary & Key Takeaways

PostgreSQL is celebrated for its extensibility, and nowhere is this more apparent than its rich indexing engine. While most relational databases only expose standard B-Trees, PostgreSQL provides six native access methods: B-Tree, BRIN, GIN, GiST, SP-GiST, and HASH.

Choosing the wrong index structureβ€”or using a B-Tree where a BRIN or GIN index is requiredβ€”leads to:

  • Index Bloat: Secondary indexes consuming 3x more disk space than the actual data table.
  • RAM Starvation: PostgreSQL's shared_buffers cache filling up with massive index trees instead of frequently accessed data rows.
  • Write Degradation: Every INSERT and UPDATE stalling as the engine locks and splits multiple B-Tree leaf pages.
text
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚                        POSTGRESQL INDEX CHEAT SHEET                    β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ 1. B-Tree (Default):                                                   β”‚
β”‚    Best for: Unique keys, primary keys, point lookups (=), ranges.    β”‚
β”‚    Tradeoff: High disk footprint; every row has an index entry.        β”‚
β”‚                                                                        β”‚
β”‚ 2. BRIN (Block Range Index):                                           β”‚
β”‚    Best for: Append-only timestamp logs, IoT metrics, audit trails.    β”‚
β”‚    Tradeoff: Saves 99% disk space; requires physically sorted data.    β”‚
β”‚                                                                        β”‚
β”‚ 3. GIN (Generalized Inverted Index):                                   β”‚
β”‚    Best for: JSONB documents (@>), arrays (&&), full-text search.      β”‚
β”‚    Tradeoff: Slower updates (mitigated by fastupdate buffer).         β”‚
β”‚                                                                        β”‚
β”‚ 4. GiST (Generalized Search Tree):                                     β”‚
β”‚    Best for: Geospatial/PostGIS (ST_DWithin), range types (&&).        β”‚
β”‚    Tradeoff: Lossy traversals; slightly slower reads than B-Tree.      β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

---

2. B-Tree: The Ubiquitous Workhorse

When you execute CREATE INDEX ON orders (customer_id);, PostgreSQL creates a self-balancing multi-way search tree (B+ Tree variant).

text
                      [ Root Page: Keys (100, 500) ]
                             /         |         \
                            /          |          \
        [ Internal Page: < 100 ]  [ 100 - 500 ]  [ > 500 ]
             /        \              /       \        \
    [ Leaf: Ptrs ] [ Leaf ]     [ Leaf ]   [ Leaf ]  [ Leaf Page: Ptrs ]
           β”‚
           β–Ό
    ( Heap Tuple on Disk: Block 42, Offset 3 )

How B-Tree Operates

  • Balanced Height: Every leaf page sits at the exact same depth from the root, guaranteeing $O(\log N)$ search time.
  • Bi-Directional Pointers: Leaf pages form a doubly-linked list, allowing high-speed range scans in both ascending (ASC) and descending (DESC) order.
  • Heap Tuple Pointers (TIDs): Every leaf entry consists of (Key Value, TID), where the Tuple ID points directly to the physical disk block and item offset of the row in the table.

Supported Operators

The B-Tree access method supports: <, <=, =, >=, >, BETWEEN, IN, and IS NULL. It also accelerates pattern matching using LIKE 'prefix%' (provided the database uses the C collation or an operator class like varchar_pattern_ops).

The B-Tree Performance Trap

Consider an event analytics table storing 100 million rows:

sql
CREATE TABLE event_logs (
    id BIGSERIAL PRIMARY KEY,
    created_at TIMESTAMPTZ NOT NULL,
    payload JSONB
);

-- Creating a B-Tree index on created_at:
CREATE INDEX idx_logs_created_at_btree ON event_logs (created_at);
  • Table Size: ~12 GB.
  • B-Tree Index Size: ~2.2 GB.

Because the B-Tree must store 100 million individual timestamps and 100 million 6-byte TIDs, the index alone consumes 2.2 GB of disk and precious RAM.

If this table is purely append-only (events are inserted chronologically), 99% of that 2.2 GB is completely wasted. That is where BRIN enters.

---

3. BRIN: The 99% Space-Saving Secret Weapon

Introduced in PostgreSQL 9.5, BRIN (Block Range Index) is specifically engineered for tables where column values correlate strongly with their physical position on disk.

text
Table Heap Storage (Physical Disk Pages):
[ Block 0 - 127 ] ──► Contains rows with created_at: [ 2026-01-01 to 2026-01-03 ]
[ Block 128 - 255] ──► Contains rows with created_at: [ 2026-01-03 to 2026-01-06 ]
[ Block 256 - 383] ──► Contains rows with created_at: [ 2026-01-06 to 2026-01-09 ]

BRIN Index Metadata Summary (Tiny Footprint):
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚ Block Range    β”‚ Minimum Value            β”‚ Maximum Value            β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Range 0 (0-127)β”‚ 2026-01-01 00:00:00+00   β”‚ 2026-01-03 23:59:59+00   β”‚
β”‚ Range 1 (128)  β”‚ 2026-01-03 14:10:00+00   β”‚ 2026-01-06 18:22:10+00   β”‚
β”‚ Range 2 (256)  β”‚ 2026-01-06 18:22:15+00   β”‚ 2026-01-09 11:05:00+00   β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

How BRIN Operates

Instead of indexing every single row, BRIN divides the physical table heap into chunks called block ranges (the default pages_per_range is 128 pages, or 1 Megabyte of table data).

For each block range, BRIN stores only two values:

  1. The Minimum value observed in that range.
  2. The Maximum value observed in that range.

When you execute:

sql
SELECT * FROM event_logs 
WHERE created_at >= '2026-01-07' AND created_at < '2026-01-08';

PostgreSQL consults the BRIN index:

  • Range 0 (2026-01-01 to 2026-01-03): Skip completely!
  • Range 1 (2026-01-03 to 2026-01-06): Skip completely!
  • Range 2 (2026-01-06 to 2026-01-09): Match found. The engine reads only Blocks 256–383 into memory and filters the rows.

The Real-World Benchmark: B-Tree vs. BRIN

On the same 100-million-row event_logs table:

sql
-- Creating a BRIN index instead:
CREATE INDEX idx_logs_created_at_brin ON event_logs USING BRIN (created_at);
MetricB-Tree IndexBRIN IndexImprovement with BRIN
Index Size on Disk2,240 MB (2.2 GB)184 KB99.99% smaller!
RAM Required in CacheHigh (~2.2 GB)Negligible (~0.2 MB)Frees memory for data
Insert Throughput~24,000 writes/sec~68,000 writes/sec2.8x faster ingestion
Query Execution Time3.2 ms5.8 msAcceptable 2.6 ms delta

The Critical Precondition: Physical Correlation

BRIN relies on physical ordering. You can verify whether a column is a candidate for BRIN by querying the pg_stats system catalog:

sql
SELECT tablename, attname, correlation 
FROM pg_stats 
WHERE tablename = 'event_logs' AND attname = 'created_at';

If the correlation metric is close to 1.0 (chronological append) or -1.0 (reverse chronological), use BRIN. If the correlation is close to 0.0 (randomly scattered values across pages), BRIN will lose its pruning ability and fall back to scanning almost every block.

---

If you attempt to query a JSONB column with a standard B-Tree:

sql
SELECT * FROM users WHERE metadata @> '{"role": "admin"}';

A B-Tree index on metadata is completely useless. B-Tree can only compare the *entire JSON string as a single scalar value*; it cannot peek inside nested keys.

This is where GIN (Generalized Inverted Index) is mandatory.

text
Document 1: {"tags": ["sql", "postgres"], "tier": "gold"}
Document 2: {"tags": ["python", "postgres"], "tier": "silver"}
Document 3: {"tags": ["sql"], "tier": "gold"}

GIN Inverted Index Lookup Table:
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚ Token / Key     β”‚ Matching Row TIDs    β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ "tier": "gold"   β”‚ Row 1, Row 3         β”‚
β”‚ "tier": "silver" β”‚ Row 2                β”‚
β”‚ "tags": "sql"    β”‚ Row 1, Row 3         β”‚
β”‚ "tags": "postgres"β”‚ Row 1, Row 2        β”‚
β”‚ "tags": "python" β”‚ Row 2                β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

How GIN Operates

GIN breaks multi-valued items (JSONB sub-keys, array elements, tsvector words) into individual atomic components. It builds an internal B-Tree of unique keys, where each leaf points to a list or bitmap of rows containing that key.

Choosing the Right GIN Operator Class

When indexing JSONB, PostgreSQL offers two distinct operator classes:

1. `jsonb_ops` (The Default)

sql
CREATE INDEX idx_users_metadata_gin ON users USING GIN (metadata);
  • Indexes: Every key, every path, and every value.
  • Supported Operators: @> (contains), ? (key exists), ?& (all keys exist), ?| (any key exists).
  • Storage Footprint: Large.

2. `jsonb_path_ops` (The Optimized Alternative)

sql
CREATE INDEX idx_users_metadata_path_gin ON users USING GIN (metadata jsonb_path_ops);
  • Indexes: Hashes of complete paths and values (e.g., hash("metadata.tier.gold")).
  • Supported Operators: Strictly @> (contains).
  • Storage Footprint: Up to 60% smaller than default GIN, and significantly faster to search!

<div className="callout callout-warning"> <div className="callout-title"> <span>⚠️ GIN Write Overhead and Fastupdate</span> </div> <p> Because a single <code>INSERT</code> containing 20 JSON keys requires inserting 20 separate entries into the GIN index, raw GIN writes are heavy. PostgreSQL mitigates this with a temporary memory buffer called <code>fastupdate</code>. New entries are written into an unorganized list page and later consolidated in bulk by VACUUM or when <code>gin_pending_list_limit</code> is exceeded. </p> </div>

---

5. GiST: Geospatial, Range Overlaps, and Exclusion Constraints

GiST (Generalized Search Tree) is a template index structure that allows developers to define indexing schemes for arbitrary, multi-dimensional data types.

While B-Tree divides data into non-overlapping left/right branches, GiST uses bounding boxes or bounding hulls that can overlap.

text
                   [ Bounding Box: Continental US ]
                          /                \
                         /                  \
        [ Bounding Box: West Coast ]    [ Bounding Box: East Coast ]
             /            \                  /           \
        [ California ] [ Oregon ]       [ New York ]   [ Florida ]

Top Production Use Cases for GiST

1. Preventing Double-Booking with Exclusion Constraints

Imagine building an Airbnb or hotel reservation engine. You must ensure that no room is booked for overlapping date ranges:

sql
CREATE EXTENSION IF NOT EXISTS btree_gist;

CREATE TABLE room_reservations (
    room_id INT NOT NULL,
    booking_dates DATERANGE NOT NULL,
    -- Prevent overlapping bookings for the same room:
    EXCLUDE USING GIST (
        room_id WITH =, 
        booking_dates WITH &&
    )
);

-- Insertion 1: Sells out Room 101 for Jan 1 to Jan 10
INSERT INTO room_reservations VALUES (101, '[2026-01-01, 2026-01-10)');

-- Insertion 2: Overlaps Jan 5 to Jan 15 -> Fails immediately with constraint error!
INSERT INTO room_reservations VALUES (101, '[2026-01-05, 2026-01-15)');
-- ERROR: conflicting key value violates exclusion constraint "room_reservations_room_id_booking_dates_excl"

Without a GiST exclusion constraint, preventing race-condition double bookings requires expensive serializable transactions or pessimistic database locking (SELECT FOR UPDATE).

2. PostGIS Geospatial Proximity Searches

In PostGIS, GiST indexes accelerate nearest-neighbor (<->) and bounding-box queries:

sql
-- Find all drivers within 5 kilometers:
SELECT driver_id, location 
FROM active_drivers 
WHERE ST_DWithin(location, ST_MakePoint(-73.9851, 40.7488)::geography, 5000);

---

6. Reading the Truth: EXPLAIN (ANALYZE, BUFFERS)

Never guess whether an index works. Always verify execution using EXPLAIN (ANALYZE, BUFFERS).

Consider this execution plan comparing an unindexed query against an indexed query on a 5-million-row orders table:

Before Indexing: Sequential Scan (Full Disk Sweep)

sql
EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM orders WHERE customer_id = 94821;
text
Seq Scan on orders  (cost=0.00..108420.00 rows=12 width=142) (actual time=142.310..388.420 rows=8 loops=1)
  Filter: (customer_id = 94821)
  Rows Removed by Filter: 4999992
  Buffers: shared hit=412 read=38410
Planning Time: 0.124 ms
Execution Time: 388.462 ms
  • Buffers: read=38410 means PostgreSQL had to physically pull 38,410 pages (over 300 Megabytes) from disk into memory.
  • Execution Time: 388 milliseconds.

After Adding B-Tree Index: Index Scan

sql
CREATE INDEX idx_orders_customer_id ON orders (customer_id);

EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM orders WHERE customer_id = 94821;
text
Bitmap Heap Scan on orders  (cost=4.82..48.12 rows=12 width=142) (actual time=0.041..0.052 rows=8 loops=1)
  Recheck Cond: (customer_id = 94821)
  Heap Blocks: exact=4
  Buffers: shared hit=7
  ->  Bitmap Index Scan on idx_orders_customer_id  (cost=0.00..4.81 rows=12 width=0) (actual time=0.028..0.028 rows=8 loops=1)
        Index Cond: (customer_id = 94821)
        Buffers: shared hit=3
Planning Time: 0.089 ms
Execution Time: 0.071 ms
  • Buffers: shared hit=7 (only 7 memory pages inspected, zero disk reads).
  • Execution Time: 0.071 milliseconds (Over 5,400x faster!).

---

7. Architectural Decision Matrix

Use this decision table when designing your database schemas:

Data Type / Access PatternQuery ExamplesRecommended IndexWhy?
Primary Keys & UUIDsWHERE id = 42B-TreeO(log N) uniqueness enforcement and point lookup.
Chronological TimestampsWHERE created_at >= '2026-01-01'BRIN99% disk savings on append-only event data.
JSONB Objects (Key/Value)WHERE data @> '{"status": "ok"}'GIN (`jsonb_path_ops`)Inverts JSON paths into fast searchable hashes.
Array Tags / CategoriesWHERE tags && ARRAY['db', 'sql']GINInverts array elements; finds matches instantly.
Geographic CoordinatesWHERE ST_DWithin(geom, ...)GiSTBounding box spatial pruning (R-Tree layout).
Booking / Schedule RangesEXCLUDE USING GIST (date_range &&)GiSTNative intersection and collision detection.
Exact Hash Equality OnlyWHERE token = 'abc123xyz'HASHO(1) equality lookups (smaller than B-Tree, no ranges).

---

8. Identifying Unused & Bloated Indexes in Production

Every index you create is a tax on write performance. Run these diagnostic queries against your live database to identify dead weight:

1. Detect Unused Indexes

sql
SELECT 
    schemaname || '.' || relname AS table_name,
    indexrelname AS index_name,
    idx_scan AS number_of_scans,
    pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
JOIN pg_index USING (indexrelid)
WHERE indisunique IS FALSE
  AND idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;

*Any non-unique index with number_of_scans = 0 on a database that has been running for weeks is dead weight consuming RAM and slowing down writes. Drop it!*

2. Safely Dropping Indexes Without Locking Traffic

Never run a bare DROP INDEX during business hours! It locks the entire table against writes. Always specify CONCURRENTLY:

sql
DROP INDEX CONCURRENTLY idx_orders_unused_field;

---

9. Conclusion: Engineering with Intent

Database performance is rarely about brute-force computational power. It is about algorithmic alignment between your data's physical layout on disk and the access method used to retrieve it.

By stepping beyond the default B-Tree:

  • You can shrink multi-gigabyte time-series indexes into kilobytes using BRIN.
  • You can turn slow, full-table JSON scanning into sub-millisecond document queries using GIN.
  • You can eliminate race-condition booking bugs permanently at the database layer using GiST.

Mastering these four index architectures is what separates developers who panic and upgrade server tiers from engineers who design scalable, high-throughput systems that run effortlessly for years.

Frequently Asked Questions

What is the difference between B-Tree and BRIN indexes in PostgreSQL?

A B-Tree index maintains a balanced, sorted tree containing a pointer to every single individual row in the table, delivering O(log N) lookups for equality and ranges at the cost of high storage and write overhead. A BRIN (Block Range Index) does not index individual rows; instead, it stores only the minimum and maximum values for physical ranges of disk pages (default 128 pages). For naturally ordered or append-only datasets (like timestamps or auto-incrementing IDs), BRIN delivers near-B-Tree query speeds while consuming up to 99% less disk space and almost zero write overhead.

When should I use a GIN (Generalized Inverted Index) instead of a B-Tree?

Use GIN when a single column contains multiple composite elements or values that need to be searched independently. Common use cases include JSONB documents (using operators like @>, ?, ?&), array columns (int[], text[]), and full-text search (tsvector). While B-Tree can only match an entire composite value as a whole, GIN creates inverted entries mapping every individual sub-key or token to the matching rows.

What is the primary use case for GiST (Generalized Search Tree) indexes?

GiST is designed for multi-dimensional data, non-scalar geometric shapes, full-text search, and range overlapping. In PostGIS, GiST powers spatial queries (like ST_DWithin or ST_Intersects). In standard PostgreSQL, GiST is essential for range types (tsrange, daterange) and exclusion constraints (preventing overlapping hotel bookings or scheduled meeting rooms using the && operator).

Why does PostgreSQL sometimes ignore an index and run a Sequential Scan instead?

The PostgreSQL query planner uses cost-based optimization. If a query matches a large percentage of the table (typically 10% to 25% or more), sequential disk scanning is faster than random index lookups because reading consecutive disk pages in bulk has lower I/O latency than bouncing back and forth between index pages and heap table pages. Outdated table statistics (fixed via ANALYZE) or indexing columns wrapped in functions (requiring expression indexes) are other common reasons.

How much write overhead do indexes introduce on INSERT and UPDATE operations?

Every B-Tree, GIN, or GiST index on a table must be synchronously updated during every INSERT, DELETE, and relevant UPDATE operation. On write-heavy tables, having 6 to 10 B-Tree indexes can slow down ingest throughput by 300% to 500% and cause severe index bloat. BRIN indexes, in contrast, introduce almost zero write overhead because new rows simply fall into the current open block range without modifying prior index pages.

How do I diagnose whether my PostgreSQL index is actually being used?

Prepend your query with EXPLAIN (ANALYZE, BUFFERS). Look for 'Index Scan' or 'Bitmap Index Scan' in the plan instead of 'Seq Scan'. The 'Buffers: shared hit=X read=Y' output reveals how many 8KB memory pages were fetched from RAM (hit) versus disk (read). Additionally, query the 'pg_stat_user_indexes' system catalog to check 'idx_scan' counters across your database to identify completely unused indexes that should be dropped.