Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 39 ยท Indexes and Performance

Clustered and Nonclustered Indexes

Understand how SQL Server stores tables as heaps or clustered B-trees, how nonclustered indexes and key lookups work, and how to choose index keys, with runnable plan examples.

An index is a separate structure that lets SQL Server find rows without reading the entire table. Think of the index of a book: instead of reading every page to find "deadlock", you look it up and jump to the page. The right indexes are the biggest single performance lever in SQL Server, and the wrong ones slow down every write.

This lesson explains how SQL Server stores data, the difference between clustered and nonclustered indexes, and how to design them. For the general idea, see SQL indexes and advanced indexing. SQL Server's own tools can't run here, but SQLite's EXPLAIN QUERY PLAN shows the same effects, and it runs in the editor.

Pages and the B-tree

SQL Server stores data in 8 KB pages. Eight pages make an extent. Rows live on data pages; an index is a B-tree (balanced tree) built from pages:

  • The root page points to the next level.
  • Intermediate levels narrow the search.
  • The leaf level holds the sorted keys (and, for a clustered index, the actual rows).

A lookup in a table with millions of rows usually touches only 3 or 4 pages, because each page fans out to hundreds of children. That is why a seek is so much cheaper than a scan.

flowchart TD
  R["Root page: 1 to 1,000,000"] --> I1["Intermediate: 1 to 400,000"]
  R --> I2["Intermediate: 400,001 to 1,000,000"]
  I1 --> L1["Leaf: rows 1 to 200"]
  I1 --> L2["Leaf: rows 201 to 400"]
  I2 --> L3["Leaf: rows 400,001 to ..."]

A seek follows one path from the root to a leaf.

Heap or clustered index

A table with no clustered index is a heap: rows sit in no particular order. A table with a clustered index is stored as that B-tree, sorted by the clustering key. The clustered index is the table, so there is only one per table.

SQL
CREATE TABLE dbo.Orders
(
    OrderId    int IDENTITY(1,1) NOT NULL,
    CustomerId int           NOT NULL,
    OrderDate  datetime2(0)  NOT NULL,
    Total      decimal(10,2) NOT NULL,
    CONSTRAINT PK_Orders PRIMARY KEY CLUSTERED (OrderId)
);

A PRIMARY KEY creates a clustered index by default, unless you say NONCLUSTERED or one already exists. A good clustering key is:

  • Narrow: the key is copied into every nonclustered index, so a bigint costs less than a long string.
  • Unique (SQL Server adds a hidden 4-byte "uniquifier" otherwise).
  • Static: updating the key moves the row.
  • Ever-increasing: IDENTITY or sequential values add rows at the end and avoid page splits. Random GUIDs (NEWID()) cause splits and fragmentation; use NEWSEQUENTIALID() or an integer key.

Nonclustered indexes

A nonclustered index is a second B-tree with the indexed columns as keys. Its leaf rows carry the clustering key (or a row ID in a heap), which is how SQL Server finds the full row:

SQL
CREATE NONCLUSTERED INDEX IX_Orders_CustomerId
    ON dbo.Orders (CustomerId);

A query WHERE CustomerId = 42 now seeks the nonclustered index, then does a key lookup into the clustered index for each matching row to get columns that the index doesn't contain. A few lookups are cheap. Thousands become expensive, and the optimizer then prefers a scan. The next lesson, covering indexes, removes lookups.

You can see an index being used with SQLite's plan output:

SQL Scan versus index seek

Press Run (or Ctrl + Enter) to see the result here.

The plan says SCAN orders: every row is read. Add the index and look again:

SQL The same query after CREATE INDEX

Press Run (or Ctrl + Enter) to see the result here.

Now it says SEARCH orders USING INDEX. That's the SQLite equivalent of an Index Seek. (In SQLite the table itself is a B-tree keyed by id, much like a clustered index.)

Composite indexes and column order

An index on (CustomerId, OrderDate) is sorted by customer first, then by date within each customer. It helps queries that filter on:

  • CustomerId alone (the leftmost column),
  • CustomerId and OrderDate,

but not OrderDate alone. Put columns used in equality tests first, then the one used for a range or sort:

SQL
CREATE NONCLUSTERED INDEX IX_Orders_Customer_Date
    ON dbo.Orders (CustomerId, OrderDate DESC);

This one serves WHERE CustomerId = 42 ORDER BY OrderDate DESC without a separate sort.

Other kinds of index

Type Use
Unique index Enforces uniqueness (a UNIQUE constraint creates one)
Filtered index WHERE Status = 'open': only some rows, smaller and faster
Columnstore Analytics over millions of rows; compressed by column
XML, spatial, full-text Special data and text search
Indexed view Materializes an aggregate query

The cost of indexes

Every index must be updated for each INSERT, UPDATE and DELETE that touches its columns, and takes space and memory. A table with 15 indexes writes slowly. Index for the queries you really run, drop indexes nobody uses (sys.dm_db_index_usage_stats shows reads and writes per index), and remove duplicates. Over time, pages split and become fragmented; ALTER INDEX ... REORGANIZE or REBUILD fixes that during maintenance.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many clustered indexes can a table have?

    The clustered index defines the physical order of the rows, so there can be only one. Nonclustered indexes are separate structures.
  2. 2. What is a key lookup?

    When a nonclustered index doesn't contain every column the query needs, SQL Server visits the base row per match.
  3. 3. Which query can use an index on (CustomerId, OrderDate) for a seek?

    Seeks need the leftmost key column. OrderDate alone is not the leading column.
  4. 4. Why are random GUID clustering keys problematic?

    Inserting in random key order splits pages all over the tree; sequential keys append at the end.

Summary

  • Tables are heaps or clustered B-trees; the clustered key should be narrow, unique, static and increasing.
  • Nonclustered indexes point back to the row, so missing columns cost key lookups.
  • Composite indexes work from the leftmost column; equality columns first.
  • Every index speeds reads and slows writes; measure usage and prune.

Next: Covering indexes and sargability