B-Tree Index Internals

Overview

PostgreSQL and MySQL default to B-Tree indexes for most column types. The tree has a root, internal branch nodes, and leaf nodes. Leaf nodes hold the indexed key value and a pointer (tuple ID / row ID) back to the actual heap row. An index scan navigates the tree then fetches heap pages; a sequential scan reads all heap pages. The optimizer chooses an index scan when selectivity is high enough that fewer pages are touched than in a sequential scan. Expression indexes on LOWER(email) or YEAR(created_at) let predicates match the function output. Partial indexes include only rows matching a WHERE clause, keeping the index small and fast for filtered lookups.

Creating Standard, Expression, and Partial Indexes

-- Standard single-column index on foreign key (always index FK columns)
CREATE INDEX idx_orders_user_id ON orders (user_id);

-- Composite index (covered in a separate concept)
CREATE INDEX idx_orders_status_created ON orders (status, created_at DESC);

-- Expression index: supports WHERE LOWER(email) = 'foo@bar.com'
CREATE INDEX idx_users_email_lower ON users (LOWER(email));
-- Query that benefits:
SELECT id, name FROM users WHERE LOWER(email) = 'alice@example.com';

-- Partial index: only active users (makes index far smaller)
CREATE INDEX idx_users_active ON users (email) WHERE status = 'active';
-- Benefits only queries that include WHERE status = 'active'
SELECT id, email FROM users WHERE status = 'active' AND email = 'x@y.com';

Index Scan vs Sequential Scan (EXPLAIN)

-- PostgreSQL EXPLAIN example
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, amount FROM orders WHERE user_id = 42;
-- Expected plan (user_id indexed):
-- Index Scan using idx_orders_user_id on orders
--   Index Cond: (user_id = 42)
--   Rows: 12  (estimated)  Actual rows: 11

-- Without the index the plan would show:
-- Seq Scan on orders
--   Filter: (user_id = 42)
--   Rows Removed by Filter: 98999

-- Index bloat: after many DELETE/UPDATE operations, run:
VACUUM ANALYZE orders;       -- PostgreSQL: reclaims dead tuples, updates stats
-- MySQL equivalent: OPTIMIZE TABLE orders;

Key Points to Remember

• 1B-Tree leaf nodes store key + heap pointer; the tree is traversed top-down then heap pages are fetched — called an index scan.
• 2The optimizer picks sequential scan over index scan when selectivity is low (reading most pages anyway) or the table is tiny.
• 3Expression indexes must syntactically match the WHERE clause expression exactly, including case and function call.
• 4Partial indexes carry fewer entries than full indexes, fit in cache better, and update faster — ideal for large tables with a small active subset.
• 5Index bloat grows after heavy DML; VACUUM ANALYZE (PostgreSQL) or OPTIMIZE TABLE (MySQL) reclaims space and refreshes statistics.
• 6Always index foreign key columns — unindexed FK columns cause sequential scans on every JOIN and ON DELETE CASCADE.