An index is not magic, it is a data structure with predictable math. Once you can see why a full table scan grows linearly while a B-tree lookup grows logarithmically, indexing stops being trial and error and becomes something you reason about. This is the deeper mechanics companion to our beginner guide to SQL indexes: read that first for the plain-language version, then use this to understand exactly what the engine does under the hood.
What this guide covers
- The problem: a full table scan is O(n)
- How a B-tree turns lookups into O(log n)
- Seek vs index scan vs table scan
- Reading EXPLAIN to see the index work
- Composite indexes and the leftmost-prefix rule
- Covering indexes and index-only scans
- Selectivity: why some columns help less
- The write cost and storage trade-off
- When an index is quietly ignored
The problem: a full table scan is O(n)
When you filter a table that has no useful index, the database has only one option: read every row and test each one against your WHERE clause. This is a full table scan (also called a sequential scan or seq scan). It is correct, it always works, and it is exactly as slow as it sounds. The cost grows in direct proportion to the number of rows, which is what computer scientists call O(n) complexity: double the table and you roughly double the work.
Consider a table of 10 million orders and a query that matches a single customer. Without an index, the engine reads all 10 million rows to return maybe 40 of them. It touches 250,000 times more data than it returns. On a small table this is invisible and even preferable, but as the row count climbs the scan turns a query that should take under a millisecond into one that takes seconds, and it gets steadily worse every month as the table grows.
-- with no index on customer_id, this reads the whole table
SELECT id, total FROM orders
WHERE customer_id = 4217;
-- 10,000,000 rows scanned to return 40 rowsThe number that matters is not the size of the result, it is the volume of data the engine had to move to produce it. An index attacks precisely that gap. Instead of reading everything and discarding almost all of it, the engine navigates directly to the rows that qualify. To see why the navigation is so cheap, we need to look at the structure that makes it possible.
How a B-tree turns lookups into O(log n)
The default index in every mainstream relational engine is the B-tree, technically a B+tree. It is a balanced, sorted tree of pages. A root page at the top holds separator keys that route a search toward the right child, internal pages repeat that routing, and the bottom level (the leaf level) holds every indexed key in sorted order along with a pointer to the full row. Because the tree is kept balanced as rows are inserted and deleted, every key sits at the same depth, so every lookup costs the same small number of page reads. For the formal definition and history, see the B-tree article on Wikipedia.
A concrete walkthrough
Say customer_id = 4217 and the index has a fan-out of about 200 keys per page, which is typical. The search does this:
Read the root page
Compare 4217 against the separator keys. It falls between the pointers for 4000 and 4500, so follow that one child pointer down.
Read one internal page
Narrow again, from a range of thousands of keys to a range of a few hundred, and follow the single matching pointer to a leaf.
Read the leaf page
The leaf holds 4217 in sorted order next to a pointer (or the row itself). Follow it to the row and you are done.
That is three page reads to find one row in a table of ten million. Each step multiplies the fan-out, so the tree only needs to be deep enough that fan-out raised to the depth exceeds the row count. With a fan-out near 200, three levels already address 8 million keys and four levels address well over a billion. This is O(log n) complexity: the cost grows with the logarithm of the row count, not the row count itself. Multiply the table by a thousand and the tree gains at most one level.
| Rows in table | Full scan reads (approx) | B-tree lookup reads |
|---|---|---|
| 1,000 | 1,000 | 2 |
| 1,000,000 | 1,000,000 | 3 |
| 10,000,000 | 10,000,000 | 3 to 4 |
| 1,000,000,000 | 1,000,000,000 | 4 to 5 |
Key idea: because a B-tree stays balanced and sorted, one structure serves equality lookups (= 4217), range scans (BETWEEN, >, <), anchored prefix matches (LIKE 'abc%'), and ORDER BY on the same columns. The sorted leaf level is what makes ranges and ordering nearly free.
Seek vs index scan vs table scan
Not every use of an index is equally fast, and plan output uses distinct words for distinct access methods. Learning to tell them apart is the difference between assuming an index helped and knowing it did.
| Access method | What the engine does | Cost |
|---|---|---|
| Index seek | Navigates the tree straight to a key or a narrow range, then reads only matching rows | Cheapest. What you want for selective filters |
| Index scan | Walks the whole index in order, reading every leaf entry | Cheaper than a table scan only when the index is narrower than the table, or when it supplies sort order |
| Table scan / seq scan | Reads every row of the table itself | Most expensive on a filtered large table; fine when you genuinely need most rows |
The vocabulary differs by engine. SQL Server and Oracle explicitly separate an index seek (jump to a range) from an index scan (walk the entire index), and seeing "index scan" there is a warning, not a win. PostgreSQL and MySQL use index scan more loosely to mean a range navigation. The point is the same everywhere: a targeted seek touches a handful of pages, while a scan of any kind touches the whole structure. The official PostgreSQL indexes documentation is a good reference for how these methods map to real operators.
Reading EXPLAIN to see the index work
You do not have to guess whether an index is used. EXPLAIN shows the plan the optimizer intends to run, with estimates only. EXPLAIN ANALYZE actually executes the query and reports real timings and real row counts beside the estimates, which is what you want when you are proving a change worked. Here is the same query before and after adding an index, with the row counts that tell the story.
EXPLAIN ANALYZE
SELECT id, total FROM orders
WHERE customer_id = 4217;Seq Scan on orders
(actual time=0.03..812.4 rows=40 loops=1)
Filter: (customer_id = 4217)
Rows Removed by Filter: 9999960
Execution Time: 815.2 msThe tell is Rows Removed by Filter: 9999960. The engine read nearly ten million rows and threw away all but 40. Now add the index and run the exact same statement.
Index Scan using ix_orders_cust on orders
(actual time=0.04..0.11 rows=40 loops=1)
Index Cond: (customer_id = 4217)
Execution Time: 0.19 msTwo things changed. The operator flipped from Seq Scan to Index Scan, and Rows Removed by Filter vanished because the index navigated straight to the 40 matching rows instead of filtering ten million. Execution time dropped from 815 ms to under a millisecond, a change of more than 4,000 times. When you read a plan, hunt first for a large Rows Removed by Filter or a big gap between estimated and actual rows: both point at an access method doing far more work than the result justifies. Our SQL performance tuning guide walks through reading fuller plans operator by operator.
Composite indexes and the leftmost-prefix rule
A composite (multi-column) index is keyed on several columns at once, and column order is the detail people get wrong most often. A B-tree on (a, b, c) is sorted by a first, then by b within each value of a, then by c within each pair. Think of a phone book sorted by last name, then first name: it is instantly useful if you know the last name, and useless if you know only the first name.
This is the leftmost-prefix rule. The index can serve any query that uses a leading prefix of its columns, and nothing else. An index on (a, b, c) helps filters on (a), on (a, b), and on (a, b, c), but it cannot help a filter on (b) alone or on (b, c), because those columns are not sorted independently of a.
-- equality column first, range/sort column last
CREATE INDEX ix_orders_cust_date
ON orders (customer_id, created_at);
-- pins one customer, then reads a contiguous date run,
-- and satisfies the ORDER BY with no separate sort
SELECT id, total FROM orders
WHERE customer_id = 4217
AND created_at >= '2026-01-01'
ORDER BY created_at;-- range column first: the equality can no longer pin a
-- single slice, so the index scans a wide range and refilters
CREATE INDEX ix_bad
ON orders (created_at, customer_id);The practical rule: put equality columns first, then the range or sort column last. The equality predicate pins the search to one narrow slice of the tree, and the range then reads a single contiguous run inside that slice. A brilliant free resource that goes deep on column order and much more is Use The Index, Luke, which is worth bookmarking. You can also browse worked patterns in our SQL indexes reference.
Covering indexes and index-only scans
Normally an index gets you to the right leaf entry, and then the engine follows the pointer back to the table to fetch the columns you actually selected. That extra hop is cheap per row but adds up across many rows. A covering index removes it entirely: if the index already contains every column the query needs, the engine answers from the index alone and never touches the table. Plans call this an index-only scan (PostgreSQL) or a covering seek.
You build one by including the returned columns in the index. SQL Server and PostgreSQL let you attach them as non-key payload with INCLUDE, so they ride along in the leaf without widening the searchable key.
-- key on the filter, INCLUDE the columns the query returns
CREATE INDEX ix_orders_cover
ON orders (customer_id)
INCLUDE (total, status, created_at);
-- answered from the index alone: no table lookup per row
SELECT total, status, created_at
FROM orders WHERE customer_id = 4217;Covering indexes are one of the highest-return tricks for read-heavy endpoints, but do not over-widen them: every included column enlarges the index on disk and adds to write cost, which we come to shortly. This is also a concrete reason to avoid SELECT *, since asking for columns the index does not carry forces the table lookup right back in.
Selectivity: why some columns help less
Selectivity is what decides whether an index is worth using at all. A highly selective column has many distinct values, so an equality lookup returns very few rows: think email address, user id, or order number. A low-selectivity column has few distinct values, so a lookup returns a large fraction of the table: think a boolean flag, a gender code, or a status with three possible values.
Here is the counterintuitive part. On a low-selectivity column the optimizer will often ignore an index you added, and it is usually right to. If a filter matches 40 percent of the table, using the index means doing millions of scattered, random-access fetches back into the table, which is slower than simply reading the whole table sequentially. Sequential reads are far cheaper than random ones, so past a threshold of roughly a few percent of the rows the scan wins. This is why an index you added "just in case" on a status flag sits unused: on that column, scanning is genuinely the faster plan.
Watch out: an unused index is not free. It still costs storage and slows every write, while never speeding a read. If the plan never chooses it, drop it. For a genuinely skewed column where only a rare value is queried (for example status = 'pending' out of mostly archived rows), a partial or filtered index over just that value gives you selectivity back without indexing the common case.
The write cost and storage trade-off
Indexes are not free lunches, they are a read-speed-for-write-speed trade. Every index is a second sorted structure that the engine must keep in step with the table. When you INSERT a row, every index on that table gains an entry, possibly splitting a full leaf page. Every DELETE removes those entries, and an UPDATE to an indexed column must move the entry to its new sorted position. Five indexes mean one insert becomes six write operations under the hood.
The chart above is representative, not a benchmark of your hardware, but the shape holds almost everywhere: the read gets thousands of times faster. The cost lives on the write side and on disk, and it is real but usually a good deal. The discipline is to index deliberately rather than reflexively:
- Index the columns you filter, join, and sort on, especially foreign keys, and stop there.
- Do not duplicate prefixes. If you have
(a, b, c)you rarely also need(a)or(a, b): the composite already serves those prefixes. - Drop indexes the optimizer never chooses. They tax every write for zero read benefit.
- Weigh write-heavy tables carefully. On a table that ingests thousands of rows per second, each extra index is a measurable throughput cost.
For the wider set of levers beyond indexing, our 15 SQL performance tuning tips and the hands-on performance tuning walkthrough put this in context.
When an index is quietly ignored
The most frustrating case is an index that exists but the plan refuses to use. Almost always the query itself has made the index unusable by wrapping, converting, or anchoring the column the wrong way. The engine can only use an index when the predicate is sargable (search argument able), which means the indexed column appears bare on one side of the comparison. Three patterns break that.
A function on the indexed column
-- wrapping the column hides its sorted value from the index
SELECT * FROM orders
WHERE YEAR(created_at) = 2026;-- rewrite as a range so the B-tree can seek
SELECT * FROM orders
WHERE created_at >= '2026-01-01'
AND created_at < '2027-01-01';Implicit type conversion
When you compare a column to a value of a different type, the engine converts one side to match. If it converts the column, the index is dead because the stored sorted values no longer match what it is comparing against. Comparing an indexed VARCHAR account number to a numeric literal is the classic trap.
-- account_no is VARCHAR; the engine casts the column to int
SELECT * FROM accounts WHERE account_no = 100457;-- match the literal's type to the column's type
SELECT * FROM accounts WHERE account_no = '100457';A leading wildcard
A B-tree is sorted left to right, so it can seek a known prefix but not a known suffix, exactly like a phone book cannot help you find everyone whose name ends in "son". LIKE 'WIDGET-%' uses the index; LIKE '%-2026' cannot and falls back to a full scan.
SELECT * FROM products
WHERE sku LIKE '%-2026'; -- leading % forces a scanSELECT * FROM products
WHERE sku LIKE 'WIDGET-%'; -- anchored prefix seeksIf you genuinely need suffix or substring search, that is a job for a full-text or trigram index rather than a plain B-tree. In every one of these cases the fix follows one principle: keep the indexed column bare on its side of the comparison, and move any function, cast, or wildcard onto the constant instead. Confirm it worked by re-running EXPLAIN and watching the operator flip from a scan to a seek.
That is the full mechanical picture: a scan is O(n), a B-tree lookup is O(log n), and everything else here is about giving the optimizer an index it can actually use and a query that lets it. To build these instincts hands-on across real plans and schemas, the SQL advanced course works through indexing and query rewrites end to end.