Beacon Robotics' employees table has grown past 50,000 rows. A query like WHERE email = 'x' used to return instantly, now it visibly pauses. Module 8 already covered CREATE INDEX's syntax, this module explains why that syntax actually makes a lookup fast, not just that it does.
Learning Objectives
- Define what a database index is, and why a lookup without one requires a full table scan.
- Explain how a B-tree index narrows a search from every row down to a handful of comparisons.
- Know the real difference between a clustered and a non-clustered index, and which databases have which.
No Index
Full table scan, every row checked
B-Tree Index
Rows sorted into a searchable tree
Index Seek
Walks the tree, not the table
Matching Rows
Only the rows that actually match
A Full Table Scan, the Default
Without an index, finding every employee with a given email means checking every single row in the table, one at a time, there's no other way to know which rows match. This is a full table scan, and its cost grows directly with the table's size: twice the rows means roughly twice the work, every time the query runs.
What a B-Tree Index Actually Is
A B-tree index is a balanced tree of the indexed column's values, kept sorted, with each leaf pointing back to the actual row. Searching it means descending the tree, comparing the search value against a handful of nodes at each level, and discarding whole branches that can't contain a match, instead of checking every row. That's the difference between roughly log(n) comparisons and n comparisons, the gap that makes a large table's lookup fast again.
A B-tree is the general-purpose default almost every relational database uses for CREATE INDEX. Some databases also offer other, more specialized index types for specific cases, outside this lesson's scope, a B-tree is the one to understand first.
Clustered vs Non-Clustered Indexes, by Database
| Database | How Table Data Relates to the Index |
|---|---|
| MySQL / MariaDB (InnoDB) | A clustered index always exists and is the primary key, table rows are physically stored in primary key order. Every other (secondary) index stores the primary key value as its pointer, not a raw physical address. |
| SQL Server | A clustered index is optional but common, and defaults to the PRIMARY KEY if one isn't chosen explicitly. A table with no clustered index at all is called a heap. Non-clustered indexes store a pointer to the row (the clustered key, or a row ID if the table is a heap). |
| PostgreSQL | No maintained clustered index at all. The CLUSTER command performs a one-time physical reorder, the very next INSERT starts breaking that order again. Every PostgreSQL index behaves like SQL Server's non-clustered kind: a separate structure pointing at the row's physical location. |
| Oracle | Default (heap-organized) tables behave like PostgreSQL's, a separate B-tree index pointing at a row's ROWID. Oracle also offers an explicit opt-in table type, Index-Organized Tables (IOTs), where the table's data is physically stored inside the primary key's B-tree itself, the real equivalent of MySQL's mandatory clustering. |
| SQLite | A normal table is physically ordered by its hidden rowid, similar in spirit to clustering, unless declared WITHOUT ROWID, in which case it's physically ordered by the PRIMARY KEY columns themselves instead. |
"Clustered" means the same general idea everywhere, table data physically ordered to match an index, but whether it happens automatically, by default, or only as an explicit opt-in is genuinely different per database, worth knowing before assuming SQL Server's or MySQL's behavior carries over.
The Cost of Every Index
- + Lookups and range scans on an indexed column go from scanning every row to walking a small tree.
- + An ORDER BY on an indexed column can often be satisfied directly from the index's own order, skipping a separate sort step.
- + A UNIQUE index enforces uniqueness, on top of speeding up lookups on that column.
- − Every INSERT, UPDATE, and DELETE has to update every index on that table too, not just the row's data.
- − Each index takes its own additional disk space, sometimes larger than the table itself for a wide composite index.
- − Too many indexes on a write-heavy table can slow writes down more than it ever speeds reads up.
When Not to Index
A small table doesn't need one, a full scan over a few hundred rows is already fast enough that an index adds maintenance overhead for no real benefit. Columns rarely used in a WHERE, JOIN, or ORDER BY clause aren't worth indexing either, an index that's never read still has to be maintained on every write.
Try It Yourself
Beacon Robotics frequently looks employees up by email during login. Write the index that would speed that lookup up, on MySQL.
CREATE INDEX idx_employees_email ON employees(email);
Frequently Asked Questions
Does adding a PRIMARY KEY or UNIQUE constraint automatically create an index for it?
Yes, every database covered in this course automatically creates an index behind a PRIMARY KEY and behind a UNIQUE constraint, specifically to enforce and speed up checking that rule.
Is a B-tree the only kind of index a database can build?
No, it's the general-purpose default everywhere, but PostgreSQL in particular also ships GiST, GIN, BRIN, and hash index types for specialized cases like full-text search or array containment, which are outside this lesson's scope.
Common Beginner Mistakes
Assuming more indexes is always better
Every index adds write overhead and storage, an index on a column no query ever filters, joins, or sorts by is pure cost with no benefit. Index what queries actually use, not every column that exists.
Assuming "clustered index" means the identical storage structure on every database
It doesn't, MySQL's InnoDB tables are always clustered by the primary key automatically, SQL Server makes it an explicit, optional choice, PostgreSQL has no maintained clustered index at all, and Oracle only clusters a table that's explicitly declared an Index-Organized Table.
Best Practices
- Index the columns a query actually uses in WHERE, JOIN, or ORDER BY, not every column on the table.
- Let PRIMARY KEY and UNIQUE constraints create their own index rather than adding a duplicate one manually.
- Measure before and after adding an index, don't just assume it helped.
Interview Questions
What's the difference between a clustered and a non-clustered index?
A clustered index means the table's actual row data is physically stored in that index's order, there can only be one, since a table's rows can only be physically ordered one way. A non-clustered index is a separate structure that points back to the row rather than containing it, a table can have many of these. Whether a table even has a clustered index, and whether it's automatic, by default, or opt-in, is genuinely different per database.
Why does adding an index speed up reads but slow down writes?
A read that filters on the indexed column can walk the B-tree instead of scanning every row, a direct speed win. A write (INSERT, UPDATE, or DELETE) has to keep every index on that table correctly sorted and up to date too, not just change the row's data, so the write cost scales with how many indexes exist on that table.
Summary
An index is a separate, sorted structure, a B-tree in almost every general-purpose case, that lets the database walk down to matching rows instead of scanning every one. Whether a table's data is physically clustered by that index, or stored separately from it, is a genuine difference between databases, not just terminology. Every index speeds up the reads it serves, and slows down every write to that table, there's a real cost on both sides.
What's Next?
The next lesson covers indexing more than one column at once, a composite index, and the real difference between a UNIQUE constraint and a UNIQUE index.
Ready to Practice SQL?
Write and run real SQL queries online, right in your browser, no install or signup required. Pick a playground based on which database you want to practice on.
Both open a third-party SQL playground in a new tab. External site terms and privacy policy apply.
Or try 50 SQL practice questions →