Heaps, clustered and nonclustered indexes — B+ tree internals — SQL Server Internals — How the Database Engine Really Works

3. Heaps, clustered and nonclustered indexes — B+ tree internals

Intermediate★ Must knowLesson 3 of 11

Heap — a table without a clustered index: rows stored in no particular order, located by a RID (file:page:slot). Updates that grow a row may leave forwarding pointers. Fine for staging tables; usually bad for OLTP.

Clustered index — the table itself is a B+ tree ordered by the clustering key: root page → intermediate pages → leaf pages containing the full rows. One per table.

Nonclustered index — a separate B+ tree on chosen key columns; leaf rows contain the key + a row locator: the clustering key (if the table is clustered) or the RID (heap). Up to 999 per table.

text

Clustered index on Orders(OrderId)                  Nonclustered index on Orders(CustomerId) INCLUDE (Total)
        [Root: 1 | 50,001 | 100,001]                         [Root: ... ]
       /            |              \                          /        \
 [Intermediate ...]                                    [Leaf: CustomerId, Total, OrderId(locator)]
 [Leaf pages: full rows ordered by OrderId]              → "key lookup" into the clustered index for other columns

Operation	What it does	Cost
Index seek	Navigate root → leaf to a key or range	~3–4 page reads for millions of rows
Index/table scan	Read all leaf pages	Proportional to table size
Key lookup (bookmark lookup)	For each row found in a nonclustered index, fetch missing columns from the clustered index	1 seek per row — expensive for many rows
Covering index	Nonclustered index containing all needed columns (keys + `INCLUDE`)	No lookups

Choosing a clustered key: narrow (it's copied into every nonclustered index), unique, static (never updated) and ever-increasing (INT IDENTITY, BIGINT, sequential GUID) to avoid page splits. Random NEWID() GUID keys cause splits and fragmentation.

Page splits and fill factor: inserting into a full page splits it into two half-full pages (expensive, logged, causes fragmentation). FILLFACTOR = 90 leaves 10 % free space on leaf pages at rebuild time for tables with random inserts.

Fragmentation: logical order of pages ≠ physical order and/or low page density. Rebuild (ALTER INDEX ... REBUILD) or reorganise based on measurement; on SSDs, page density (wasted space) matters more than physical order.

sql

CREATE CLUSTERED INDEX CIX_Orders ON dbo.Orders(OrderId);
CREATE NONCLUSTERED INDEX IX_Orders_Customer_Date ON dbo.Orders(CustomerId, OrderDate DESC) INCLUDE (Total, Status)
    WITH (FILLFACTOR = 95, ONLINE = ON);
CREATE INDEX IX_Orders_Open ON dbo.Orders(OrderDate) WHERE Status = 'Open';   -- filtered index