🗄️ Section 1 · Question #2

How does B-tree index work

A B-tree (Balanced Multi-way Search Tree) is the default, general-purpose index structure in PostgreSQL (and most relational databases).

🗄️ Databases SQL PostgreSQL 📄 Source Markdown

🟢 Junior Level

A B-tree (Balanced Multi-way Search Tree) is the default, general-purpose index structure in PostgreSQL (and most relational databases).

Why “Balanced”?

All leaf nodes in a B-tree reside at the exact same depth from the root. This guarantees consistent logarithmic search complexity $O(\log n)$ for every lookup, preventing pathological degeneration into an $O(n)$ linked list (a common failure mode in unbalanced binary search trees).

Simple Analogy

Think of an index in a multi-volume encyclopedia:

  • Top Level (Root): Volume dividers (A–D, E–H, I–P, Q–Z).
  • Middle Level (Internal Nodes): Section headings within each volume.
  • Bottom Level (Leaf Nodes): Specific topic keywords paired with exact page and paragraph numbers.

To locate an article, you begin at the root, compare your search term, follow the single relevant pointer downward through 2–3 levels, and arrive directly at the exact page without reading the rest of the encyclopedia.

                   ┌──────────────┐
                   │  Root Node   │
                   └──────┬───────┘
            ┌─────────────┴─────────────┐
            ▼                           ▼
     ┌──────────────┐            ┌──────────────┐
     │Internal Node │            │Internal Node │
     └──────┬───────┘            └──────┬───────┘
       ┌────┴────┐                 ┌────┴────┐
       ▼         ▼                 ▼         ▼
  ┌────────┐ ┌────────┐       ┌────────┐ ┌────────┐
  │ Leaf 1 │ │ Leaf 2 │◄─────►│ Leaf 3 │ │ Leaf 4 │  (Bidirectional Links)
  └────────┘ └────────┘       └────────┘ └────────┘
       │          │               │          │
       ▼          ▼               ▼          ▼
    [Row 1]    [Row 2]         [Row 3]    [Row 4]     (Physical Table Heap)

Core Characteristics

  • Data is stored in a strictly sorted (lexicographical) order.
  • Traversal is blisteringly fast: searching through 10,000,000 rows requires reading only 3–4 eight-kilobyte index pages instead of scanning gigabytes of table heap.
  • PostgreSQL automatically balances the tree during INSERT, UPDATE, and DELETE operations.
-- Creates a standard B-tree index (B-tree is used by default)
CREATE INDEX idx_users_email ON users(email);

-- Index lookup executes in O(log n) time
SELECT * FROM users WHERE email = 'alex@example.com';

Supported Query Patterns

  • Equality lookups: WHERE id = 42
  • Range scans: WHERE price BETWEEN 100 AND 500 or WHERE created_at >= '2026-01-01'
  • Prefix pattern matching: WHERE username LIKE 'alex%'
  • Sorted retrieval: ORDER BY created_at DESC LIMIT 10 (avoids expensive in-memory sort)
  • Null checks: WHERE deleted_at IS NULL

🟡 Middle Level

Internal Physical Structure: 8 KB Pages

PostgreSQL organizes B-trees into standard 8 KB pages (blocks) structured hierarchically:

  • Level 0 (Leaf Pages): Store the indexed key values paired with TID (ItemPointerData) pointers (block_number, tuple_offset) referencing the exact row location in the table heap.
  • Level 1+ (Internal Pages): Store routing separator keys paired with downlink block pointers directing searches to lower tree levels.
  • Root Page: The top-level entry point (cached in memory via the meta-page’s Fastroot pointer).

Inside an 8 KB Index Page:

  1. Page Header (PageHeaderData): Contains LSN (Log Sequence Number for WAL recovery), checksums, and free space boundary offsets.
  2. High Key: The strict upper boundary key stored on this page (present on all non-rightmost pages).
  3. Index Tuples: The sorted payload keys and downlink pointers / TIDs.
  4. Special Area (BTPageOpaqueData): Located at the very end of the 8 KB page, containing tree level flags, cycle detection metadata, and bidirectional sibling pointers (P_NEXT and P_PREV).
Structure of an 8 KB B-Tree Page:
┌────────────────────────────────────────────────────────┐
│ Page Header (LSN, Checksum, Offsets)                   │
├────────────────────────────────────────────────────────┤
│ Line Pointers (Index tuple directory offsets)          │
├────────────────────────────────────────────────────────┤
│ Free Space                                             │
├────────────────────────────────────────────────────────┤
│ High Key (Upper bound value for this page)             │
├────────────────────────────────────────────────────────┤
│ Index Tuples: [Key 1, TID 1], [Key 2, TID 2] ...       │
├────────────────────────────────────────────────────────┤
│ Special Area (P_NEXT, P_PREV, Flags: LEAF/ROOT)        │
└────────────────────────────────────────────────────────┘

