Database Indexing and Query Optimization Strategies in PostgreSQL and MySQL

Slow web applications are rarely limited by CPU processing speed. In the vast majority of performance audits, system lag is caused by unindexed database queries performing full table sequential scans across millions of rows.

Understanding how database engines store, search, and traverse B-Tree index structures is the most effective skill for any backend engineer.

---

1. Anatomy of a B-Tree Index

When a table has no index, finding a single row requires reading every data page from disk—an O(N) sequential scan.

A B-Tree (Balanced Tree) index organizes column values into a balanced hierarchical tree with logarithmic search complexity O(log N):

• Root Node -> Branch Nodes -> Leaf Nodes.
• Leaf nodes store the indexed column values along with a direct pointer (TID in PostgreSQL, Primary Key in MySQL InnoDB) to the physical row.

---

2. Composite Index Column Ordering: The Leftmost Prefix Rule

When querying against multiple columns (e.g. WHERE status = 'ACTIVE' AND created_at >= '2026-01-01'), creating two separate single-column indexes is inefficient. You should create a Composite Index.

However, the order of columns in a composite index is critical:

-- Correct ordering: Equality columns first, range columns second
CREATE INDEX idx_orders_status_date ON orders (status, created_at);

The Golden Rule:

1. Place columns used for Equality (=) comparisons first.
2. Place columns used for Range (>, <, BETWEEN) or sorting (ORDER BY) last.

If you reverse the order to (created_at, status), the database can filter on date range, but cannot effectively use the second column for equality lookup within the B-Tree.

---

3. Reading Execution Plans with EXPLAIN ANALYZE

Never guess whether a query is optimized. Always run EXPLAIN (ANALYZE, BUFFERS):

EXPLAIN ANALYZE
SELECT id, customer_name, total_amount 
FROM orders 
WHERE status = 'PENDING' 
ORDER BY created_at DESC 
LIMIT 20;

Watch for two key indicators:

• Seq Scan (Sequential Scan) on large tables: Indicates missing indexes.
• Index Scan / Index Only Scan: The database navigates directly to matching rows using the B-Tree without touching unneeded pages.

```

---