Database Indexing and Query Performance: B-Trees, Query Plans, and Trade-offs
Learn how indexes turn scans into targeted lookups, how B-trees and composite indexes shape access paths, and why every index adds write and operational cost. This reference works through a 200-million-row orders table, shows how to interpret execution plans, diagnoses N+1 and implicit-cast failures, and provides a framework for defending index choices at scale.
Why Sequential Scans Become Production Incidents
A filter over 10 rows can scan the whole table so quickly that the cost disappears into measurement noise. The same access pattern over 100 million rows examines 10 million times as many rows. That is why a query that feels instant in staging can become a production incident: the data volume changed, but the way the application asks for data did not.
Databases read table data in pages, typically 8–16 KB each. At the same row layout, using 8 KB pages requires 2x as many page reads as using 16 KB pages. A full table scan must read the pages needed to cover the table, whether or not the filter matches the row on each page. The I/O volume—not the apparent simplicity of the WHERE clause—is what dominates as the table grows. Query performance is therefore how fast and efficiently the database executes a query, shaped by the indexes available, the query shape, the data volume, and the execution plan.
Design a platform-scale distributed rate limiter55 min
Critique: find the failure modes in a given design45 min
An unindexed filter amplifies a small lookup into a scan across the entire table.
Compare the same filter's two access patterns: the unindexed path touches every table page, while the indexed path targets only pages containing matching rows.
PostgreSQL’s documentation describes the intended benefit directly: “An index allows the database server to find and retrieve specific rows much faster than it could do without an index,” while also noting that indexes add overhead to the database system. Indexing is the use of a separate data structure—most commonly a B-tree—to let the database jump to matching rows instead of scanning every row.
How a B-tree Turns a Filter into a Lookup
A B-tree is a self-balancing tree organized around the indexed key. Its root directs the search to an internal node; the internal node narrows it again; and a leaf stores the indexed column value together with a pointer—such as a row ID or primary key—to the actual table row. Because the tree stays balanced, the path from root to leaf remains short as the table grows.
For a point lookup such as last_name = 'Smith', the database compares the search value with separators in the root, follows the matching branch to an internal node, and then follows that node to the leaf containing Smith. The lookup performs O(log N) comparisons rather than checking every row. Even on a huge table, the path typically requires only 3–4 disk reads because upper tree levels remain cached; the database repeatedly narrows the search instead of loading the table's pages.
The same initial seek makes a range query efficient. For a range such as last_name LIKE 'S%', the database first traverses root → internal node → the first matching leaf. It then walks the linked leaves in sorted order, collecting entries through the end of the S range. A point lookup stops after finding the matching leaf; a range lookup pays the seek once and then follows adjacent leaf entries.
The leaf pointer is what turns an index match into a row fetch: the index identifies candidate records, and the database uses those pointers to retrieve columns that are not stored in the index. If the requested result is contained in the index, the engine can avoid that table lookup with an index-only or covering scan. The index therefore changes the physical read path from “inspect every row” to “navigate the tree, then fetch only the matching records.”
CHECK YOUR UNDERSTANDING
Why does a `last_name LIKE 'S%'` query not need to restart at the root for every matching row?
SHOW ANSWERHIDE ANSWER
The database seeks once to the first matching leaf, then walks the leaves' sorted links until the range ends. The initial tree traversal finds the starting position; the linked leaf chain supplies the remaining entries.
Choosing the Columns: Selectivity, Prefixes, and Covering Indexes
Start with the values that prune
Index selectivity is the number of distinct indexed values relative to the total number of rows. High-cardinality columns such as user_id, email addresses, and timestamps usually prune the candidate set effectively: a lookup can narrow the scan to a small part of the index. A boolean or a status column with only three values usually does not justify a standalone index, because each value can still match a large fraction of the table. The question is not whether the database can use the index; it is whether the index eliminates enough rows to repay its storage and maintenance cost.
Treat composite order as part of the query contract
A composite index stores keys in lexicographic order: the first column groups entries, and the next column orders entries within each group. For an index on (a, b, c), the conventional leftmost-prefix rule supports predicates on (a), (a, b), and (a, b, c). A predicate on b or c alone does not match the conventional leftmost-prefix access pattern and may require scanning much of the index or a sequential table scan. Column order is therefore not interchangeable: put the column that your access path constrains first, then the column that narrows or orders the remaining range.
The SQL below makes the distinction concrete. The first query constrains user_id, the leftmost column. The second keeps that prefix and adds a created_at range. The third constrains only created_at; it may still be considered by a database planner in some circumstances, but it does not match the conventional leftmost-prefix access pattern.
sql
CREATE INDEX ON orders (user_id, created_at);
SELECT *
FROM orders
WHERE user_id = 42;
SELECT *
FROM orders
WHERE user_id = 42
AND created_at > <date>;
SELECT *
FROM orders
WHERE created_at > <date>;
The first two queries constrain the composite index's leftmost column; the final query filters only on created_at and does not match the conventional leftmost-prefix access pattern.
For (user_id, created_at), all rows for one user occupy a contiguous region, and timestamps are ordered inside that region. The database can seek to user 42, walk the created_at range in order, and stop after the required ten orders. A created_at-only search has no single user prefix to seek into, so it cannot select one equivalent contiguous region.
Use a covering index when the index has the whole answer
A covering index contains every column needed by a query: its filters, ordering columns, and returned values. The database can then answer from index entries without following their row pointers into the main table. That avoids the extra table access on a read-heavy path. For the orders query, (user_id, created_at) supplies the filter and ordering, but it is covering only if the selected output columns are also stored in the index. Otherwise it still uses the index to find and order candidate rows, then reads the base table for the missing values. This is a targeted optimization: adding output columns widens the index, so reach for it when the read path is important enough to justify the extra structure.
CHECK YOUR UNDERSTANDING
Given a composite index on `(country, city, zip_code)`, which predicates receive the conventional leftmost-prefix lookup: `country = 'US'`, `country = 'US' AND city = 'Boston'`, `city = 'Boston'`, or `zip_code = '02108'`? Explain why.
SHOW ANSWERHIDE ANSWER
The first two do: they constrain the first column, and the second also constrains the next column within that prefix. The city-only and zip-code-only predicates do not match the conventional leftmost prefix, because the index is grouped first by country; without that leading constraint, matching values are spread across the index rather than forming one directly searchable prefix.
The Write Path: Every Index Is Another Structure to Maintain
An indexed write has more than one destination. The database must write the row to the base table and keep every affected index synchronized. For an INSERT, that means adding the indexed value and its row pointer to each relevant B-tree. An UPDATE to an indexed column must adjust the corresponding index entry; a DELETE must remove the row’s entry from each affected index. The logical change is one application operation, but the storage work fans out across the base table and the indexes.
The fan-out repeats once for every index that the write affects. Add an index on customer_id, and an order insert now maintains the base table plus that index. Add another on created_at, and the same insert maintains a third structure. PlanetScale describes indexes as “data structures that exist in your database engine, outside of whatever table they work with”; each additional structure therefore brings its own maintenance work and storage. Updates that change indexed values can require the index entry to be repositioned so the tree remains ordered.
That is the central read/write exchange: an index reduces the work needed to find rows later, while writes affecting indexed columns also pay maintenance work to preserve the shortcut. PostgreSQL’s documentation states that “indexes also add overhead to the database system as a whole,” and PlanetScale notes that “They also make INSERT queries take longer.” The cost is easy to hide during schema design because reads and writes appear as separate requests, but they compete for the same database resources. Count the indexes touched by the write path, not just the query that benefits from them.
An indexed write is maintained in the base table and in every affected index.
Follow the single write as it fans out into the base table and each affected index; the extra branches are the write tax.
Worked Example: 200 Million Orders, One Customer Filter
Take an orders table and the query SELECT * WHERE customer_id = 42. With no index, the database has no shortcut: it examines all 200,000,000 rows to determine which ones match. Because databases read data in pages, typically 8–16 KB, the scan must load the pages needed to cover the full table. The exact page count depends on row width and page layout, so the row count is the reliable comparison here—not an invented I/O total.
The same access pattern is easy to miss in staging. On a 10-row table, a full scan examines only 10 rows, so the work feels instant. At production size, it examines 200,000,000 rows: 200,000,000 ÷ 10 = 20,000,000, or 20 million times more rows than the staging case. The query did not change; the data volume did. That is why an unindexed filter can pass small-environment testing and become a production incident.
Add an index on customer_id, and the database can use the index to find the matching row locations instead of testing every row. For this example, assume the lookup reads approximately 50 matching rows' worth of pages. The pruning effect is 200,000,000 ÷ 50 = 4,000,000: roughly four million times fewer rows examined than the unindexed scan. The exact number of pages still depends on how rows and index entries are laid out across 8–16 KB pages, but the scale of the reduction is already clear.
CHECK YOUR UNDERSTANDING
For `SELECT * WHERE customer_id = 42` on 200 million orders, what is the row-examination reduction if the index reaches approximately 50 matching rows' worth of pages?
SHOW ANSWERHIDE ANSWER
Compute 200,000,000 ÷ 50 = 4,000,000. The indexed path examines roughly four million times fewer rows, although the exact page count depends on row and page layout.
Indexing Is a Workload Decision, Not a Free Speedup
An index is a workload decision, not a universal accelerator. You are trading cheaper reads for more work on every write and for additional storage. The defensible question is not “can this index help one query?” but “does the read benefit justify its cost across the workload?”
Compare an index-backed read path with the write and storage costs that determine whether it belongs in the design.
Workload / strategy
Read effect
Write/storage cost
When to choose it
Read-focused access path: targeted B-tree index
Provides a more direct path to requested rows and reduces the amount of I/O required.
Adds overhead to the database system; inserts, updates, and deletes must write to the index as well as the table.
Choose it when a known, frequently used query benefits from finding specific rows rather than scanning the table.
Write-heavy table: several speculative indexes
Each index can provide a direct read path, but continuously adding indexes for slow queries can create duplicated or overlapping paths.
Every insert, update, and delete consumes more resources; index space can approach the size of the data, doubling table size.
Do not add speculatively. First determine how often each index will be used, measure its improvement, and check for similar indexes.
Write-optimized structure: an LSM-tree system
Use the structure when the workload prioritizes high-volume writes and analytics access patterns do not justify many secondary indexes.
Minimize secondary-index maintenance and storage by organizing the data around the write workload.
Choose it for write-heavy systems such as event ingestion and logging when a read-optimized B-tree design would impose too much write tax.
The first row is the normal read-optimized choice: create a targeted B-tree when a known, frequently used query needs to find a small set of rows. The second row is the common failure mode. Adding several indexes whenever a query is slow can create overlapping access paths, and writes affecting the indexed columns must maintain each affected index. Storage is not incidental: S9 describes a case where index space was almost as large as the data space, effectively doubling the table's size.
The condition that flips the decision is the read/write ratio and the access pattern. A targeted index is defensible when it serves a frequent, selective query and its improvement is measured. Five speculative indexes on a high-volume ingestion table are not: they impose write and storage costs before you know whether the future queries will use them. For analytics, organizing data around the read workload can make more sense than adding relational secondary indexes; S10 describes open table formats as letting the workload determine both data organization and auxiliary structures.
CHECK YOUR UNDERSTANDING
A high-volume event-ingestion system has five proposed indexes for future analytics queries. What should you challenge before approving them?
SHOW ANSWERHIDE ANSWER
Ask how often each index will be used, what measured read improvement it provides, whether indexes overlap, and what write and storage tax they add. If the workload is dominated by writes and the queries are speculative, minimize secondary indexes or choose a write-optimized structure instead.
When the Query Plan Betrays Your Assumptions
A query plan is the database’s explanation of how it will retrieve rows. EXPLAIN exposes that plan; in Postgres, EXPLAIN ANALYZE also executes the query so you can compare the estimates with what happened. Treat Seq Scan as the first red flag when you expected a selective index. Index Scan or Index Only Scan may be appropriate when the index matches the predicate and required columns.
The plan makes the failure concrete. For events, a plan showing Seq Scan on events (cost=0.00..94832.00 rows=2000000) says the database expects to scan 2 million rows. After adding an index on event_type, the example changes to Index Scan (cost=0.43..8.46 rows=3): the upper cost estimate drops from 94832.00 to 8.46, roughly 11,000x. That is not proof that production latency will improve by 11,000x—the estimates are not milliseconds—but it is strong evidence that the access path changed from broad scanning to selective lookup.
Do not stop at the word Index. An index can still return so many rows that the database must read a large part of the table. A low-cardinality predicate such as a boolean may match roughly half the rows, making an index only marginally better than scanning the table. Compare the estimated rows with the total table size, and check whether the plan uses Index Only Scan when the query can be answered from index entries alone.
Query shape can defeat an otherwise useful index. If a VARCHAR column is filtered with an integer literal, the database may need an implicit type cast; because the types do not match, it can abandon the index and perform a full scan. Make the predicate’s types match the column before tuning the index. Then inspect the plan again rather than assuming the index is being used.
N+1 is a different failure: it is query structure, not missing index coverage. Loading 100 posts in one query and then issuing one author query for each post produces 101 queries—101 times the query count of the initial load. An index may make each author lookup cheaper, but it cannot remove the 100 round trips or the extra query work. Restructure the read as a JOIN or a batch fetch so the authors are retrieved through one combined operation.
The same author lookup is either repeated 100 times or combined into one read.
Follow the fan-out from the posts query to 100 author queries, then compare it with the single JOIN or batch-fetch path: the defect is query count and structure, not simply index coverage.
CHECK YOUR UNDERSTANDING
A table has 50 million events, and `status` has only three possible values. Will adding an index on `status` necessarily help?
SHOW ANSWERHIDE ANSWER
No. Three values usually mean low selectivity: a status predicate may still match a large fraction of the 50 million rows, so the database may prefer a sequential scan or gain little from the index. Check the value distribution and the execution plan. Add the index only when the real workload filters narrowly enough, or when the chosen plan shows that its read benefit justifies its maintenance cost.
The Operational Risks of Adding Indexes
An index migration changes the write path even when it improves the target query. Every INSERT, UPDATE, or DELETE that affects the indexed columns must maintain the new structure. PostgreSQL’s documentation warns that indexes “add overhead to the database system as a whole,” and SQL Server guidance makes the mechanism explicit: writes must update the table and its existing indexes as well as each new index. On a write-heavy table, ten speculative indexes add maintenance work for each write that affects them, plus storage that future queries may never use.
The construction path is a separate production decision. An index build on a large table can block or degrade normal traffic; an online option can allow concurrent activity to continue. SQL Server's ONLINE option allows concurrent activity on the underlying data to continue while an index is created or rebuilt, although the operation still consumes resources. Account for the resources used by the build, its interaction with concurrent writes, and the possibility of a long-running or failed migration. Roll out the build deliberately, observe write latency and table health during construction, and validate that the resulting index serves a measured query before treating it as complete.
The post-deploy symptom is often easy to connect to the migration: write latency spikes immediately after four indexes are added, while read plans improve only for the queries those indexes support. The explanation is additional maintenance work on every subsequent write, not a mysterious regression in the application. Before accepting an index, measure how often it will be used, the improvement it provides, and whether an overlapping index already exists. Remove speculative or redundant structures rather than accumulating them whenever a new slow query appears.
At scale, separate the two risks in the rollout plan: the temporary impact of building the index and the permanent tax of maintaining it. Plan the build around availability requirements and concurrent activity, and keep a way to remove the index if its measured benefit is insufficient.
Building an index introduces a temporary construction risk, then leaves a permanent maintenance cost on the write path.
Follow the two build paths from the large-table scan: the online path preserves service with overhead, while the offline path risks locking or degrading the table before both converge on the permanent write-maintenance tax.
CHECK YOUR UNDERSTANDING
A senior engineer says, “Our write latency spiked after last night’s deploy.” You find that the migration added four indexes. How do you connect those facts?
SHOW ANSWERHIDE ANSWER
Each affected insert, update, or delete now has additional index-maintenance work. The four new structures can therefore raise write latency even if they improve selected read plans. Compare write latency before and after the migration, identify which writes touch the indexed columns, check whether the indexes are used and whether any overlap, and remove or roll back indexes whose read benefit does not justify their permanent write and storage cost.
How to Defend an Indexing Decision in a Design Review
Make the workload pay for the index
A defensible proposal starts with an access path, not with “indexes are good.” State the query shape, its selectivity, read/write mix, write rate, storage impact, and the execution plan you expect. Then name the trade-off: the index should reduce I/O for an important read, while every insert, update, or delete must maintain another structure. Ask how often the query runs, how many rows it returns, whether an existing index overlaps, and what fallback you will use if the measured plan does not meet the target.
Use these questions to justify an index before committing it to a design.
Design question
Evidence to request
Index consequence
Alternative
Query shape/selectivity
Frequently used queries, predicates, and data distribution; whether columns have many distinct data values
Target the queries that reduce I/O and return a small result set; avoid indexes on columns with many duplicate values
Use a filtered index for predictable, well-defined subsets
Read-write workload
Read/write mix, modification rate, throughput target, and the critical queries
Prefer a few narrow indexes for write-heavy OLTP; writes affecting indexed columns must also update the affected indexes
Use a clustered columnstore index for analytics or data warehousing workloads
Precomputation or denormalization
Whether the workload can organize the data itself or use auxiliary data structures for the required access path
Do not add an index when precomputed or denormalized data can answer the read directly
Use a read-optimized analytics path or a pre-sorted, precomputed feed
Build or rebuild with the ONLINE option when appropriate; validate that the index prevents substantial I/O rather than only a few page reads
Defer, narrow, or remove the index if its measured benefit does not justify its migration and maintenance cost
For a high-volume event-ingestion pipeline, challenge “add indexes on five columns for future analytics.” Which analytics queries exist now, and which predicates actually need selective lookups? What write throughput and storage tax can the ingestion path tolerate? If the workload is primarily analytical, organizing data around the analytical workload may be preferable to adding speculative secondary indexes to the ingestion table. The answer should include a migration strategy: how you will build or remove the index under concurrent activity, validate the I/O reduction, and roll back if the benefit is too small.
A Twitter-like feed makes the boundary clear. At moderate scale, an index on (author_id, created_at) can support reads organized around an author and time. At Twitter scale, however, the feed is a fan-out problem: pre-compute and cache the recipients’ feeds so the read path does not depend on the index alone sustaining the required read QPS. A strong design says when the indexed path stops being sufficient and names the replacement, rather than claiming that a larger or wider index will solve every scale problem.
CHECK YOUR UNDERSTANDING
In a high-volume event-ingestion pipeline, a teammate proposes indexes on five columns for future analytics queries. What trade-offs should you raise before accepting the design?
SHOW ANSWERHIDE ANSWER
Ask which concrete queries require each index, what predicates and data distribution they have, and whether they will substantially reduce I/O. Quantify the read/write mix, write rate, throughput target, storage impact, and maintenance cost: every insert, update, and delete must also maintain the indexes. Check for overlap with existing indexes and define how you will build, validate, and roll back the migration under concurrent activity. Finally, compare the indexes with a read-optimized analytics path, denormalized or precomputed data, or a pre-sorted feed. Keep only indexes whose measured read benefit justifies their write, storage, and operational costs.
KEY TAKEAWAYS
A B-tree narrows a lookup to a leaf range, then follows row pointers; a range query pays the initial seek once and walks adjacent leaves.
Composite indexes follow a conventional leftmost-prefix rule, so column order must match the access path; later-column predicates can still have planner-specific alternatives.
Indexes reduce read work but add storage and maintenance work to writes affecting indexed columns.
An execution plan must be judged by estimated rows and actual access patterns, not by the presence of an Index Scan label alone.
Choose indexes from measured workload needs, then account for build risk, permanent write cost, storage, overlap, and rollback or removal.