Why Database Indexes Speed Up Queries
Photo: Mathews Jumba / Pexels
A database index is a separate, sorted data structure that lets a database engine locate matching rows without reading every row in a table. Without one, a query becomes a full table scan: the database reads every row, in order, checking each against the filter. With an index built on a B-tree (a self-balancing, branching sorted structure), that same lookup can drop from millions of comparisons to a handful, the same way a phone book lets you jump to "Smith" instead of reading every name from "Aaronson" onward.
That speedup is not free. Every index a table carries has to be updated on every insert, update, and delete, and it consumes its own chunk of disk and memory. Understanding why indexes work, and what they cost, is the difference between a database that scales cleanly to millions of rows and one that grinds to a crawl under its own writes. This piece walks through the actual mechanics: the tree structure underneath, why the math favors it so heavily, what happens on the write side, when the query planner ignores an index anyway, and how to decide which columns actually deserve one.
The problem indexes exist to solve
Picture a users table with 10 million rows and a query like SELECT * FROM users WHERE email = 'jane@example.com'. Without any index on the email column, the database engine has exactly one option: scan the table from the first row to the last, comparing each row's email value against the target string. This is called a full table scan, and its cost scales linearly with table size — twice the rows, twice the work, on average.
For a table with a handful of rows, a full scan is fine; the overhead of even checking whether an index exists can exceed the cost of just reading everything. But linear scaling breaks down fast. A table scan against 10,000 rows might take a few milliseconds. The same scan against 10 million rows takes roughly a thousand times longer, because the database has to physically read a thousand times more data off disk or out of memory, in the worst case touching every single row before it can conclude which ones matched.
This is the concrete problem an index solves: it trades a query's dependence on table size for a dependence on the depth of a search structure, which grows far more slowly than the row count does. A production application serving a login page cannot afford a query whose latency scales with how many users have ever signed up. An index is what keeps that latency roughly flat as the table grows from thousands of rows to billions.
The B-tree: the structure behind most indexes
Most relational databases, including PostgreSQL and MySQL, implement their default indexes using a B-tree (short for "balanced tree"). PostgreSQL's own documentation describes it as a standard multi-way balanced tree structure where every leaf page sits the same distance from the root, which is what "balanced" means in this context — no branch of the tree is deeper or shallower than any other (PostgreSQL 17 Documentation, §64.1, postgresql.org).
Think of a B-tree like the organizational chart of a large company built specifically for finding one employee fast. At the top sits a small root node holding a handful of reference values. Each of those values points down to a child node covering a range of the underlying data, and each of those children points further down, until you reach the leaf nodes that hold pointers to actual table rows. To find a value, the database compares it against the root's reference points, follows the one pointer whose range contains the target, and repeats at the next level down. In three or four steps, it has narrowed 10 million candidate rows down to one page holding the actual match.
This is fundamentally the same trick as a "guess the number between one and a million" game, where each guess halves the remaining range. If you always guess the midpoint, you can find any number in that range in about 20 guesses, not a million. A B-tree does something structurally similar but with a branching factor much wider than two, since each node holds many keys, which is why real B-tree indexes on multi-million-row tables typically resolve in three to five levels rather than twenty.
Why the math favors a tree so heavily
A full table scan of a table with n rows takes, in the worst case, on the order of n comparisons; double the rows, double the work. A B-tree lookup takes on the order of log(n) comparisons, where the log's base is the tree's branching factor. Because logarithmic growth is so much flatter than linear growth, the gap between the two widens dramatically as tables grow: a table 100 times larger might need only two or three additional tree levels to search, while the equivalent full scan needs 100 times the comparisons. This is the core reason B-tree indexes are treated as the default choice across relational database engines rather than a niche optimization.
Why indexes aren't free
An index is not a strictly positive addition to a database; it is a tradeoff, and treating it as a free performance upgrade is one of the most common mistakes newer backend developers make. Every time a row is inserted, updated, or deleted, the database has to update not just the table's underlying storage but every index built on that table, in the same operation, before the write is considered complete.
Concretely: a table with five indexes turns a single INSERT into six write operations under the hood, one to the table's heap storage and one to each index structure, since each B-tree has to re-sort itself to keep the new value in the correct position and, when a node fills up, split that node to preserve the tree's balance. On a table that receives thousands of writes per second, like an events or logging table, adding indexes casually can visibly slow ingestion, because the database is now doing proportionally more work per write than per read.
Indexes also consume storage, and this cost is easy to underestimate. An index on a large text column, for instance, duplicates a sorted copy of that column's data (or a derived form of it) inside the index structure, separate from the table itself. A table with several indexes on wide columns can end up with an index footprint that rivals or exceeds the size of the actual table data, which matters both for disk cost and for how much of the working set fits in memory, where lookups are fast, versus disk, where they are not.
This is why experienced database engineers treat indexing as a targeted decision rather than a default. They index the columns that are searched, filtered, or joined on frequently enough that the read speedup clearly outweighs the added write cost and storage, and they deliberately leave less-queried columns unindexed.
Beyond B-trees: other index structures worth knowing
A B-tree is the default, but it is not the only structure a database can build an index on, and matching the structure to the query pattern matters. A hash index stores a hashed representation of each value, letting the database jump directly to a matching bucket for an exact-match lookup, in principle even faster than a B-tree traversal for that one specific case. MySQL's own documentation is explicit about the tradeoff: hash indexes cannot support range queries or ORDER BY, and they generally require the full key value rather than a prefix, because a hash discards the original ordering of the data (MySQL 8.0 Reference Manual, §10.3.9, dev.mysql.com).
A full-text index solves a different problem entirely: searching for words or phrases inside large text fields, like a blog post body or a product description, where a plain B-tree comparison against the whole string would be useless. Full-text indexes typically build an inverted index, mapping individual words back to the rows that contain them, which is closer in spirit to how a search engine works than how a phone book works.
A composite index, as noted above, spans multiple columns in a defined order and is built specifically to serve queries that filter or sort on that same combination of columns together. Choosing the right structure, and the right column order for composite indexes, is arguably more consequential to real-world query performance than the decision to index at all.
| Index type | Underlying structure | Best for | Weak for |
|---|---|---|---|
| B-tree | Balanced, sorted branching tree | Equality, range (>, <, BETWEEN), sorting, prefix matching |
Full-text search inside long strings |
| Hash | Hashed key to bucket lookup | Exact-match equality lookups only | Range queries, ORDER BY, partial-key search |
| Full-text | Inverted index (word to row map) | Searching words/phrases inside text columns | Exact structured equality on non-text columns |
| Composite | Multi-column B-tree, ordered | Queries filtering/sorting on the same column combination | Queries using only a non-leading column from the index |
Matching index type to query pattern matters as much as deciding whether to index a column at all — a hash index on a column that also needs range queries will silently fail to help half your workload.
Watching an index work: reading an EXPLAIN plan
Everything above is easier to trust once you can actually see it happen. Every major relational database ships a command that shows exactly which path the query planner chose and how much work it estimates that path will take: EXPLAIN in PostgreSQL and MySQL, with EXPLAIN ANALYZE adding real, measured execution numbers on top of the planner's estimates (PostgreSQL 17 Documentation, §14.1, postgresql.org).
Picture that same users table with 10 million rows, no index on email, and this query: EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'jane@example.com';. The plan comes back looking something like this, using the general shape and node labels PostgreSQL actually emits for a sequential scan (Crunchy Data, "How to Read Postgres EXPLAIN," crunchydata.com):
Seq Scan on users (cost=0.00..214730.00 rows=1 width=245)
(actual time=612.114..612.116 rows=1 loops=1)
Filter: (email = 'jane@example.com'::text)
Rows Removed by Filter: 9999999
Planning Time: 0.112 ms
Execution Time: 612.140 ms
Read this top to bottom. Seq Scan on users names the strategy: the planner is reading the table start to finish. Rows Removed by Filter: 9999999 is the tell — the database checked nearly every one of the 10 million rows and threw almost all of them away, because it had no faster way to find the one row that matched. Execution Time at the bottom is the actual measured wall-clock cost of that scan, not an estimate.
Now add an index — CREATE INDEX idx_users_email ON users(email); — and run the identical query again. The plan changes shape entirely:
Index Scan using idx_users_email on users
(cost=0.43..8.45 rows=1 width=245)
(actual time=0.031..0.033 rows=1 loops=1)
Index Cond: (email = 'jane@example.com'::text)
Planning Time: 0.098 ms
Execution Time: 0.052 ms
The node label switches to Index Scan, and Index Cond replaces Filter, meaning the database used the B-tree to jump straight to the matching row rather than filtering every row it touched. The cost estimate drops from a five-digit number to single digits, and the measured Execution Time falls from hundreds of milliseconds to a fraction of one. That gap, roughly what a full scan versus a B-tree lookup predicts mathematically, is not a hypothetical; it is exactly the kind of before-and-after difference EXPLAIN ANALYZE is designed to surface on a real, running database.
MySQL's equivalent, EXPLAIN (with EXPLAIN ANALYZE available since MySQL 8.0.18), reports the same underlying story through different column names: a type of ALL signals a full table scan, while a type of ref or const signals an index lookup, and the rows column estimates how many rows the engine expects to examine before returning a result (MySQL 8.0 Reference Manual, §8.8.2, dev.mysql.com). Whichever database is in use, the habit is the same: run EXPLAIN before assuming an index helped, because the plan, not intuition, is the actual source of truth for what the query planner did.
How to decide what to index in practice
Reading a query plan tells you what happened after the fact. Deciding what to index in the first place is a smaller, more disciplined set of questions worth asking before adding any index to a production table.
- Start from actual slow queries, not guesses. Use
EXPLAIN ANALYZE, a slow-query log, or an application performance monitoring tool to find queries that are genuinely expensive, rather than indexing columns that merely "seem important." - Index columns that appear in
WHERE,JOIN, andORDER BYclauses of those slow queries — these are exactly the column roles a B-tree index is built to accelerate, as covered above. - Check column order on composite indexes against the query's leading filter. An index on
(status, created_at)only helps a query that filters onstatusfirst; matching the index's column order to how queries actually filter is often more impactful than adding another single-column index. - Be more conservative on write-heavy tables. A table that logs thousands of inserts per second pays the write cost of every index on every single insert; each additional index is a direct tax on that table's ingestion throughput, so only add indexes there that a measured, recurring query genuinely needs.
- Skip low-cardinality columns like boolean flags or small enum-style fields, since an index that doesn't meaningfully narrow the row set gives the planner little reason to use it over a scan.
- Re-check periodically, not just at launch. A column's access pattern can shift as an application grows; an index that was essential at one scale can become dead weight later, and one that wasn't needed at launch can become necessary once a table crosses a size threshold where scans stop being cheap.
- When in doubt, measure, don't assume. Add the index in a staging environment, re-run
EXPLAIN ANALYZEon the target query, and confirm the plan actually switched from a scan to an index lookup before shipping the change to production.
When an index actually gets used
Not every column benefits equally from being indexed, and understanding which ones do is what separates useful indexing from wasted overhead.
- Columns in a
WHEREclause used to filter rows, like searching for a specific customer ID or email address, benefit heavily from an index on that column, since it converts an n-row scan into a small handful of tree traversals. - Columns used in
JOINconditions between two tables benefit substantially, because the database has to match rows between tables efficiently, and doing that with a full scan on the joined side for every row in the driving table would multiply the cost. - Columns used in
ORDER BYcan sometimes use an index to retrieve rows already in sorted order, avoiding a separate, computationally expensive sort step that would otherwise happen after the rows are fetched. - Low-cardinality columns, ones with few distinct values like a boolean
is_activeflag, often see little to no benefit from indexing, since an index doesn't meaningfully narrow the search when roughly half the table shares the same value; the database may ignore the index and scan anyway. - Columns rarely referenced in filters or joins gain nothing from an index and only add write and storage overhead, which is why blanket "index everything" policies tend to backfire on write-heavy tables.
How does a database decide whether to actually use an available index?
A component called the query planner (or query optimizer) evaluates the estimated cost of every available execution path for a query, including full scans and each usable index, and picks whichever it estimates will be cheapest, based on statistics it keeps about table size and data distribution.
What people get wrong about indexes
A common misconception is that adding more indexes always makes a database faster. In practice, over-indexing a write-heavy table can slow it down significantly, since every insert, update, or delete now has to modify multiple index structures in addition to the base table, and the query planner also spends measurable time evaluating which of many available indexes, if any, is worth using for a given query.
Another mistake is assuming an index will automatically be used just because it technically exists on a relevant column. Query planners sometimes choose a full table scan over an available index if the table is small enough that scanning is actually cheaper, since the overhead of tree traversal and the extra step of fetching the full row from the table's separate storage can exceed the cost of just reading the whole (small) table sequentially. A planner may also skip an index if a query's filter conditions don't align with how the index is structured, such as searching for a substring in the middle of a value when the index is built for prefix matching, or filtering on the second column of a composite index without filtering on the first.
A third, subtler mistake is assuming index cost is only about write speed. Storage and memory pressure matter too: an index that rarely gets used but occupies gigabytes of disk space, and competes for the same memory cache the database uses to hold frequently accessed data, can degrade performance even for queries that never touch it, simply by crowding out more useful data from cache.
Why might a database ignore an available index on a large table?
Even on a large table, the planner can decide a full scan beats an index if the query is expected to match a large fraction of the rows anyway, since fetching each matching row individually via the index (a series of scattered reads) can cost more in aggregate than one sequential read of the whole table.
The takeaway
A database index trades additional write cost and storage space for dramatically faster reads, using a sorted, branching B-tree structure (or, for narrower use cases, a hash or full-text structure) to let the database narrow down matching rows in a handful of steps instead of scanning an entire table row by row. The underlying math is what makes this worth it at scale: logarithmic growth versus linear growth means the gap between an indexed lookup and a full scan widens, not narrows, as a table grows.
The skill isn't indexing everything, it's identifying which columns are searched, filtered, or joined on often enough that the read speedup justifies the ongoing write and storage cost, and matching the index structure to the actual query pattern rather than defaulting to whatever the database offers first. Get that balance right, and query latency stays roughly flat as a table grows from thousands of rows to hundreds of millions; get it wrong in either direction, either no indexes or too many, and either reads or writes end up paying for it.
Read next:
- How Rate Limiting Protects APIs
- How CDN Caching Speeds Up Websites
- What Server Side Rendering Solves
FAQ
Q: What data structure do most database indexes use?
Most relational databases, including PostgreSQL and MySQL, use a B-tree (balanced tree) by default, a sorted, branching structure that lets the database narrow down to matching rows in a small, predictable number of steps instead of scanning every row (PostgreSQL Documentation, postgresql.org).
Q: Do indexes slow down write operations?
Yes. Every insert, update, or delete has to update each index on the affected table in addition to the table data itself, so tables with many indexes see measurably slower write performance than tables with few or none, since each write becomes multiple underlying operations.
Q: Should every column in a table be indexed?
No. Indexing every column adds unnecessary write overhead and storage cost without proportional benefit. Columns that are frequently searched, filtered, or joined on benefit most, while low-cardinality columns with few distinct values often see little to no benefit from an index.
Q: Why might a database ignore an available index?
The query planner may choose a full table scan if the table is small enough that scanning is actually faster, if the query is expected to match a large fraction of the rows, or if the query's filter conditions don't align with how the index is structured, such as searching for a substring in the middle of a value or filtering on a non-leading column of a composite index.
Q: What is the difference between a B-tree index and a hash index?
A B-tree index keeps values sorted and supports range queries, sorting, and prefix matching, while a hash index maps values directly to storage locations for fast exact-match lookups but cannot support range queries or ORDER BY (MySQL Reference Manual, dev.mysql.com).
Q: Does column order matter in a composite index?
Yes. A composite index built on multiple columns is only fully useful for queries that filter on those columns starting from the leftmost column in the index definition; a query that filters only on a later column in the list generally cannot use the index efficiently.
Follow new articles
Add SciHub101 to your feed reader to see new science and technology stories.
About the Author
SciHub101 is an independent science and technology publication founded and edited by Buğra Sözeri, a software engineer and app developer based in Türkiye. AI tools assist with drafting and research. Source documentation in the existing archive is uneven, and articles are being reviewed and corrected. The Editorial Team byline identifies editorial responsibility; it does not certify specialist or independent human review. Where we compare products, anything built by our own team is labelled as such — see the editorial guidelines and About page for how corrections and disclosures work.
Related Articles
How Progressive Web Apps Work
How progressive web apps work: the web app manifest, service worker lifecycle, caching strategies, install rules, and where iOS and Android still differ.