Skip to content

Database Index Internals: B-Tree, GIN, GiST & BRIN Architecture on Linux

Created: 2026-11-08  ·  Last updated: 2026-11-08  ·  Nejat Hakan

Executive Summary: An index trades disk space and write overhead for dramatic reductions in read query latency—transforming an O(N) full sequential table scan into an O(log N) tree traversal or O(1) bitmap lookup. However, applying default B-Trees indiscriminately to JSON payloads, geometric ranges, or multi-terabyte append-only time-series tables results in massive index bloat and cache thrashing. This guide explores the physical data structures and algorithms powering B-Tree, GIN, GiST, and BRIN indexes, alongside production patterns like Covering Indexes (INCLUDE), Partial Indexes, and non-blocking CREATE INDEX CONCURRENTLY.

  • B-Tree Architecture

    Traverse balanced N-ary search trees: navigate root and branch routing pages down to doubly-linked leaf pages for range scans.

  • GIN for JSONB & Arrays

    Invert unstructured payloads into posting lists: accelerate containment (@>) and key existence lookups on JSONB documents.

  • :material-compress:{ .lg .middle } BRIN Time-Series Compression

    Index multi-terabyte append-only tables with 99% less disk space: summarize minimum and maximum values per physical 1 MB block range.

  • Covering & Partial Indexes

    Eliminate heap pointer hops via INCLUDE for Index-Only Scans, and index strictly active rows (WHERE status = 'PENDING').

1. Index Architecture & Traversal Mechanics

Choosing the correct index structure depends on the mathematical nature of the data and query predicates:

Index Type Underlying Data Structure Optimal Query Operators Primary Production Workload
B-Tree (Default) Balanced N-ary tree with horizontally linked leaf pages =, <, <=, >, >=, BETWEEN, IN, ORDER BY High-cardinality scalar columns (id, email, created_at, foreign keys).
GIN (Generalized Inverted) Inverted lookup map of component elements → posting lists of ctids @>, ?, ?&, ?|, @@ (Full-Text Search) Nested JSONB documents, array types (TEXT[]), and full-text search tsvector.
GiST (Generalized Search Tree) Lossy balanced tree supporting arbitrary bounding boxes && (Overlap), <-> (KNN distance), @> PostGIS geographic coordinates, IP network subnets (INET), and exclusion constraints.
BRIN (Block Range Index) Min/Max boundary summary per physical block range (default 128 pages) <, >, BETWEEN on correlated physical data Multi-terabyte append-only audit logs, IoT sensor data, and time-series telemetry. 
%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart TB
    subgraph BTree["🌳 B-Tree: High-Precision O(log N)"]
        B_ROOT["Root Page<br/>Keys: [1000 | 5000]"]
        B_INT["Internal Routing Node<br/>Keys: [250 | 750]"]
        B_LEAF1["Leaf Page 1 (Sorted)<br/>ctid -> (Block 4, Slot 1)"]
        B_LEAF2["Leaf Page 2 (Sorted)<br/>ctid -> (Block 4, Slot 2)"]
        B_ROOT --> B_INT
        B_INT --> B_LEAF1
        B_INT --> B_LEAF2
        B_LEAF1 <-->|"Doubly-Linked Scan"| B_LEAF2
    end

    subgraph GIN["📄 GIN: Inverted Key Map"]
        G_KEY["JSON Key: 'role'"]
        G_POST["Posting List<br/>ctid: [(1,2), (5,8), (9,1)]"]
        G_KEY --> G_POST
    end

    subgraph BRIN["📦 BRIN: Block-Range Summary"]
        BR_RANGE["Pages 0–127 (1 MB Block)"]
        BR_SUM["Min: 2026-01-01<br/>Max: 2026-01-07"]
        BR_RANGE --> BR_SUM
    end

2. B-Tree Internals: Why Leaf Doubly-Linked Lists Matter

In a B-Tree index, all leaf pages reside at the exact same depth from the root (guaranteeing uniform O(log N) search latency).

Fast Range Scans Without Root Traversal

When an application queries WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31': 1. The engine traverses from the Root page down through internal routing nodes to find the leaf page containing the start date '2026-01-01'. 2. Once the starting leaf page is located, the engine never re-traverses the root. It follows the horizontal doubly-linked pointers (next_page / prev_page) directly between leaf pages until it encounters '2026-01-31'. 3. This architecture makes sequential range scans and ORDER BY operations run at near-memory bandwidth.

3. GIN (Generalized Inverted Index) for JSONB