Search Traversal Algorithm

  1. The backend accesses the index Meta-page (Block 0) and identifies the Root Page.
  2. Inside the root page, binary search locates the highest key that is $\le$ the search key.
  3. The backend follows the downlink block pointer to the child internal page.
  4. Steps 2–3 repeat until the search lands on a Leaf Page (Level 0).
  5. On the leaf page, binary search finds the exact key match.
  6. The engine reads the matching TID and fetches the physical row from the table heap.
  7. For range queries (BETWEEN A AND B), after finding key A, the engine does not navigate back up the tree. It simply follows the P_NEXT sibling link sequentially across adjacent leaf pages until reaching key B.

Why B-tree Instead of a Binary Search Tree (BST)?

Architecture Metric Binary Search Tree (BST / Red-Black) PostgreSQL B-Tree
Branching Factor (Fan-out) 2 (left / right child) 100–500+ child pointers per page
Height for 10,000,000 Rows ~24 levels 3–4 levels
Disk I/O Reads per Query ~24 random disk seeks 3–4 block reads (root and internal nodes reside in RAM buffer cache)
Hardware Cache Alignment Poor (nodes scattered across memory) High (dense 8 KB pages perfectly match OS block I/O)

🔴 Senior Level

Concurrency Model: Lehman & Yao B-Link Tree Algorithm

PostgreSQL avoids global tree locking during concurrent modifications by implementing the Lehman & Yao B-link tree algorithm:

  • No Parent Locks on Descent: A reader descends the tree taking short-term shared buffer content latches on one page at a time, releasing the parent latch before locking the child.
  • Handling Concurrent Page Splits: When an 8 KB leaf page fills up and an insert occurs, a Page Split divides the page into two 50/50 halves.
  • Right-Link Invariant: If a concurrent reader descends to a leaf page that was split moments earlier by an in-flight writer:
    1. The reader inspects the page’s High Key.
    2. If search_key > High_Key, the reader realizes the target item was moved to the newly created split sibling.
    3. Instead of aborting or backtracking to the root, the reader simply moves rightward across the P_NEXT pointer.

Modern PostgreSQL Engine Innovations

1. B-Tree Deduplication (PostgreSQL 13+)

In older versions, indexing non-unique columns (e.g., status = 'ACTIVE') stored repetitive (Key, TID) pairs, consuming gigabytes of redundant space.
PostgreSQL 13 introduced B-Tree Deduplication (deduplicate_items = on):

-- Stores 'ACTIVE' once, followed by a Posting List array of TIDs:
-- Key: 'ACTIVE' -> [TID_1, TID_2, TID_3, ..., TID_150]
CREATE INDEX idx_orders_status ON orders(status);

This reduces index physical size by 60–85% and keeps tree depth shallow.

2. Bottom-Up Index Deletion (PostgreSQL 14+)

Previously, frequent UPDATE statements that could not use HOT optimization caused rapid B-tree page splits.
In PostgreSQL 14+, when an insertion threatens to split an index leaf page, the engine triggers a Bottom-Up Index Deletion:

  1. It identifies index tuples pointing to dead heap tuples (LP_DEAD).
  2. It checks whether the dead heap versions are fully visible to all active transactions.
  3. It purges the dead index tuples in-place before triggering the split. This prevents runaway index bloat in heavy update workloads.

3. Asymmetric Split for Monotonic Keys

For strictly ascending keys (BIGSERIAL id, timestamps), standard 50/50 page splitting would leave the left half frozen at 50% density forever. PostgreSQL detects sequential right-side insertions and performs an asymmetric 90/10 split, ensuring append-only indexes maintain 90%+ page packing density.

Diagnosing B-Tree Health and Fragmentation

-- Enable pgstattuple extension for physical index inspection
CREATE EXTENSION IF NOT EXISTS pgstattuple;

-- Analyze physical tree metrics
SELECT 
    tree_level,              -- Tree height (3-4 is typical for millions of rows)
    pg_size_pretty(index_size) AS size,
    root_blkno,
    internal_pages,
    leaf_pages,
    empty_pages,
    deleted_pages,
    avg_leaf_density         -- Target > 70-80%; < 50% indicates severe bloat
FROM pgstatindex('idx_users_email');

-- Zero-downtime rebuild to eliminate page fragmentation
REINDEX INDEX CONCURRENTLY idx_users_email;

