---

🟢 Junior Level

Indexes are auxiliary data structures in a relational database that dramatically accelerate data retrieval operations at the cost of additional disk storage and slower write operations (INSERT, UPDATE, DELETE).

Simple Analogy

Imagine a 1,000-page technical textbook without a table of contents or an index at the back. To find where “PostgreSQL transactions” are discussed, you would have to scan every single page from beginning to end. An index in a database works exactly like the back-of-the-book alphabetical index: you look up the search term, get the exact page numbers, and jump straight to the relevant content.

Core Idea

• Without an index: The database engine scans the entire table row by row (Sequential Scan / Seq Scan), reading every data block from disk or buffer cache into memory.
• With an index: The database engine navigates a compact, sorted search structure (typically a B-Tree) to directly pinpoint the physical location of the matching rows (Index Scan).

-- Without an index: Reads all 1,000,000 rows sequentially (~250 ms)
SELECT * FROM users WHERE email = 'alex@example.com';

-- Create an index on the email column
CREATE INDEX idx_users_email ON users(email);

-- With an index: Navigates 3–4 B-tree levels and fetches the exact row (~0.05 ms)
SELECT * FROM users WHERE email = 'alex@example.com';

What Happens Internally

The SQL query remains identical, but the execution plan generated by the PostgreSQL planner changes completely:

1. Instead of reading thousands of 8 KB heap pages sequentially, PostgreSQL traverses 3–4 levels of the B-Tree index.
2. The leaf page of the B-Tree contains the indexed value and a physical pointer to the table row called a TID (Tuple Identifier), formatted as (block_number, tuple_offset).
3. The engine uses this TID to directly read the specific row from the table heap.

When to Create an Index

• Columns frequently filtered in WHERE clauses.
• Foreign Key columns and join keys used in JOIN ... ON conditions.
• Columns used for sorting (ORDER BY) or grouping (GROUP BY).
• Tables with thousands to millions of rows where queries filter down to a small fraction of the total rows.

---

🟡 Middle Level

How It Works: Physical Storage & Pointers

In PostgreSQL, table data is stored in physical 8 KB blocks called Heap Pages. Rows (tuples) inside a heap page are unordered. An index stores column values in a strictly sorted order, accompanied by an ItemPointerData (TID) pointing to the physical location of the row in the heap:

B-Tree Leaf Page:
┌──────────────────────────────┬──────────────────────────────┐
│  Key: 'alex@example.com'     │  Key: 'bob@example.com'      │
│  TID: (Block 42, Offset 3)   │  TID: (Block 115, Offset 1)  │
└──────────────┬───────────────┴──────────────┬───────────────┘
               │                              │
               ▼                              ▼
      Heap Page 42, Row 3           Heap Page 115, Row 1

Index Types in PostgreSQL

Index Type	Primary Use Cases	Supported Operators	Internal Mechanism
B-Tree	General-purpose (default), unique constraints, ranges	<, <=, =, >=, >, BETWEEN, IN, IS NULL	Balanced multi-way search tree (Lehman & Yao B-link tree)
Hash	Exact equality lookups only	=	Bucket array using 32-bit hash codes (WAL-logged since PG 10)
GIN (Generalized Inverted)	Arrays, JSONB documents, Full-Text Search	@>, ?, ?&, ?\|, @@	Inverted index mapping individual elements/lexemes to posting lists of TIDs
GiST (Generalized Search Tree)	Geometric objects, PostGIS geospatial, ranges	&&, @>, <@, <<, >>, <-> (k-NN)	Lossy/lossless balanced tree for multidimensional data
BRIN (Block Range Index)	Massive append-only tables (>50 GB) with physical data correlation	<, <=, =, >=, >, BETWEEN	Stores summary metadata (min/max values) for physical block ranges (default 128 pages)

Scan Types in PostgreSQL Query Plans

Understanding scan types in EXPLAIN (ANALYZE, BUFFERS) is essential for query tuning:

1. Sequential Scan (Seq Scan): Reads the heap sequentially block by block. Chosen for small tables (< 1,000 rows) or low-selectivity queries fetching a large percentage (> 15–20%) of the table.
2. Index Scan: Traverses the B-Tree index to find matching TIDs, then performs random I/O reads on the heap pages to fetch the full row tuples.
3. Index Only Scan: Satisfies the query entirely from the index leaf pages without accessing heap pages at all. Prerequisite: All requested columns must exist in the index, AND the heap page must be marked as all-visible in the Visibility Map.
4. Bitmap Index Scan:
   • Phase 1 (Bitmap Index Scan): Gathers all matching TIDs from the index and constructs an in-memory bitmap array of physical heap block IDs.
   • Phase 2 (Bitmap Heap Scan): Reads the heap blocks in physical sequential disk order, eliminating chaotic random disk seeks. Ideal when hundreds or thousands of matching rows are scattered across the table.

Common Pitfalls and Anti-Patterns

