Database Indexing and Query Performance: B-Trees, Query Plans, and Trade-offs

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.

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.”

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.

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>;

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.

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.

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.

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?”

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.

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 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.

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.

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.