Introduction
An index is an auxiliary data structure that lets a database engine locate rows without scanning every row in a table. Without an index, a query like WHERE email = 'x@y.com' forces a sequential scan of the entire table, comparing every row's email column. As tables grow to millions of rows, this becomes prohibitively slow. Most relational databases implement indexes using a balanced tree structure called a B-tree (or a variant, B+tree), which keeps data sorted and allows logarithmic-time search, insert, and delete operations.
Cricket analogy: Without a stats index, finding every century Sachin Tendulkar scored means scanning every ball of his career; a well-built index lets a scorer jump straight to those innings the way a B-tree jumps straight to matching rows.
Syntax
-- Create a basic single-column index
CREATE INDEX idx_users_email ON users (email);
-- Create a unique index (enforces uniqueness + speeds lookups)
CREATE UNIQUE INDEX idx_users_username ON users (username);
-- Drop an index
DROP INDEX idx_users_email;
-- Inspect how the optimizer uses an index
EXPLAIN SELECT * FROM users WHERE email = 'x@y.com';Explanation
A B-tree index stores indexed column values in sorted order across a tree of pages. Each internal node holds pointers that partition the key range into subranges, and leaf nodes hold the actual key values along with a pointer (or row identifier) back to the full row in the table's heap storage. Because the tree is balanced, the number of page reads needed to find a value grows only logarithmically with table size — a table of a million rows might need only 3-4 page reads to locate a match, compared to potentially a million comparisons for a full scan. The tradeoff is that every INSERT, UPDATE, or DELETE that touches an indexed column must also update the index's tree structure, which means writes become slower and each index consumes additional disk space. A table with five indexes pays that maintenance cost on every write, five times over.
Cricket analogy: A tournament's wagon-wheel database sorts shots into a tree of overs and innings; finding Rohit Sharma's sixes takes only a few page lookups instead of scanning a decade's balls, but recording every new shot means updating that sorted tree too, five times over if five separate indexes exist.
Example
CREATE TABLE orders (
order_id INT PRIMARY KEY,
customer_id INT NOT NULL,
status VARCHAR(20),
created_at TIMESTAMP
);
-- Without this index, filtering by customer_id scans the whole table
CREATE INDEX idx_orders_customer_id ON orders (customer_id);
-- This query can now use the B-tree to jump straight to matching rows
SELECT * FROM orders WHERE customer_id = 4821;Analysis
The primary key on order_id is automatically backed by a unique index (and in many engines defines the physical clustering of the table). The added index on customer_id lets the optimizer choose an index scan instead of a sequential scan when filtering on that column, turning an O(n) operation into roughly O(log n). However, because orders is likely a write-heavy table (new orders inserted constantly), each new index added to it should be justified by a real, frequent query pattern — indexes that are rarely used by queries still cost write throughput and storage on every insert.
Cricket analogy: The unique match_id index lets scorers instantly retrieve any specific match, while an added index on team_id turns 'show all India matches' into a fast lookup instead of a full-season scan; but since matches are logged constantly, each extra index should be justified by real query demand, not added just in case.
Key Takeaways
- Indexes let the engine avoid full table scans by using a sorted, balanced tree (B-tree) structure.
- Lookups on an indexed column are roughly O(log n) instead of O(n) for a sequential scan.
- Every index must be updated on INSERT, UPDATE, and DELETE, which slows writes and uses extra storage.
- A primary key typically creates an implicit unique index automatically.
- Indexes should be added deliberately based on actual query patterns, not applied to every column.
Practice what you learned
1. What data structure do most relational databases use to implement standard indexes?
2. Why do indexes slow down write operations like INSERT and UPDATE?
3. Without an index on a filtered column, how does the database typically find matching rows?
4. What is typically true about a table's primary key?
Was this page helpful?
You May Also Like
Query Optimization Basics
Foundational techniques for writing queries the optimizer can execute efficiently.
Execution Plans
How to read EXPLAIN output to understand and diagnose how the database will run a query.
Indexing Strategies and Tradeoffs
How to choose composite index column order, use covering indexes, and know when not to index.