Database Indexing

Why Indexing Matters

An index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space.

Without an index, the database must perform a Full Table Scan ($O(N)$), checking every row to find matches. A balanced-tree lookup can locate a key in $O(\log N)$ comparisons, but returning K matches still requires work proportional to K; the planner may prefer a scan.

B-Tree Structure

Most relational databases (PostgreSQL, MySQL, Oracle) use B-Trees (specifically B+ Trees) for indexing.

Key Characteristics

• Balanced: All leaf nodes are at the same depth.
• Sorted: Data is kept capable of range queries.
• High Fanout: Nodes have many children (unlike binary trees), minimizing disk I/O.

Clustered vs Non-Clustered

Understanding this distinction is the single most important concept in physical database design.

[!TIP] Primary Keys are clustered indexes by default in MySQL (InnoDB) and SQL Server. In PostgreSQL, all indexes are secondary (heap table organization), though CLUSTER command exists.

Composite Indexes

An index on multiple columns: CREATE INDEX idx_name_age ON users(last_name, age).

Leftmost Prefix Rule

Leading equality conditions usually narrow a B-tree scan most effectively. This is a planning rule of thumb, not an absolute prohibition on later columns: skip scans and index filtering depend on the database version and data distribution.

Given Index on (A, B, C):

Visualizing Multi-Column Sort

Think of a phone book. It's sorted by Last Name, then First Name.

• Finding "Smith" is easy.
• Finding "John" (without knowing Last Name) is impossible without scanning everything.

Covering Indexes

A super-optimization. If the index contains all the columns needed for the query, the DB doesn't need to look up the table row at all!

Query: SELECT age FROM users WHERE last_name = 'Smith' Index: (last_name, age)

The index has the requested columns. In PostgreSQL, an index-only scan may still visit heap pages to check visibility unless the visibility map permits skipping them.

Indexing Strategies

1. Cardinality

Index columns with high cardinality (many unique values like UserID, Email). Low cardinality alone is not a reason to reject an index. A rare status value, a partial index, or a useful composite index can be selective even when a column has few distinct values.

2. Is NULL

B-Trees handle NULLs differently per DB.

• Oracle B-tree indexes omit entries where all indexed key columns are NULL; composite and function-based cases require care.
• PostgreSQL/MySQL/SQL Server: NULLs are indexed.

3. Write Penalty

Inserts and deletes generally add index maintenance; updates may affect relevant indexes or benefit from engine-specific optimizations such as PostgreSQL HOT.

• Too many indexes = Slow writes.
• Too few indexes = Slow reads.

Code Examples

SQL: Analyzing Execution Plans

-- 1. Create Table
CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    email VARCHAR(255),
    age INT,
    created_at TIMESTAMP
);

-- 2. Populate 1M rows...

-- 3. Analyze Query without Index
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'test@example.com';
-- Result: Seq Scan on users (cost=0.00..18334.00 rows=1)
-- Inspect actual timing and buffer reads on your data; this is not a benchmark result.

-- 4. Create Index
CREATE INDEX idx_email ON users(email);

-- 5. Analyze Again
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'test@example.com';
-- Result: Index Scan using idx_email on users
-- Compare measured execution time, heap fetches, and buffer reads.

Hash Index (Key-Value)

Good for equality checks (=), useless for ranges (>, <). Structure: Hash Table. $O(1)$ lookup.

CREATE INDEX idx_session ON sessions USING HASH (session_id);

Interview Tips 💡

• "How does a B-Tree work?" — Explain "Balanced, Sorted, High Fanout". Differentiate from Binary Tree (depth).
• "What is the difference between Clustered and Non-Clustered?" — Clustered IS the table. Non-clustered points to the table.
• "What is a Composite Index?" — Explain the Leftmost Prefix Rule.
• "Why not index every column?" — Write amplification. Storage cost.
• "LSM Tree vs B-Tree?" — Compare page updates with buffered LSM writes and compaction. Read/write performance depends on access patterns and storage configuration.

Related Concepts

• LSM Trees
• SQL vs NoSQL
• Write Ahead Log (WAL)

Sources and a design check

PostgreSQL multicolumn indexes covers leading columns and skip scans; index-only scans explains heap visibility checks. Compare plans before and after indexing using the same data and cache state, then measure the write penalty as well.