SQL Server B-Tree: How an Index Seek Finds One Row

What "Seek" Actually Means

"Index Seek" and "Index Scan" are both operators that read an index — the difference is how they get to the rows.

• Scan: starts at one end of the index and reads leaf pages in order, evaluating every row it passes. It ignores the tree structure above the leaf level entirely.
• Seek: uses the tree structure to navigate directly to the leaf page(s) that can contain a match, based on a predicate on the index's leading key column(s). It never touches pages it doesn't need.

That distinction is the entire reason a seek is cheap: its cost is tied to the height of the tree, not the size of the table.

The Shape of a B-Tree Index

Every SQL Server index — clustered or nonclustered — is a balanced B-tree (technically a B+ tree). Three kinds of pages:

• Root page — one per index, the single entry point.
• Intermediate pages — zero or more levels, each page holding pointers to the next level down.
• Leaf pages — the bottom level. For a clustered index, leaf pages hold the actual row data. For a nonclustered index, they hold the key value plus a row locator (the clustering key, or a RID for a heap).

"Balanced" means every leaf is the same distance from the root. A table growing from a million to a billion rows doesn't multiply the page reads by a thousand — it typically adds one more level. That's the logarithmic growth that makes a seek scale so well: log(n), not n.

Watching a Seek Happen

Below is a simplified three-level tree. The query asks for a single key; watch how few pages it takes to land on it.

That's the whole trick. At every level the engine does one comparison against the page's separator keys, follows the one pointer that can contain the value, and discards everything else on that page without reading it. Two levels of separators here means the table could hold anywhere from a few hundred rows to several million and the seek would still take exactly three page reads.

Seeing It in the Execution Plan

The animation above maps directly onto what SQL Server reports for a real query:

CREATE TABLE dbo.Orders
(
    OrderID    INT IDENTITY PRIMARY KEY,
    CustomerID INT NOT NULL,
    OrderDate  DATE NOT NULL,
    Status     TINYINT NOT NULL
);

CREATE NONCLUSTERED INDEX IX_Orders_CustomerID
    ON dbo.Orders (CustomerID)
    INCLUDE (OrderDate, Status);

SET STATISTICS IO ON;

SELECT OrderDate, Status
FROM dbo.Orders
WHERE CustomerID = 4821;

With a reasonably sized table, the plan shows an Index Seek on IX_Orders_CustomerID, and STATISTICS IO reports a handful of logical reads — root, one or two intermediate levels, one leaf page. Grow the table by a factor of 100 and that number barely moves.

What Turns a Seek Into a Scan

The optimizer can only use the tree structure if the predicate is SARGable — expressible as "the leading index key(s) fall in this range/equal this value" without first computing something on every row. Common ways a seek quietly becomes a scan:

• Wrapping the indexed column in a function or expression — see Never Put Functions in WHERE Clauses.
• A leading wildcard in LIKE '%value' — the engine can't bound a range from an unknown prefix; compare with LIKE vs. LEFT.
• Implicit conversion from a datatype or collation mismatch between the column and the literal/parameter.
• Filtering on a non-leading column of a composite index while skipping the leading column(s).
• OR conditions across columns that aren't all covered by the same or compatible indexes.

Seek vs. Scan, Side by Side

When a Scan Is Actually Fine

Don't chase "Seek" as a goal in itself. A scan is the right choice — and often the cheaper one — when:

• The table is small enough that it fits in one or two pages. A seek plus a bookmark lookup back to the clustered index can cost more than just reading the whole thing.
• The query needs most of the table's rows anyway (a large aggregation, an unfiltered report). Seeking one row at a time in that case is strictly worse than one sequential pass.

The query optimizer already weighs this with cost-based estimates; if it picked a scan on a table you expected a seek on, look at the estimated row count and the predicate first, before assuming the plan is "wrong."

Best Practices

• ☐ Match WHERE and JOIN columns to the leading columns of an index, in the same order the index defines them.
• ☐ Never wrap an indexed column in a function, CAST, or implicit conversion in the predicate — see Never Put Functions in WHERE Clauses.
• ☐ In the plan, check Seek Predicate versus plain Predicate — only the former narrows page reads.
• ☐ Add narrow, non-key columns via INCLUDE to make the index covering and avoid a bookmark lookup back to the clustered index.
• ☐ Watch Number of Executions on a seek inside a nested loop — a cheap single seek repeated a million times is not cheap.
• ☐ Cross-check STATISTICS IO logical reads against what the tree height should produce; a much higher number usually means the seek predicate is looser than it looks.
• ☐ Don't force a seek on a table small enough that a scan is genuinely cheaper.

The Bottom Line

A B-tree index turns "find this row" from a linear search into a small, fixed number of comparisons — because the tree is balanced and every level narrows the search by following exactly one pointer. An Index Seek is SQL Server using that structure the way it was built to be used; an Index Scan is SQL Server giving up on it, deliberately or otherwise.

When a query is slower than it should be, the plan's Seek Predicate — not the operator's name — is where the real answer lives.