Standard B-Trees index entire column values as single monolithic entities. A GIN Index decomposes composite values (such as JSONB documents or arrays) into individual component keys and values:

Document 1: {"role": "admin", "team": "devops"}
Document 2: {"role": "viewer", "team": "devops"}

GIN Inverted Map:
  "admin"  --> [Doc 1]
  "viewer" --> [Doc 2]
  "devops" --> [Doc 1, Doc 2]

jsonb_ops vs. jsonb_path_ops

PostgreSQL provides two operator classes for GIN indexing: - jsonb_ops (Default): Indexes every key, value, and path. Supports path lookups (?, ?|, @>), but results in larger index footprints. - jsonb_path_ops: Hashes the full path-value pair (e.g., hash("team.devops")). Produces an index up to 60% smaller and faster, but only supports containment queries (@>).

-- Production Best Practice: Fast containment indexing on JSONB
CREATE INDEX CONCURRENTLY idx_customer_metadata_gin 
    ON customer_orders USING GIN (metadata jsonb_path_ops);

4. BRIN (Block Range Index): Scaling to Multi-Terabytes

On massive time-series tables (e.g., 500 million rows of server metrics), a B-Tree index can consume hundreds of gigabytes of RAM, exceeding available buffer pool capacity.

If rows are inserted in natural chronological order, the data in physical storage blocks is already sorted:

Physical Storage on Disk:
  Block 0-127   --> Timestamps from 2026-01-01 to 2026-01-05
  Block 128-255 --> Timestamps from 2026-01-06 to 2026-01-10
  Block 256-383 --> Timestamps from 2026-01-11 to 2026-01-15

A BRIN Index does not record pointers for individual rows. It simply stores the min and max values for each contiguous range of physical pages (default 128 pages = 1 MB): - When querying WHERE recorded_at = '2026-01-08', the engine skips Blocks 0–127 and Blocks 256–383 entirely. - A BRIN index is typically 100× to 1000× smaller than a B-Tree, fitting entirely inside the CPU L3 cache.

-- Production Best Practice: BRIN index for chronological time-series tables
CREATE INDEX CONCURRENTLY idx_server_metrics_brin 
    ON server_metrics USING BRIN (recorded_at) 
    WITH (pages_per_range = 128);

5. Advanced Production Indexing Patterns

A. Covering Indexes (INCLUDE) for Index-Only Scans

When a query selects columns not present in a secondary index, the engine must make a random I/O hop to the table heap page for every matching row.

Using INCLUDE appends non-key payload columns to the B-Tree leaf pages without adding them to the search key:

-- Allows dashboard queries to be answered ENTIRELY from the index (Index-Only Scan)
CREATE INDEX CONCURRENTLY idx_orders_customer_covering 
    ON customer_orders (customer_id) 
    INCLUDE (total_cents, created_at);

-- Query:
SELECT customer_id, total_cents, created_at 
FROM customer_orders 
WHERE customer_id = 101; -- Zero Heap Hops if Visibility Map is clean!

B. Partial Indexes: Indexing strictly what matters

If 99% of orders have status = 'COMPLETED' and only 1% are status = 'PENDING', indexing the entire table wastes disk space and slows down inserts. A Partial Index filters rows at index-creation time:

-- Index shrinks by 99%, writes to completed orders cause zero index updates!
CREATE INDEX CONCURRENTLY idx_orders_pending_queue 
    ON customer_orders (created_at) 
    WHERE status = 'PENDING';

6. The Production Golden Rule: CREATE INDEX CONCURRENTLY

A standard CREATE INDEX command acquires a SHARE lock on the table, blocking all concurrent INSERT, UPDATE, and DELETE operations for the entire duration of the build:

-- NEVER RUN THIS IN PRODUCTION ON LARGE TABLES:
CREATE INDEX idx_orders_customer ON customer_orders (customer_id);
-- Blocks all customer checkouts and payments until the index finishes!

-- ALWAYS USE CONCURRENTLY IN PRODUCTION:
CREATE INDEX CONCURRENTLY idx_orders_customer ON customer_orders (customer_id);
-- Scans the table in two background passes; writes continue completely unhindered!

Handling Failed Concurrent Builds

If a concurrent build fails (e.g., due to a deadlock or unique constraint violation), PostgreSQL marks the index as INVALID. Invalid indexes consume disk space and slow down writes without serving queries. Always audit and clean invalid indexes: 

-- Check for invalid indexes:
SELECT indisvalid, indexrelid::regclass FROM pg_index WHERE NOT indisvalid;
-- Drop invalid index safely:
DROP INDEX CONCURRENTLY IF EXISTS index_name;