What is an index?

What is an index?

An index is a second copy of some of your data, kept sorted, with a pointer back to the row it came from. You create it once; the database maintains it forever, on every insert, update, and delete. In exchange, queries that filter or sort on those columns stop reading the whole table and start jumping straight to the rows they want.

The comparison everyone reaches for is the index at the back of a book, and it holds up well. The index is not the book. It is a smaller, alphabetised structure that exists only to tell you which page to turn to. It takes up extra paper, it has to be reprinted when the book changes, and it is worth every bit of that because the alternative is reading all 900 pages to find one mention.

An index does not make the database faster. It gives the engine a cheaper way to find rows - and it charges you for that on every single write.- the trade in one sentence

Everything in this article uses SQL Server and T-SQL, because that is the engine the rest of this path is built on. The concepts port almost unchanged to PostgreSQL, MySQL, and Oracle. The vocabulary shifts a little (Postgres says "index scan" where SQL Server says "index seek", and its default table is a heap rather than a clustered index), but the B-tree underneath is the same structure everywhere.

One boundary worth drawing now: this is about rowstore B-tree indexes, the kind you get from CREATE INDEX and the kind that serves transactional workloads. SQL Server also has columnstore indexes, which store data by column in compressed segments for analytical scans over hundreds of millions of rows, plus specialised full-text, spatial, and XML indexes. Those are different structures answering different questions, and none of the reasoning below applies to them unchanged.

The table without one

SQL Server does not read rows from disk. It reads pages: fixed 8 KB blocks, each holding as many rows as will fit. A row of roughly 50 bytes packs about 150 to a page. A table of 12 million such rows is around 80,000 pages, or 640 MB.

Now run this against that table with no index on CustomerId:

The engine has no way of knowing where customer 4172's rows are, or even whether there are any, so it reads every page in the table and checks every row. That is a scan. It returns the right answer, and it costs 79,412 page reads to return twelve rows.

SET STATISTICS IO ON is the honest measure here, not the clock. Wall-clock time on a warm cache lies to you: the second run of the same scan is fast because the pages are already in memory, and it is still reading all of them. Logical reads count the pages touched regardless of where they came from, so it is the number that actually moves when you fix the problem.

Inside a B-tree

Create an index on CustomerId and the engine builds a tree. At the bottom - the leaf level - sit all the index keys in sorted order. Above that, one or more intermediate levels hold ranges: "keys 1 to 4000 are on that page, 4001 to 8000 on that one". At the top, a single root page covers the whole set.

Two properties make this useful. First, the tree is balanced: every leaf page is exactly the same distance from the root, so no key is more expensive to find than any other. Second, it is wide: each 8 KB page holds hundreds of key entries, so depth grows logarithmically. Millions of rows fit in three or four levels; billions fit in five or six.

Finding a row is then one page read per level. Start at the root, pick the range that contains your key, read that page, repeat until you hit the leaf. Three or four reads instead of 79,412. That is a seek, and the entire discipline of indexing is about arranging for the engine to be able to do one.

The numbers are worth internalising, because they explain why indexing feels like magic. With a few hundred entries per page, one level covers hundreds of rows, two levels covers tens of thousands, three covers tens of millions, and four covers billions. Growing a table by a factor of a thousand adds roughly one page read to a seek. That is what logarithmic means in practice, and it is why the same index design holds up as a table grows for years.

Strictly speaking SQL Server uses a B+ tree: the upper levels carry only keys for navigation, all the actual entries live at the leaf, and leaf pages hold pointers to their neighbours. Everyone says B-tree, including Microsoft's own documentation, and the distinction only matters when you want to know why range scans are cheap.

Because the leaf level is sorted and its pages are linked to their neighbours, two more things come free. Range predicates (WHERE OrderDate >= '20260101') become "seek to the start, then walk forward". And an ORDER BY that matches the index key order needs no sort at all, because the data is already in that order on disk.

Clustered vs non-clustered

SQL Server has two kinds, and the difference is the single most important thing to understand about the storage engine.

The clustered index

A clustered index defines the physical order of the table, and its leaf level is the table. There is no separate copy: the row data itself lives in the leaf pages, sorted by the clustered key. That is why a table can have exactly one. Declaring a PRIMARY KEY creates one by default, on that key.

A table with no clustered index is a heap - rows sit wherever there was room when they were written, in no order at all. Heaps have narrow legitimate uses (staging tables, bulk-load targets) and are usually an accident everywhere else.

The non-clustered index

A non-clustered index is a separate structure. Its leaf level holds the index key columns plus a row locator pointing back to the full row - the clustered key if the table has one, a physical row identifier if it is a heap. You can have many of them.

This is where a subtle and very common performance problem lives. If your query needs a column the index does not carry, the engine has to follow that locator back to the table for every matching row. That extra hop is a key lookup, and it happens once per row:

A lookup is cheap once and ruinous in bulk. Past a tipping point - often only a few percent of the table - the optimizer decides that scanning everything beats seeking and then looking up hundreds of thousands of times, and it stops using your index. It is usually right to do so. The fix is not to force the index; it is to remove the need for the lookup.

Covering the query

An index covers a query when it carries every column that query touches, so the engine never has to go back to the table. This is the highest-value indexing technique there is, and it is one keyword:

