The Core Idea
A Shortcut Structure Built on Top of Your Table
Without an index, finding rows matching a condition (like WHERE email = 'x@example.com') requires a full table scan — checking every single row in the table one by one, an O(n) operation regardless of how selective the condition is. An index is a separate, additional data structure — typically a B-tree — built on one or more columns, that lets the database jump almost directly to matching rows instead of scanning everything.
This is conceptually identical to a book's index: instead of reading every page to find every mention of a specific topic, you check the index at the back, which tells you exactly which page numbers to jump to — at the cost of the book needing extra pages to maintain that index in the first place.
💡 Memory Trick
Picture a library with a card catalog. Without it, finding every book by a specific author means walking every single aisle, checking every single spine. With the catalog, you look up the author's name once (fast, because the catalog is alphabetically sorted) and it tells you exactly which shelves to walk to. The catalog itself takes real effort to keep updated every time a book is added or removed — that upkeep cost is the trade-off for the dramatic search speedup.
The Trade-off
Faster Reads, Slower Writes
1
Reads Get Faster — Often O(log n)
A B-tree index turns a search that would otherwise be O(n) (full table scan) into O(log n), since B-trees are specifically structured to support fast search, similar in spirit to a balanced binary search tree but optimized for disk-based storage with wide, shallow branching.
2
Writes Get Slower
Every INSERT, UPDATE, or DELETE that touches an indexed column must also update the index itself, not just the underlying table row. More indexes on a table means more index-maintenance work on every write — this is the direct cost side of the trade-off, and it's why indexing every column 'just in case' is a bad default strategy.
3
Extra Storage Space
An index is a genuinely separate data structure stored alongside the table, so it consumes additional disk space proportional to the size of the indexed column(s) and the number of rows — for a table with many indexes, the indexes combined can sometimes take up as much space as the table itself.
When to Index
Matching Indexes to Actual Query Patterns
Good candidates for indexing are columns frequently used in WHERE clauses, JOIN conditions, or ORDER BY clauses — especially columns with high selectivity (many distinct values, so an index meaningfully narrows down the search, unlike a boolean column with only two possible values, where an index provides little benefit). Primary keys and foreign keys are almost always indexed by default in most database systems.
Poor candidates for indexing include columns rarely used in filtering conditions, tables that are written to far more often than they're read from (where the write-slowdown cost outweighs any read benefit), and low-selectivity columns where the index barely narrows the search space at all. The right approach is to index based on your application's actual, measured query patterns — not to index every column defensively.
🖥️ Applied Scenario
Your application's 'find user by email' login query has become noticeably slow as your users table has grown past 5 million rows.
1
You confirm the query runs WHERE email = ? with no index on the email column, meaning every login attempt triggers a full table scan across all 5 million rows.
2
You add a B-tree index on the email column, since email is highly selective (nearly every value is unique) and is used in a WHERE clause on essentially every login request.
3
You verify that write-heavy operations (like bulk user imports) still perform acceptably despite the added index-maintenance overhead, since user creation is far less frequent than login attempts in your application.
4
Conclusion: the login query drops from an O(n) full scan to an O(log n) index lookup, and because email lookups vastly outnumber user-creation writes in this application, the read speedup easily outweighs the added write cost.
📌 Exam Application
Exam questions frequently ask you to identify whether a given column is a good indexing candidate, expecting you to reference selectivity (how many distinct values exist) and the read/write ratio of the actual query workload. You may also be asked to explain, conceptually, why an index speeds up SELECT queries but slows down INSERT/UPDATE/DELETE operations.
⚠️ Most Common Database Indexes Mistakes
The most common mistake is indexing every column 'to be safe' — each additional index adds real write overhead and storage cost on every modification to that table, and a table with far too many indexes can end up with worse overall write performance without providing meaningful additional read benefit beyond what the most useful indexes already give. Another frequent error is indexing a low-selectivity column (like a boolean 'is_active' flag with only two possible values) expecting a large speedup — with so few distinct values, an index narrows the search very little, and the database's query planner may even choose to ignore such an index and fall back to a full scan anyway.
✓ Quick Self-Test
Can you explain, using the library card-catalog analogy, why an index speeds up reads but slows down writes? Given a described table and its most common queries, can you identify which columns would make good indexing candidates and explain why, referencing selectivity and query frequency?
→
← All Databases Lessons