What is an INDEX in SQL Server? How does it improve query performance?

What an index is

An index is a separate, sorted data structure that lets SQL Server find rows fast without scanning the entire table.

The analogy: a book's index at the back. To find "Liskov" in a 900-page book, you don't read every page (a table scan) — you jump to "L" in the index, which tells you the exact page (an index seek). An SQL index does the same for table rows.

Physically, SQL Server indexes are B-trees (balanced trees): a root page → intermediate pages → leaf pages, all sorted by the index key. Finding any value takes a handful of page reads (logarithmic), no matter how big the table gets.

[ Root ]

/ | \

[ Intermediate pages ]

/ | | \

[ Leaf pages — sorted key values ]

────────────────────

The two main types

Clustered Index — is the table, sorted

• Defines the physical storage order of the rows themselves. The leaf level of a clustered index is the actual data.

• A table can have only ONE clustered index (data can only be physically sorted one way).

• Created automatically when you define a PRIMARY KEY (by default).

• A table without one is a heap (unordered pile of rows — usually slower to search).

Like a phone book physically sorted by last name — the sort order is how the data is stored.

Non-Clustered Index — a separate lookup structure

• A separate structure holding the key columns (sorted) + a pointer back to the full row.

• A table can have many (up to 999).

• The pointer is either the clustered key (if the table has a clustered index) or a RID (if it's a heap).

Like the index at the back of the book — separate from the content, pointing to it.

────────────────────

How it actually speeds up queries

Without an index,  WHERE LastName = 'Smith'  forces a table scan — read every row (millions of pages). With an index on  LastName :

1. Index Seek — SQL navigates the B-tree directly to  'Smith'  in a few page reads. O(log n) instead of O(n).

2. Eliminates sorts — because index data is already sorted,  ORDER BY LastName  or  GROUP BY  can skip an expensive sort operation.

3. Speeds up JOINs — indexes on join/foreign-key columns let SQL match rows via seeks instead of scanning both tables.

4. Range queries —  BETWEEN ,  > ,  <  are fast because sorted values sit next to each other in the leaf pages.

The performance difference is dramatic: a seek on a 10-million-row table reads ~4–5 pages; a scan reads hundreds of thousands.

────────────────────

The Key Lookup problem & covering indexes

A non-clustered index only holds its key columns. If your query needs other columns:

-- Index is on (LastName). But query wants FirstName, Email too:

SELECT FirstName, Email FROM Customers WHERE LastName = 'Smith';

SQL seeks the index, then must jump back to the table for each match — a Key Lookup — which can be costly for many rows.

Fix: a covering index using  INCLUDE  — store the extra columns in the index leaf so the query is answered entirely from the index, no lookup needed:

CREATE NONCLUSTERED INDEX IX_Customers_LastName

ON Customers (LastName)

INCLUDE (FirstName, Email); -- ← "covers" the query