SQL Server: Clustered and Nonclustered indexes

Article
1/17/2024

Preamble

A brief web search on differences between clustered and nonclustered indexes shows that it is a very commonly held misconception that clustered indexes are always stored sorted on the clustered index key.

The below article - copied from my StackOverflow answer here illustrates that this is not always the case, with the help of an undocumented function and the aid of the Spatial Results tab to show this graphically.

Overview

In SQL Server row oriented storage both clustered and non clustered indexes are organized as B trees.

http://i.stack.imgur.com/QF8d7.gif

(Image Source)

The key difference between clustered indexes and non clustered indexes is that the leaf level of the clustered index is the table. This has two implications.

The rows on the clustered index leaf pages always contains something for each of the columns in the table (either the value, or a pointer to the actual value).
The clustered index is the primary copy of a table.

(NB: Regarding point 1 there are some exceptions where nothing is stored at all but it must be possible for SQL Server to still infer the actual value for each column. Examples of these are null sparse columns, null columns stored at the end of the variable length section, columns added with default values in Enterprise Edition.)

Non clustered indexes can also do point 1 by using the INCLUDE clause (since SQL Server 2005) to explicitly include all non key columns but they are secondary representations and there is always another copy of the data around (the table itself).

Leaf Level Rows Compared

Below we look at the case alluded to above where the non clustered index includes all columns in the table.

CREATE TABLE T
 (
 A INT NOT NULL,
 B INT NOT NULL,
 C INT NOT NULL,
 D INT NOT NULL
 );

CREATE UNIQUE CLUSTERED INDEX ci
 ON T(A, B);

CREATE UNIQUE NONCLUSTERED INDEX nci
 ON T(A, B)
 INCLUDE (C, D);

INSERT INTO T
VALUES (1,2,3,4);

The general structure of the two indexes created above will be nearly identical. With the upper level index pages containing values for the key columns A,B and the leaf level pages containing A,B,C,D . The leaf level page for a clustered index is accounted for as a data page whereas the leaf level for a non clustered index is accounted for as an index page but the differences in row structure are minor and boil down to the non clustered index leaf rows being slightly more compact with less space taken up with metadata.

As the images below show the non clustered index row does not have a null bitmap when all columns are not nullable - unlike the clustered index case. And a few more bytes are saved in the column count and status bits sections.

Leaf Level Row - Clustered Index shown in SQL Internals Viewer

http://i.stack.imgur.com/HVIJb.png

Leaf Level Row - Non Clustered Index shown in SQL Internals Viewer

http://i.stack.imgur.com/aDF4y.png

Page Order

Whilst it is of course trivially correct that the table pages are in the same order as the clustered index leaf pages (as the table pages are the Clustered Index leaf pages) the commonly held belief that with a clustered index the rows are always stored physically on the disk in the same order as the index key is false.

This would be an absurd implementation. For example if a row is inserted into the middle of a 4GB table SQL Server does not have to copy 2GB of data up in the file to make room for the newly inserted row .

Instead a page split occurs. Each page at the leaf level of both clustered and non clustered indexes has the address (File:Page) of the next and previous page in logical key order. These pages need not be either contiguous or in key order.

e.g. the linked page chain might be 1:2000 <-> 1:157 <-> 1:7053

When a page split happens a new page is allocated from anywhere in the filegroup (from either a mixed extent, for small tables, or a non empty uniform extent belonging to that object or a newly allocated uniform extent). This might not even be in the same file if the file group contains more than one.

The degree to which the logical order and contiguity differs from the idealised physical version is the degree of logical fragmentation.

In a newly created database with a single file I ran the following.

CREATE TABLE T
 (
 X TINYINT NOT NULL,
 Y CHAR(3000) NULL
 );

CREATE CLUSTERED INDEX ix
 ON T(X);

GO

--Insert 100 rows with values 1 - 100 in random order
DECLARE @C1 AS CURSOR,
 @X AS INT

SET @C1 = CURSOR FAST_FORWARD
FOR SELECT number
 FROM master..spt_values
 WHERE type = 'P'
  AND number BETWEEN 1 AND 100
 ORDER BY CRYPT_GEN_RANDOM(4)

OPEN @C1;

FETCH NEXT FROM @C1 INTO @X;

WHILE @@FETCH_STATUS = 0
 BEGIN
 INSERT INTO T (X)
 VALUES (@X);

 FETCH NEXT FROM @C1 INTO @X;
 END

Then checked the page layout with

SELECT page_id,
 X,
 geometry::Point(page_id, X, 0).STBuffer(1)
FROM T
 CROSS APPLY sys.fn_PhysLocCracker( %% physloc %% )
ORDER BY page_id

Results were all over the place. The first row in key order (with value 1 - highlighted with arrow below) was on nearly the last physical page.

http://i.stack.imgur.com/OL6eY.png

Fragmentation can be reduced or removed by rebuilding or reorganising an index to increase the correlation between logical order and physical order.

After running

ALTER INDEX ix ON T REBUILD;

I got the following

http://i.stack.imgur.com/ETaJd.png

Tables without clustered indexes

If the table has no clustered index it is called a heap. Non clustered indexes can be built on either a heap or a clustered index. They always contain a row locator back to the base table. In the case of a heap this is a physical row identifier (rid) and consists of three components (File:Page:Slot). In the case of a Clustered index the row locator is logical (the clustered index key).

For the latter case if the non clustered index already naturally includes the CI key column(s) either as NCI key columns or INCLUDE-d columns then nothing is added. Otherwise the missing CI key column(s) silently get added in to the NCI.

Slightly amending the example from earlier and creating a non clustered index on a heap we can see that in addition to all the table columns (as this nonclustered index was defined to include all of them) the index leaf level now contains another 8 bytes for the RID

CREATE TABLE T
 (
 A INT NOT NULL,
 B INT NOT NULL,
 C INT NOT NULL,
 D INT NOT NULL
 );

CREATE UNIQUE NONCLUSTERED INDEX nci
 ON T(A, B)
 INCLUDE (C, D);

INSERT INTO T
VALUES (1,2,3,4);

http://i.stack.imgur.com/Y4c63.png

SQL Server always ensures that the key columns are unique for both types of index. The mechanism in which this is enforced for indexes not declared as unique differs between the two index types however.

Clustered indexes get a uniquifier added for any rows with key values that duplicate an existing row. This is just an ascending integer.

For non clustered indexes not declared as unique SQL Server silently adds the row locator in to the non clustered index key. This applies to all rows, not just those that are actually duplicates.

The clustered vs non clustered nomenclature is also used for column store indexes. The paper Enhancements to SQL Server Column Stores states

Although column store data is not really "clustered" on any key, we decided to retain the traditional SQL Server convention of referring to the primary index as a clustered index.

Share via