How SQL Server stores data: pages, heaps and B-trees

Until now you have told SQL Server what you want. This module is about how it finds it, and why one query takes a millisecond while another, returning the same rows, takes seconds. Almost all of the difference comes from one number: how many pages the query has to read.

The BuildMart tables are far too small to show this: each one fits on a single page. The script below creates dbo.Sales, with 100,000 made-up sales. GENERATE_SERIES returns the numbers 1 to 100,000, and arithmetic on each number fills the columns. Note that the table has no primary key yet; that is on purpose.

1DROP TABLE IF EXISTS dbo.Sales;2CREATE TABLE dbo.Sales (3    SaleId     int           NOT NULL,4    SaleDate   date          NOT NULL,5    CustomerId int           NOT NULL,6    ProductId  int           NOT NULL,7    Quantity   int           NOT NULL,8    Amount     decimal(10,2) NOT NULL,9    Channel    varchar(10)   NOT NULL,10    Notes      char(100)     NULL11);12INSERT INTO dbo.Sales (SaleId, SaleDate, CustomerId, ProductId, Quantity, Amount, Channel)13SELECT value,14       DATEADD(day, value * 37 % 1096, '2022-01-01'),15       value * 7919 % 5000 + 1,16       value % 12 + 1,17       value % 7 + 1,18       value * 31 % 9000 / 100.0 + 1,19       CASE value % 10 WHEN 0 THEN 'Phone' WHEN 1 THEN 'Shop' WHEN 2 THEN 'Shop' ELSE 'Web' END20FROM GENERATE_SERIES(1, 100000);21 22SELECT COUNT(*) AS SalesRows, MIN(SaleDate) AS FirstDay, MAX(SaleDate) AS LastDay23FROM dbo.Sales;

SalesRows  FirstDay    LastDay
---------  ----------  ----------
   100000  2022-01-01  2024-12-31

The data has a pattern you can rely on later: 5,000 customers with 20 sales each, 12 products, dates from 2022-01-01 to 2024-12-31, and three channels (Web 70%, Shop 20%, Phone 10%).

Pages: the unit SQL Server reads

SQL Server stores every table in pages of 8 KB (8,192 bytes). A page starts with a 96-byte header, then the rows, and ends with a small slot array: 2 bytes per row, saying where on the page each row starts. That leaves about 8,060 bytes for rows. A row must fit on one page (long varchar(max) values are stored on separate pages).

SQL Server reads and writes whole pages, never single rows. To read one row, it reads the page the row is on. sys.dm_db_index_physical_stats shows how many pages a table uses:

1SELECT index_type_desc, page_count, record_count,2       avg_record_size_in_bytes AS AvgRowBytes3FROM sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID(N'dbo.Sales'), NULL, NULL, 'DETAILED');

index_type_desc  page_count  record_count  AvgRowBytes
---------------  ----------  ------------  -----------
HEAP                   1786        100000        142.4

Each row takes about 142 bytes, plus 2 bytes in the slot array. 8,060 ÷ 144 is 56 rows per page, and 100,000 ÷ 56 is 1,786 pages: about 14 MB.

Wider rows, more pages

Notes is char(100). A char column always takes its full length, even when it holds NULL, so every row carries 100 bytes it does not use. Compare a copy of the table where Notes is varchar(100), which stores only what is there:

1DROP TABLE IF EXISTS dbo.SalesSlim;2SELECT SaleId, SaleDate, CustomerId, ProductId, Quantity, Amount, Channel,3       CAST(Notes AS varchar(100)) AS Notes4INTO dbo.SalesSlim5FROM dbo.Sales;6 7SELECT OBJECT_NAME(object_id) AS TableName, page_count,8       avg_record_size_in_bytes AS AvgRowBytes9FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'DETAILED')10WHERE object_id IN (OBJECT_ID(N'dbo.Sales'), OBJECT_ID(N'dbo.SalesSlim'));11 12DROP TABLE dbo.SalesSlim;

TableName  page_count  AvgRowBytes
---------  ----------  -----------
Sales            1786        142.4
SalesSlim         550         42.4

The same 100,000 rows fit on less than a third as many pages. Every query that reads the whole table does that much less work, and more of the table fits in memory. Choosing the narrowest type that fits the data is a performance decision, not only a tidy one.

Logical reads: how much work a query did