Key columns and INCLUDE columns are not the same thing. Key columns are sorted, live at every level of the tree, and can be searched and ordered by. Included columns exist only at the leaf, are not sorted, and cannot be seeked on - they are just payload, carried along so the lookup becomes unnecessary. Because they only exist at the leaf, they also make the tree wider without making it deeper.

The practical rule: columns you filter or sort on go in the key, columns you merely SELECT go in INCLUDE. And within the key, put the equality predicates first and the range predicate last. An index on (CustomerId, OrderDate) serves WHERE CustomerId = 4172 AND OrderDate >= '20260101' perfectly; reverse the columns and the engine can no longer seek to a single contiguous span.

Why your index is ignored

You created the index, the query is still slow, and the plan still shows a scan. There are five common reasons, and only one of them is the optimizer's fault.

• You are not using the leading column. A composite index on (A, B, C) is sorted by A first. It can seek on A, on A and B, or on all three. It cannot seek on B alone, any more than a phone book sorted by surname can find everyone called David. The leading column is not optional.
• The predicate is not SARGable. If a column is wrapped in a function or an expression, the sorted order of the index no longer applies to the thing being compared, so the engine must compute the expression for every row. WHERE YEAR(OrderDate) = 2026, WHERE Total * 1.1 > 100, and WHERE Email LIKE '%acme.com' are all scans by construction.
• An implicit conversion is in the way. Compare an NVARCHAR parameter to a VARCHAR column and SQL Server converts the column, not the parameter, because that is what its data-type precedence rules require. The result is CONVERT_IMPLICIT wrapped around your indexed column and the same scan as any other function. The query plan flags it with a warning, and it is one of the most common causes of a mysteriously unused index in ORM-generated SQL.
• The column is not selective enough. An index on a status flag where 90% of rows are 0 is not useful for finding those rows: reading the index and then looking up 90% of the table is strictly more work than reading the table. A filtered index - WHERE IsActive = 1 - is the answer when you only ever query the rare value.
• The statistics are stale. The optimizer chooses based on how many rows it expects. If the histogram was built when the table had 3,000 rows and it now has 3 million, it will happily pick a plan that is catastrophic at the real size. This is the one case where the index is fine and the estimate is wrong.

The first four are rewrites. The fix for a non-SARGable date predicate is always the same shape - turn the function into a range:

What every index costs

Indexes are usually discussed as a pure win, which is how databases end up with fourteen of them on one table. Every one you add is a standing charge:

• Writes multiply. An INSERT into a table with six indexes is seven writes, not one. An UPDATE touches every index whose columns it changes. A write-heavy table with a large index count spends most of its time maintaining indexes nobody reads.
• Page splits and fragmentation. Inserting a key in the middle of a full leaf page forces the engine to split it in two and move half the rows. That is expensive at the moment it happens, it generates extra transaction log, and it leaves the index physically scattered. An ever-increasing clustered key (an identity or a sequence) avoids most of this by always appending at the end; where the insert pattern is genuinely random, a fill factor below 100 leaves free space on each page to absorb the inserts instead.
• Storage, memory, and backups. Indexes are real pages. They occupy disk, they compete for the same buffer pool as your table data, and they are copied by every backup and every restore.
• Longer compilation. More indexes means more candidate plans to consider on every compile.

Unused indexes are the worst version of this: full cost, no benefit. SQL Server tracks reads and writes per index, so you can find them:

One caveat that catches people out: those counters reset when the instance restarts. An index with zero reads after two days of uptime is a candidate for removal; an index with zero reads after twenty minutes tells you nothing, and the monthly report that uses it runs on the 1st.

Choosing indexes

Index for the queries, not for the table. There is no good answer to "how should I index this table" without knowing what is asked of it.

• Start with the clustered key. Narrow, unique, static, and ever-increasing. Every non-clustered index carries a copy of it as its row locator, so a wide clustered key inflates every other index on the table. This is why a random UNIQUEIDENTIFIER clustered key is a poor default: 16 bytes, copied everywhere, and it splits pages on every insert.
• Index your foreign keys. SQL Server creates an index for a primary key automatically and for a foreign key never. The child side of an FK is what joins and cascading deletes read, and an unindexed one turns every parent delete into a full scan of the child table.
• Equality columns first, range last, payload in INCLUDE. The rule from section 05, and it settles most composite-index arguments before they start.
• One wider index beats three overlapping narrow ones. If you already have (CustomerId) and you need (CustomerId, Status), extend the first rather than adding a second. The old one was a prefix of the new one and is now redundant.
• Treat "missing index" suggestions as evidence, not instructions. The green text in a plan and the dm_db_missing_index views describe one query in isolation. They will happily recommend six near-identical indexes on the same table. Read them as a list of columns the workload cares about, then design one index that serves several queries.
• Measure with logical reads, one change at a time. SET STATISTICS IO ON, note the number, make one change, run it again. If reads did not drop, the index did not help, whatever the duration says.
• Confirm in the plan, not in your head. An index only helped if the operator changed. Reading the query plan before and after is the difference between knowing and hoping.

Indexing is not a one-time setup task. Query patterns change with every release, data volumes change every month, and an index that was correct in March can be dead weight by September. The habit worth building is small and periodic: look at what the workload actually reads, look at what it actually costs to write, and keep the set honest.