05. Indexing Mechanics & Data Structures¶

Indexes in PostgreSQL are self-contained access methods registered in pg_am. Understanding their internal tree representations and page structures allows engineers to choose optimal indexing strategies and execute zero-downtime schema changes.

1. The B-Tree Internals: The Lehman & Yao Algorithm¶

PostgreSQL's B-Tree implementation (src/backend/access/nbtree/) is based on the Lehman & Yao (1981) high-concurrency B-Tree algorithm.

               [ Root Node ]
               /           \
     [ Internal Page A ] ----btpo_next----> [ Internal Page B ]
        /            \                         /            \
  [ Leaf Page 1 ] -btpo_next-> [ Leaf Page 2 ] -btpo_next-> [ Leaf Page 3 ]

High Keys & Right-Link Pointers (`btpo_next`)¶

In standard B-Trees, splitting a page requires acquiring an exclusive write lock on the parent node, creating severe lock contention under high insert throughput. * In Lehman & Yao, every page contains a High Key (the upper bound key on that page) and a right-link pointer (btpo_next) pointing to its right sibling. * Concurrent Split Without Parent Locks: When a page splits, the right sibling is created and linked immediately. If a concurrent search traverses down using an outdated parent key, it detects that the target key is greater than the High Key and simply follows btpo_next horizontally to find the item!

B-Tree Deduplication (PG 13+) & Bottom-Up Pruning (PG 14+)¶

Deduplication: In columns with duplicate values, leaf pages store the key once followed by an array of ctid pointers (a posting list), saving up to 40% disk and RAM.
Bottom-Up Index Deletion: Eliminates index bloat caused by non-HOT updates. When a leaf page is full, PostgreSQL inspects heap tuples to find dead versions and deletes their index pointers proactively before triggering an expensive page split.

2. GIN (Generalized Inverted Index)¶

Designed for composite and multi-element data types (JSONB, full-text search tsvector, arrays).

Entry Tree (B-Tree of distinct words/keys)
├── "database"  ──> Posting List: [ctid 1, ctid 4, ctid 19, ...]
├── "distributed" ──> Posting Tree (B-Tree of ctids if list > 1 page)
└── "postgres"  ──> Posting List: [ctid 2, ctid 4, ...]

The `fastupdate` Buffer¶

Inserting into a GIN index requires updating multiple entries per row. To maintain high write speed: * fastupdate = on writes new entries to an unorganized pending list page. * When the pending list exceeds gin_pending_list_limit (default 4MB) or during VACUUM, the entries are batch-merged into the main GIN tree.

3. BRIN (Block Range Index)¶

For append-only and time-series tables physically ordered by a column (e.g. created_at, auto-incrementing id):

Instead of storing a pointer per row, BRIN stores only the minimum and maximum value for a range of pages (default 128 pages = 1 MB of heap data).
Space Footprint: While a B-Tree on 100M rows might take 2.5 GB, a BRIN index takes under 100 KB!

-- Optimal for sequential time-series events
CREATE INDEX idx_events_created ON events USING brin (created_at) 
WITH (pages_per_range = 64);

4. Covering Indexes (`INCLUDE`) for Index-Only Scans¶

An Index-Only Scan fulfills a query entirely from the index without reading the heap table, provided the 8KB page is marked as all-visible in the Visibility Map.

Using the INCLUDE clause adds payload columns to the leaf pages only, keeping internal B-Tree routing nodes small and cache-friendly:

-- Standard compound index bloats internal nodes with large payloads
-- Covering index keeps routing keys narrow:
CREATE INDEX idx_users_active_lookup 
ON users (tenant_id, email) 
INCLUDE (first_name, last_name, avatar_url);

-- This query performs a pure Index-Only Scan:
SELECT first_name, last_name, avatar_url 
FROM users 
WHERE tenant_id = 42 AND email = 'alice@example.com';

5. Zero-Downtime Indexing (`CREATE INDEX CONCURRENTLY`)¶

A standard CREATE INDEX acquires an SHARE lock on the table, blocking all concurrent INSERT, UPDATE, and DELETE queries until the index build completes.

CREATE INDEX CONCURRENTLY operates in three non-blocking phases:

sequenceDiagram
    participant D as DDL Transaction
    participant T as Table (Concurrent Writes)

    Note over D,T: Phase 1: Prepare & Register
    D->>T: Acquire ShareUpdateExclusiveLock (Writes NOT blocked)
    D->>T: Register index entry in pg_class (indisready=false, indisvalid=false)

    Note over D,T: Phase 2: Build Initial Snapshot
    D->>T: Wait for old write transactions to complete
    D->>T: Scan table & build index entries (indisready=true)

    Note over D,T: Phase 3: Catch-up & Validate
    D->>T: Wait for write transactions that started during Phase 2
    D->>T: Second scan: apply missed updates & validate (indisvalid=true)
    Note over D,T: Index becomes active for queries

Handling Invalid Indexes¶

If a unique constraint violation or lock timeout occurs during Phase 3, the index remains on disk with indisvalid = false:

-- Query to identify corrupted or failed concurrent index attempts:
SELECT schemaname, relname, indexrelname 
FROM pg_stat_user_indexes 
JOIN pg_index USING (indexrelid) 
WHERE NOT indisvalid;

-- Remediation: Drop the invalid index and retry
DROP INDEX CONCURRENTLY idx_users_active_lookup;