Indexes in SQL
Overview
An index in SQL is an auxiliary data structure—most commonly a self-balancing B-Tree (Balanced Tree)—that allows the database engine to locate specific rows in $O(\log N)$ time rather than scanning every single row in the table ($O(N)$ full table scan). While indexes drastically accelerate SELECT, JOIN, and ORDER BY operations, they introduce storage overhead and write amplification because every INSERT, UPDATE, and DELETE must synchronize the underlying index trees.
What You Will Learn
In this lesson, you will master:
- B-Tree Index Architecture: Root, branch, and leaf page hierarchy.
- Clustered vs Non-Clustered Indexes: Physical row ordering vs secondary pointer lookups.
- Index Seek vs Index Scan: Why the query planner chooses an index seek over a scan.
- Composite Indexes & The Leftmost Prefix Rule: Optimizing multi-column filters.
- Covering Indexes: Utilizing
INCLUDEcolumns to eliminate expensive heap / bookmark lookups. - Write Amplification: Balancing read acceleration against write latency.
B-Tree Index Architecture
When you create a standard B-Tree index, the database arranges the indexed column values in sorted order across disk pages:
[ Root Page: 100 | 500 ]
/ | \
[ Branch: 1..99 ] [ Branch: 100..499 ] [ Branch: 500..999 ]
/ | \
[ Leaf Pages: Keys + Row Pointer to Physical Data Table ]
When searching for WHERE user_id = 245, the database navigates the root page $\rightarrow$ branch page $\rightarrow$ leaf page in just 3 disk I/O operations, regardless of whether the table has 10,000 or 100,000,000 rows.
Clustered vs Non-Clustered (Secondary) Indexes
| Property | Clustered Index | Non-Clustered (Secondary) Index |
| :--- | :--- | :--- |
| Physical Storage | The leaf pages are the actual data rows of the table | Leaf pages contain the indexed key + a Row Pointer |
| Quantity Allowed | Only 1 per table (data can only be physically sorted one way) | Multiple (dozens) allowed per table |
| Default Assignment | Automatically created on PRIMARY KEY in MySQL InnoDB & SQL Server | Created with CREATE INDEX |
| Lookup Mechanic | Direct retrieval from leaf node | Traverses index tree, then performs a Bookmark / Heap Lookup to fetch remaining columns |
Composite Indexes & The Leftmost Prefix Rule
A composite index indexes multiple columns together:
CREATE INDEX idx_orders_customer_date ON orders(customer_id, order_date);
The database sorts the index first by customer_id, and then by order_date within each customer. Under the Leftmost Prefix Rule:
-- 1. Uses Index Seek (Leftmost column customer_id present) -> OPTIMAL
SELECT * FROM orders WHERE customer_id = 42;
-- 2. Uses Index Seek (Both prefix columns present) -> OPTIMAL
SELECT * FROM orders WHERE customer_id = 42 AND order_date >= '2026-01-01';
-- 3. CANNOT use Index Seek (Leftmost column customer_id MISSING!) -> Table Scan
SELECT * FROM orders WHERE order_date >= '2026-01-01';
Prefix Order Matters
An index on (A, B) can satisfy queries on WHERE A = 1 and WHERE A = 1 AND B = 2, but it cannot accelerate queries that filter only on WHERE B = 2.
Covering Indexes & The INCLUDE Clause
When a query requests columns not present in the secondary index, the engine must perform a slow secondary disk lookup (Key Lookup or Bookmark Lookup) back to the clustered table.
A Covering Index contains all columns requested by the query. In PostgreSQL and SQL Server, you can append unindexed columns to leaf nodes using INCLUDE:
-- Query to optimize:
-- SELECT order_date, total_amount FROM orders WHERE customer_id = 42;
-- Covering Index: Index key is customer_id; payload columns stored in leaf nodes
CREATE INDEX idx_orders_cust_covering
ON orders (customer_id)
INCLUDE (order_date, total_amount);
Because the index itself contains customer_id, order_date, and total_amount, the database engine satisfies the query entirely from the index (Index-Only Scan), completely bypassing table disk lookups!
Partial & Expression Indexes (PostgreSQL)
-- 1. Partial Index: Index only active records (Keeps index tiny and fast)
CREATE INDEX idx_unprocessed_jobs ON job_queue (created_at)
WHERE status = 'pending';
-- 2. Expression / Functional Index: Index calculated values
CREATE INDEX idx_users_lower_email ON users (LOWER(email));
-- Accelerates: WHERE LOWER(email) = 'alice@example.com'
Common Mistakes & Gotchas
- Wrapping Indexed Columns in Functions (Non-Sargable Queries):
sql
-- BAD: Invalidates index because function must run on every row SELECT * FROM users WHERE YEAR(created_at) = 2026; -- GOOD: Sargable range query utilizes index seek SELECT * FROM users WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'; - Over-Indexing: Every index added slows down
INSERT,UPDATE, andDELETEoperations because the engine must update every B-Tree concurrently inside write transactions. - Indexing Low-Cardinality Columns: Indexing a boolean flag (
is_active) or gender column where values are split 50/50 is typically useless. The query optimizer will skip the index and choose a table scan because traversing the index offers no selectivity advantage.
Interview Perspective
SQL Interview Question: What is the difference between an Index Seek and an Index Scan, and what makes a query sargable?
Key Talking Points for Candidates:
- Index Seek: The engine traverses the B-Tree directly from root to leaf to pinpoint specific boundary keys ($O(\log N)$).
- Index Scan: The engine reads every leaf page of the index sequentially ($O(N)$), usually when filters are not sargable or the query lacks the leftmost prefix column.
- Sargability (Search Argument Able): A query predicate is sargable if it allows the engine to leverage an index seek without modifying column values (e.g. avoiding functions like
SUBSTRING(name, 1, 3) = 'ABC'or leading wildcards likeLIKE '%term').
Interactive Practice Challenge
DataPlayArena Technical Editorial Board
Curated & maintained by enterprise data platform engineers with 10+ years in distributed systems.
Runtime Verification Standards: Every code example, query, and architecture diagram in this tutorial is compiled and verified against real runtimes (Apache Spark 3.5, Python 3.11, PostgreSQL, and DuckDB). If you spot any errata or want to suggest improvements, please submit feedback.