SET STATISTICS IO ON makes SQL Server report, for each table a query touched, how many pages it read. In SSMS the report appears on the Messages tab.

• logical reads: pages read from memory (the buffer pool). Every page a query uses counts here, whether or not it had to come from disk first.
• physical reads and read-ahead reads: pages that first had to be fetched from disk. They depend on what happens to be in memory, so they change from run to run.
• Scan count: how many times the table or index was entered.

Logical reads is the number to watch when you tune a query: it measures the work itself and is the same every time you run the query. Find one sale:

1SET STATISTICS IO ON;2SELECT SaleId, SaleDate, CustomerId, Amount3FROM dbo.Sales4WHERE SaleId = 4321;5SET STATISTICS IO OFF;

SaleId  SaleDate    CustomerId  Amount
------  ----------  ----------  ------
  4321  2024-08-15        3000   80.51

Table 'Sales'. Scan count 1, logical reads 1786, physical reads 283, page server reads 0, read-ahead reads 1711, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

One row, and 1,786 pages read: every page of the table. The table is a heap, a table without a clustered index. Its rows are stored wherever there was space, in no order, so SQL Server cannot know which page holds SaleId 4321. The only way to find it is to read every page and check every row. The same is true for any WHERE on a heap.

B-trees: finding a row without reading them all

An index keeps rows sorted by a key and builds a tree of pages above them, so SQL Server can go straight to the right page. Create a clustered index on SaleId and look at the pages again:

1CREATE UNIQUE CLUSTERED INDEX CX_Sales ON dbo.Sales (SaleId);2 3SELECT index_type_desc, index_level, page_count, record_count4FROM sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID(N'dbo.Sales'), NULL, NULL, 'DETAILED')5ORDER BY index_level DESC;

index_type_desc  index_level  page_count  record_count
---------------  -----------  ----------  ------------
CLUSTERED INDEX            2           1             3
CLUSTERED INDEX            1           3          1786
CLUSTERED INDEX            0        1786        100000

The index has three levels:

• Level 2, the root: one page with 3 entries, one for each page on the level below. Each entry holds the first SaleId on that page and the page’s address.
• Level 1, intermediate: 3 pages with 1,786 entries, one for each leaf page.
• Level 0, the leaf level: 1,786 pages holding the rows themselves, now sorted by SaleId.

Together these form a B-tree (balanced tree): every leaf page is the same distance from the root. Now find the same sale again:

1SET STATISTICS IO ON;2SELECT SaleId, SaleDate, CustomerId, Amount3FROM dbo.Sales4WHERE SaleId = 4321;5SET STATISTICS IO OFF;

SaleId  SaleDate    CustomerId  Amount
------  ----------  ----------  ------
  4321  2024-08-15        3000   80.51

Table 'Sales'. Scan count 0, logical reads 3, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

Three logical reads instead of 1,786: the root, one intermediate page and one leaf page. Reading down the tree like this is called a seek. Reading all the leaf pages is a scan. (Scan count 0 in the report means the index was entered once, for a single-value seek.)

Trees stay shallow as tables grow, because each index page holds hundreds of entries. Each extra level multiplies the number of rows the tree can reach by several hundred, so even tables with billions of rows usually need only four or five levels, which means four or five reads to find one row.

Ranges follow the leaf chain

Each leaf page also stores the address of the page before and after it, so the leaf level is a linked chain in key order. For a range, SQL Server seeks to the first row and then reads along the chain until it passes the end of the range:

1SET STATISTICS IO ON;2SELECT COUNT(*) AS SalesRows, SUM(Amount) AS Total3FROM dbo.Sales4WHERE SaleId BETWEEN 1001 AND 2000;5SET STATISTICS IO OFF;

SalesRows     Total
---------  --------
     1000  47925.00

Table 'Sales'. Scan count 1, logical reads 22, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

1,000 rows at 56 rows a page is about 18 leaf pages, plus the root and an intermediate page on the way down. The cost of a range seek grows with the number of rows it returns, not with the size of the table.

1SET STATISTICS IO ON;2SELECT SaleId, Amount3FROM dbo.Sales4WHERE SaleId IN (10, 50000, 99999);5SET STATISTICS IO OFF;

SaleId  Amount
------  ------
    10    4.10
 50000   21.00
 99999   40.69

Table 'Sales'. Scan count 3, logical reads 9, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.