1. Applying Functions or Expressions to Indexed Columns:

   -- ❌ Standard B-Tree on 'created_at' CANNOT be used!
   SELECT * FROM orders WHERE DATE(created_at) = '2026-01-01';
   
   -- ✅ Solution 1: Rewrite as a sargable range query
   SELECT * FROM orders 
   WHERE created_at >= '2026-01-01 00:00:00' AND created_at < '2026-01-02 00:00:00';
   
   -- ✅ Solution 2: Create an Expression Index
   CREATE INDEX idx_orders_created_date ON orders(DATE(created_at));
   

2. Querying Trailing Columns of a Composite Index:

   -- Composite index on (company_id, user_role)
   CREATE INDEX idx_users_comp_role ON users(company_id, user_role);
   
   -- ❌ Cannot effectively use the B-Tree index (violates leftmost prefix rule)
   SELECT * FROM users WHERE user_role = 'ADMIN';
   

3. Over-Indexing (Write Amplification): Every INSERT, UPDATE, and DELETE must modify every index on the table. Adding 10 indexes to an OLTP table will turn a 1 ms insert into a 15 ms disk-bound bottleneck.

---

🔴 Senior Level

B-Tree Internal Architecture: Lehman & Yao B-Link Algorithm

PostgreSQL implements the Lehman & Yao high-concurrency B-link tree algorithm:

• Right-Link Pointers (P_NEXT): Every internal and leaf page maintains a horizontal pointer to its right sibling on the same tree level.
• High Key: Every page defines an upper boundary value representing the maximum key allowed on that page.
• Lock-Free Downward Traversal: Concurrent readers do not take locks on entire parent subtrees. A reader traverses downward taking short-term shared buffer content latches, releasing them immediately. If an ongoing concurrent insert splits a leaf page while a reader is in-flight, the reader detects that its search key exceeds the page’s High Key and follows the P_NEXT link rightward without backtracking to the root.

Page Structure:
Meta-Page (Block 0: Root pointer, Fastroot, B-tree version)
   └── Root Page
        ├── Internal Pages (Keys + Pointers to lower pages)
        └── Leaf Pages (Keys + TIDs to Heap + High Key + P_NEXT / P_PREV)

Advanced Indexing Strategies

1. Covering Indexes (INCLUDE Clause)

Introduced in PostgreSQL 11, the INCLUDE clause appends non-key payload attributes directly to the leaf pages of a B-Tree:

CREATE INDEX idx_orders_customer_include 
ON orders(customer_id) INCLUDE (total_amount, status);

• Benefit: Queries filtering on customer_id and projecting total_amount perform an Index Only Scan.
• Advantage over Composite Index: The included columns do not participate in B-Tree sorting or root/internal page routing, keeping upper B-Tree pages compact and cache-friendly.

2. Partial Indexes

Index only a relevant subset of rows to save 90%+ storage and write I/O:

-- Indexes only unprocessed queue records
CREATE INDEX idx_orders_unprocessed 
ON orders(created_at) 
WHERE status = 'PENDING';

The query planner automatically uses this index whenever the query includes WHERE status = 'PENDING'.

3. Production Online Index Creation (CREATE INDEX CONCURRENTLY)

Standard CREATE INDEX acquires a table-level SHARE lock, blocking all concurrent INSERT, UPDATE, and DELETE operations until completion.

-- Non-blocking index build for 24/7 highload environments
CREATE INDEX CONCURRENTLY idx_users_email ON users(email);

Operational Invariants:

1. Cannot run inside an explicit transaction block (BEGIN ... COMMIT).
2. Performs two separate table scans and waits for all active concurrent writing transactions to terminate.
3. If interrupted (timeout, deadlocks, manual cancel), it leaves behind an INVALID index that consumes disk space and write I/O without being used by the planner.

MVCC and HOT (Heap-Only Tuple) Optimization

In PostgreSQL MVCC, an UPDATE writes a brand new row version into the table heap. Normally, every index on that table must also be updated to point to the new tuple’s TID.

HOT (Heap-Only Tuple) optimization completely eliminates index updates during modifications:

• Condition 1: The UPDATE statement does not modify any column referenced by any index on the table.
• Condition 2: The new tuple version physically fits inside the same 8 KB heap page as the old tuple version.
• Mechanism: The old tuple’s header is transformed into a pointer (t_ctid) leading directly to the new tuple on the same page. Index leaf nodes continue pointing to the original TID.

[!WARNING] Adding an unnecessary index on a frequently updated column (e.g., last_active_at) permanently breaks HOT optimization for that table, causing severe write amplification, WAL bloat, and runaway index degradation.

---

4 Tricky Questions

1. Under what circumstances will an Index Only Scan still read from the heap table?

Answer:
When the Visibility Map (VM) indicates that the targeted heap page is not marked as all-visible.
In PostgreSQL, index tuples do not store MVCC transaction metadata (xmin, xmax). To ensure a tuple returned by an index is visible to the current transaction snapshot, PostgreSQL checks the Visibility Map. If the bit corresponding to that heap block is 0 (meaning dead tuples or concurrent uncommitted modifications exist), the engine must fetch the heap page to verify visibility. Frequent VACUUM runs keep the Visibility Map up to date, ensuring true index-only execution.

