How SQL Server Stores a Table: Heaps, Clustered Indexes and B+ Trees

Learning outcome

You can explain how SQL Server stores rows on 8 KB pages, the difference between a heap and a clustered index, why a lookup by the clustered key costs 3 page reads while the same lookup on a heap costs 3,226, and why every nonclustered index carries the clustered key. Every example in this course is a script or a small .NET 10 program that was run against SQL Server 2022 (16.0.4305.5, Developer Edition) in Docker. The output blocks are the real output, printed by a small runner that shows result sets, SET STATISTICS IO lines and the operators of the actual execution plan with estimated and actual row counts.

Intuition

A table is a pile of 8 KB pages. If nothing orders those pages, the table is a heap: to find one order SQL Server has to read every page. A clustered index sorts the rows themselves by a key and builds a small tree of "signpost" pages above them. Finding one row means walking from the root down to one leaf page: a handful of reads, whatever the table size.

flowchart TD
    R["Root page (level 2): 11 entries"] --> I1["Intermediate pages (level 1): 11 pages"]
    I1 --> L1["Leaf pages (level 0): 3,226 pages = the rows, sorted by OrderId"]
    H["Heap: 3,226 pages, no order"] -.->|"find OrderId 123456 = read all of them"| H

Deep dive

• Pages. The unit of storage and of I/O is an 8 KB page (8,192 bytes, checked in verify/claims-sql). logical reads in STATISTICS IO counts pages read from the buffer pool. It is the most stable cost metric you have: unlike duration, it does not depend on cache warmth or load.
• Heap. A table without a clustered index. Rows are found by a RID (file:page:slot). There is no order, so a predicate on any column means a Table Scan unless a nonclustered index helps.
• Clustered index. The table is the index: the leaf level holds the full rows sorted by the key. The levels above hold one entry per page below. Here, 200,000 rows fit in 3,226 leaf pages, 11 intermediate pages and 1 root page: an index depth of 3.
• Seek vs scan. A seek navigates the tree to a starting key and reads only the range it needs. A scan reads the whole leaf level (or the whole heap).
• Range queries. Because leaf pages are linked in key order, BETWEEN 1000 AND 1999 on the clustered key can follow the leaf pages in key order, but only ORDER BY guarantees the result order.
• The clustered key is the row locator. Every nonclustered index stores, for each row, its own key plus the clustered key, which it uses to find the full row. A wide clustered key (a uniqueidentifier, a composite of strings) makes every index wider. The index key limit is 900 bytes for a clustered index (Msg 1944 in verify/claims-sql).
• Choosing a clustered key. Narrow, unique, static and ever-increasing (int/bigint identity) is the default good choice. A random GUID key works, but causes page splits and fragmentation on insert. NEWSEQUENTIALID() or a sequential GUID generated by the client reduces that.
• What a primary key gives you. PRIMARY KEY creates a clustered index by default if the table does not have one yet. EF Core follows that default for its key.

Code example: the same 200,000 rows as a heap and as a clustered index

-- Lesson 1: heap vs clustered index. 200,000 orders stored twice.
SET NOCOUNT ON;
CREATE TABLE dbo.OrdersHeap (OrderId int NOT NULL, CustomerId int NOT NULL, OrderDate date NOT NULL, Total decimal(10,2) NOT NULL, Note char(100) NOT NULL);
CREATE TABLE dbo.OrdersClustered (OrderId int NOT NULL CONSTRAINT PK_OrdersClustered PRIMARY KEY CLUSTERED,
    CustomerId int NOT NULL, OrderDate date NOT NULL, Total decimal(10,2) NOT NULL, Note char(100) NOT NULL);
WITH n AS (SELECT TOP (200000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS i FROM sys.all_objects a CROSS JOIN sys.all_objects b)
INSERT dbo.OrdersHeap SELECT i, i % 5000 + 1, DATEADD(day, i % 730, '2024-01-01'), (i % 997) + 0.99, 'x' FROM n;
INSERT dbo.OrdersClustered SELECT * FROM dbo.OrdersHeap;
GO
-- > Physical structure: index type, B-tree depth, pages and rows per level
SELECT OBJECT_NAME(s.object_id) AS TableName, s.index_type_desc, s.index_depth, s.index_level, s.page_count, s.record_count
FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'DETAILED') AS s
WHERE s.object_id IN (OBJECT_ID('dbo.OrdersHeap'), OBJECT_ID('dbo.OrdersClustered'))
ORDER BY TableName, s.index_level DESC;
GO
-- > Point lookup by OrderId: heap (no index) vs clustered (B+ tree seek)
-- @plan
SET STATISTICS IO ON;
SELECT Total FROM dbo.OrdersHeap WHERE OrderId = 123456;
SELECT Total FROM dbo.OrdersClustered WHERE OrderId = 123456;
SET STATISTICS IO OFF;
GO
-- > Range on the clustered key reads only the needed leaf pages, already in key order
-- @plan
SET STATISTICS IO ON;
SELECT COUNT(*) AS Orders, SUM(Total) AS Revenue FROM dbo.OrdersClustered WHERE OrderId BETWEEN 1000 AND 1999;
SET STATISTICS IO OFF;
GO
-- > The clustered key is the row locator stored in every nonclustered index
CREATE INDEX IX_OrdersClustered_CustomerId ON dbo.OrdersClustered (CustomerId);
SELECT i.name, c.name AS column_name, ic.key_ordinal, ic.is_included_column
FROM sys.indexes i JOIN sys.index_columns ic ON ic.object_id = i.object_id AND ic.index_id = i.index_id
JOIN sys.columns c ON c.object_id = ic.object_id AND c.column_id = ic.column_id
WHERE i.object_id = OBJECT_ID('dbo.OrdersClustered') AND i.name = 'IX_OrdersClustered_CustomerId';
SELECT index_level, page_count, record_count, avg_record_size_in_bytes
FROM sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID('dbo.OrdersClustered'), INDEXPROPERTY(OBJECT_ID('dbo.OrdersClustered'), 'IX_OrdersClustered_CustomerId', 'IndexID'), NULL, 'DETAILED')
ORDER BY index_level DESC;
GO