4 Tricky Questions

1. Is PostgreSQL’s B-Tree technically a B-Tree or a B+Tree? Why does this distinction matter?

Answer:
In academic computer science terminology, PostgreSQL implements a variant of the B+Tree (specifically, a B-link tree), not a classical B-Tree.

  • In a classical B-Tree, row data pointers are stored in both internal and leaf nodes.
  • In a B+Tree, internal nodes store strictly routing keys and child downlink pointers; all data pointers (TIDs) are stored exclusively in leaf nodes.
    Why it matters: Storing data only at the leaf level maximizes the branching factor (fan-out) of internal pages, keeping tree height extremely shallow (3–4 levels). Furthermore, connecting all leaf nodes with horizontal sibling links (P_NEXT / P_PREV) enables $O(k)$ range scans without repeatedly ascending and descending parent nodes.

2. How does PostgreSQL handle NULL values in a B-Tree, and how does this compare to Oracle?

Answer:
In PostgreSQL, NULL values are indexed by default in standard B-Trees. They are grouped together and sorted at the extreme end of the index depending on the index definition (NULLS LAST by default for ASC, NULLS FIRST for DESC). This allows queries like SELECT * FROM users WHERE deleted_at IS NULL to perform an efficient B-Tree Index Scan.
In contrast, databases like Oracle do not store index entries where all indexed columns are NULL, requiring partial indexing or composite dummy column workarounds to index NULLs.

3. What is the Leftmost Prefix Rule in composite B-Trees, and can an index on (a, b) ever be used when querying only column b?

Answer:
The Leftmost Prefix Rule states that a multi-column B-tree sorted by (a, b) sorts primarily by a, and sorts by b only within ties of a.
Normally, a query filtering solely by WHERE b = 42 cannot use the index because values of b are scattered across the entire tree.
However: PostgreSQL’s optimizer can choose a Skip Scan emulation or an Index Scan if column a has near-zero cardinality (e.g., a boolean or status enum with 2 values). In such cases, the engine can conceptually evaluate WHERE a = 1 AND b = 42 UNION ALL WHERE a = 2 AND b = 42. Nevertheless, relying on this is an anti-pattern; queries filtering primarily on b should have an index starting with b.

4. What causes a B-Tree index to bloat, and why doesn’t standard VACUUM shrink the file size?

Answer:
Index bloat is caused by out-of-order INSERTs and non-HOT UPDATEs that trigger page splits, leaving pages with low fill ratios (often 30–50% empty). When rows are deleted, standard VACUUM marks index slots as reusable (LP_DEAD), but it cannot merge underpopulated leaf pages back together nor can it truncate disk space in the middle of a file. The physical file size on disk never decreases.
To restore 80–90% leaf density and return free blocks to the operating system, you must run REINDEX TABLE CONCURRENTLY <table_name> or REINDEX INDEX CONCURRENTLY <index_name>.

🎯 Interview Cheat Sheet

Core Concepts

  • Definition: Multi-way balanced search tree variant (Lehman & Yao B-link tree).
  • Complexity: $O(\log n)$ for search, insertion, and deletion.
  • Fan-out: 100–500 child pointers per 8 KB page, keeping tree height to 3–4 levels for hundreds of millions of rows.
  • Structure: Root → Internal Navigation Nodes (routing keys) → Leaf Nodes (keys + TIDs + High Key + P_NEXT/P_PREV).
  • Range Scans: Once the starting key is found, the engine traverses horizontally via P_NEXT leaf links without visiting upper tree levels.

Key Internal Optimizations

  • Lehman & Yao B-Link: Readers never lock parent subtrees; concurrent page splits are handled seamlessly via High Key and horizontal P_NEXT pointer traversal.
  • Deduplication (PG 13+): Collapses duplicate keys into posting lists, saving 60–85% storage for non-unique columns.
  • Bottom-Up Deletion (PG 14+): Cleans dead index tuples in-place before executing a page split, curbing update-driven bloat.
  • Asymmetric Split: 90/10 split for monotonic serial/timestamp keys avoids 50% permanent fragmentation.

Red Flags (What NOT to Say)

  • ❌ “A B-tree is a binary search tree with two children per node.” (It is a multi-way balanced tree with hundreds of child pointers per 8 KB page).
  • ❌ “Postgres B-trees cannot index NULL values.” (Postgres indexes NULLs by default, placed at the end or beginning via NULLS FIRST/LAST).
  • ❌ “VACUUM FULL is the standard way to fix index bloat in production.” (VACUUM FULL acquires an ACCESS EXCLUSIVE table lock, bringing down production; use REINDEX CONCURRENTLY instead).