2. How does CREATE INDEX CONCURRENTLY work internally, and how do you remediate a failed attempt?

Answer:
CREATE INDEX CONCURRENTLY executes in three distinct phases:

1. Phase 1: Creates the catalog entry and builds the index structure while registering it with concurrent transactions so they begin maintaining it for new writes.
2. Phase 2 (Scan 1): Scans the heap table and populates the index with existing data, then waits for all transactions that started before this scan to finish.
3. Phase 3 (Scan 2): Performs a second scan to catch any changes made during the build, updates missing entries, and waits for prior transactions to terminate before marking the index valid (indisvalid = true).

If it fails or is killed, it remains in the catalog with indisvalid = false. It continues to consume write I/O on every insert but is never chosen by the planner.
Remediation: Detect and drop invalid indexes:

SELECT indexrelid::regclass, indrelid::regclass FROM pg_index WHERE NOT indisvalid;
DROP INDEX CONCURRENTLY idx_users_email; -- Clean up invalid index

3. Why does the query planner choose a Seq Scan even when an index exists and the query filters by WHERE id = 42?

Answer:
There are four common root causes:

1. Small Table Size: If the table occupies only a few pages (e.g., < 100 pages), seq_page_cost (default 1.0) is much lower than random_page_cost (default 4.0) plus index navigation overhead. Sequential reading is physically faster.
2. Stale Statistics: If ANALYZE has not run recently, pg_statistic may report an incorrect row count or skewed distribution, leading the cost-based optimizer to overestimate index costs.
3. Data Type Mismatch (Implicit Cast): If the column is BIGINT and the parameter is passed as NUMERIC or VARCHAR, PostgreSQL inserts an implicit type conversion function WHERE CAST(id AS numeric) = 42, which invalidates the standard B-Tree index on id.
4. Low Selectivity: If id has low cardinality (or duplicate values) and the condition matches a large percentage (> 15–25%) of the table, sequential scanning is cheaper.

4. What is B-Tree index bloat, and why is VACUUM insufficient to reclaim index disk space?

Answer:
When rows are updated or randomly inserted, B-Tree leaf pages split. If subsequent updates or deletes create dead tuples, standard VACUUM removes the index pointers and marks space within the 8 KB index pages as reusable for future keys of that same range. However, standard VACUUM cannot merge or rebalance B-Tree pages, nor does it return allocated disk pages to the operating system. Over time, pages remain 30–50% empty, leading to index bloat.
Solution: Use REINDEX TABLE CONCURRENTLY <table_name> or REINDEX INDEX CONCURRENTLY <index_name> to build a completely fresh, fully packed B-Tree index online without locking readers or writers.

---

🎯 Interview Cheat Sheet

Core Fundamentals

• Purpose: Accelerate read queries (SELECT) at the expense of disk space and write latency (INSERT, UPDATE, DELETE).
• Default Index: B-Tree (balanced multi-way search tree supporting equality, ranges, sorting, and prefix matches).
• 5 PostgreSQL Index Types: B-Tree (universal), Hash (strict equality), GIN (arrays/JSONB/full-text), GiST (spatial/ranges/k-NN), BRIN (large append-only time series).
• 4 Scan Types: Seq Scan (full table), Index Scan (index + random heap lookup), Index Only Scan (index only via Visibility Map), Bitmap Index Scan (index -> memory bitmap -> sorted physical heap reads).

Critical Operational Practices

• Production Index Creation: Always use CREATE INDEX CONCURRENTLY to avoid blocking writes (ACCESS EXCLUSIVE lock).
• HOT Updates (Heap-Only Tuples): Updates that do not touch indexed columns and fit on the same heap page avoid index writes entirely. Never index frequently updated timestamps unless absolutely necessary.
• Index Only Scans Depend on VACUUM: Index Only Scan requires the Visibility Map to mark pages as all-visible; unvacuumed tables degrade to reading heap pages.
• Covering Indexes: Use CREATE INDEX ... ON orders(customer_id) INCLUDE (total_amount) to serve queries via Index Only Scan without bloating the B-Tree navigation keys.

Red Flags (What NOT to Say)

• ❌ “We should add an index to every column just in case.” (Index maintenance severely degrades write throughput and breaks HOT updates).
• ❌ “Regular VACUUM shrinks bloated indexes and frees disk space to the OS.” (VACUUM only frees space internally; only REINDEX CONCURRENTLY compacts and rebuilds the physical index).
• ❌ “Hash indexes are always faster than B-Trees for equality searches.” (Modern B-Trees with deduplication perform equality lookups with comparable speed, while supporting ranges, unique constraints, and index-only scans).

Related Topics

• How does B-tree index work — Internal Lehman-Yao B-link tree algorithms
• What is a composite index — Multi-column indexing and leftmost prefix rule
• How does MVCC work in PostgreSQL — Multi-version concurrency control and tuple versions
• What is VACUUM in PostgreSQL — Visibility maps and dead tuple reclamation
• How to optimize slow queries — Execution plans and performance tuning with EXPLAIN