B-Tree Index Internals

How B-Tree indexes work internally and when they collapse to full table scans

⏱ 14 min📊 Diagram

A database without indexes is like a library without a card catalog — every query scans every row. B-Tree indexes transform O(N) full scans into O(log N) tree traversals, which means finding 1 row in 10 million takes ~23 steps instead of 10 million.

Key Concepts

B-Tree Structure

A balanced tree where each node stores sorted keys and pointers. Leaf nodes contain actual row references. Depth stays bounded at O(log N) through automatic rebalancing on insert/delete.

Range Scan Advantage

Unlike hash indexes, B-Trees support range queries (BETWEEN, <, >, ORDER BY) because leaf nodes are linked in sorted order — you can walk the list without re-traversing the tree.

Write Overhead Cost

Every INSERT, UPDATE, DELETE must update all indexes on the table. Each extra index adds ~10-15% write overhead. Never index columns you don't query on.

Index Selectivity

An index on a boolean column (true/false) is nearly useless — the DB may prefer a full scan. High-cardinality columns (email, UUID) have maximum index benefit.

B-Tree Traversal: Finding Value '42'

Understanding EXPLAIN ANALYZE

The only way to know if your index is actually being used is to read the query execution plan. `EXPLAIN ANALYZE` actually runs the query and shows exactly how the database fetched the data.

**Seq Scan (Sequential Scan):** The database completely ignored your index and read every row in the table. Usually happens on small tables, low cardinality columns, or using `SELECT *` without restrictive `WHERE` clauses.
**Index Scan:** The database traversed the B-Tree index to find the row pointers, then immediately jumped to the heap (table) to fetch the row data.
**Index Only Scan:** The absolute fastest query type. The index contained all the requested columns, so the database didn't even need to touch the main table (heap).
**Bitmap Heap Scan:** Used for queries that match many rows. It first scans the index to build a memory bitmap of matching blocks, then sequentially reads those blocks from the table to optimize disk I/O.

Index Types Comparison

Index Type	Supports	Best For
B-Tree (default)	=, <, >, BETWEEN, LIKE 'abc%', ORDER BY	Most queries — the universal default
Hash Index	= only (exact match)	Equality lookups on high-cardinality columns
GIN	Array contains, JSONB, full-text search	PostgreSQL JSONB queries, text search
BRIN	Range on physically ordered columns	Timestamps on append-only tables (cheapest storage)
Partial Index	Filtered subset of rows	Indexes WHERE status='ACTIVE' only — tiny, fast

PostgreSQL DDL Examples

indexes.sqlsql
-- Standard B-Tree index on high-cardinality column
CREATE INDEX idx_orders_customer_id ON orders(customer_id);

-- Composite index — LEFT-MOST PREFIX RULE applies
-- Covers queries on (tenant_id), (tenant_id, status), (tenant_id, status, created_at)
-- Does NOT cover queries starting with status alone
CREATE INDEX idx_orders_composite
ON orders (tenant_id, status, created_at DESC);

-- Covering index — SELECT query answered from index alone (no table lookup)
CREATE INDEX idx_orders_covering
ON orders (customer_id, status)
INCLUDE (total_amount, created_at);  -- INCLUDE = stored but not searchable

-- Partial index — only indexes rows we actually query
CREATE INDEX idx_active_users ON users(email)
WHERE status = 'ACTIVE' AND deleted_at IS NULL;

-- Check index usage with EXPLAIN ANALYZE
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT id, status, total_amount
FROM orders
WHERE tenant_id = 1001
  AND status = 'PENDING'
ORDER BY created_at DESC
LIMIT 20;

💡

Senior Architect Insight: The Composite Index Left-Most Prefix Rule is the most misunderstood indexing concept. An index on (a, b, c) is automatically also an index on (a) and (a, b) — but NOT on (b) or (c) alone. Design your composite indexes with the most selective, most commonly filtered column first.

PreviousSaga Pattern (Choreography & Orchestration)

Next LessonComposite & Covering Indexes