Output (SQL Server 2022 in Docker)

-- Physical structure: index type, B-tree depth, pages and rows per level
TableName       | index_type_desc | index_depth | index_level | page_count | record_count
----------------+-----------------+-------------+-------------+------------+-------------
OrdersClustered | CLUSTERED INDEX | 3           | 2           | 1          | 11
OrdersClustered | CLUSTERED INDEX | 3           | 1           | 11         | 3226
OrdersClustered | CLUSTERED INDEX | 3           | 0           | 3226       | 200000
OrdersHeap      | HEAP            | 1           | 0           | 3226       | 200000
(4 rows)
-- Point lookup by OrderId: heap (no index) vs clustered (B+ tree seek)
Total
------
825.99
(1 row)
IO: 'OrdersHeap'. Scan count 1, logical reads 3226
PLAN (actual):
  Table Scan [OrdersHeap]  est=1.1 actual=1
Total
------
825.99
(1 row)
IO: 'OrdersClustered'. Scan count 0, logical reads 3
PLAN (actual):
  Clustered Index Seek [OrdersClustered.PK_OrdersClustered]  est=1 actual=1
-- Range on the clustered key reads only the needed leaf pages, already in key order
Orders | Revenue
-------+----------
1000   | 497508.00
(1 row)
IO: 'OrdersClustered'. Scan count 1, logical reads 20
PLAN (actual):
  Compute Scalar  est=1 actual=n/a
    Stream Aggregate (Aggregate)  est=1 actual=1
      Clustered Index Seek [OrdersClustered.PK_OrdersClustered]  est=1000 actual=1000
-- The clustered key is the row locator stored in every nonclustered index
name                          | column_name | key_ordinal | is_included_column
------------------------------+-------------+-------------+-------------------
IX_OrdersClustered_CustomerId | CustomerId  | 1           | False
(1 row)
index_level | page_count | record_count | avg_record_size_in_bytes
------------+------------+--------------+-------------------------
1           | 1          | 350          | 15
0           | 350        | 200000       | 12
(2 rows)

Code walkthrough

• Physical structure: the clustered index has index_depth 3: 1 root page, 11 intermediate pages, 3,226 leaf pages holding 200,000 rows. The heap is a single level of 3,226 pages.
• Point lookup: the heap needs a Table Scan with 3,226 logical reads to return one row. The clustered index does a Clustered Index Seek with 3 logical reads: one page per level.
• Range: 1,000 consecutive keys cost 20 logical reads, a few more than the point lookup, because those rows sit on adjacent leaf pages.
• The nonclustered index on CustomerId has 350 leaf pages for the same 200,000 rows, with an average leaf record of 12 bytes. Its declared key is only the 4-byte CustomerId (key_ordinal 1); the rest of each record is the row locator (the 4-byte clustered key OrderId) plus row overhead. That is why it is about a tenth the size of the table (350 vs 3,226 pages).

Failure modes

• A large table left as a heap "because inserts are faster": lookups without a useful nonclustered index require scans, and heaps suffer from forwarded records after updates that grow rows.
• A random GUID as the clustered key on a hot insert table: page splits, fragmentation, and a 16-byte locator copied into every nonclustered index.
• A wide composite clustered key (for example three nvarchar columns) that bloats every index.
• Judging performance by duration on a warm cache instead of by logical reads.
• Believing a table is "sorted" without ORDER BY. The clustered index is a storage structure; only ORDER BY guarantees result order.

Interview angle

"What is the difference between a clustered and a nonclustered index?" The clustered index is the table: its leaf level holds the rows, sorted by the key, so there is at most one. A nonclustered index is a separate B+ tree whose leaves hold the index key plus a row locator (the clustered key, or a RID on a heap). Then quote cost: a seek costs about one page per level (3 reads for 200,000 rows here) while a heap scan reads every page (3,226).

Practice questions

1. Why does a clustered index seek on a 200,000-row table cost only 3 logical reads?

Answer: The B+ tree has depth 3. A seek reads one page per level: root, intermediate, leaf.

2. Why is uniqueidentifier with NEWID() a questionable clustered key?

Answer: Random values insert in the middle of the tree (page splits, fragmentation), and the 16-byte key is copied into every nonclustered index as the row locator.

3. Does a clustered index guarantee that SELECT * FROM T returns rows in key order?

Answer: No. Without ORDER BY, order is not guaranteed (parallel plans and other access paths can return any order).

Revision checklist

• 8 KB pages; logical reads = pages touched.
• Heap = no order, RID locator, scans.
• Clustered index = the rows sorted by the key, one per table.
• Seek cost ≈ index depth; scan cost = all leaf pages.
• Nonclustered index leaf = key + clustered key.
• Narrow, unique, static, increasing clustered keys.

Related on TechInterviewNotes

• Free cheat sheet: SQL Server Indexes and Isolation Levels
• Course: EF Core Performance and Behavior (what EF sends to SQL Server; this course covers what SQL Server does with it)
• Mock interview: EF Core and SQL

References

• Clustered and nonclustered indexes described
• SQL Server index architecture and design guide
• Pages and extents architecture guide
• sys.dm_db_index_physical_stats