In-depth Understanding of Non-Clustered Index Structure in SQL Server

Is a non-clustered index also a heap structure? Actually, SQL Server uses several types of pages (data is stored page by page, just like how Windows organizes memory in pages). For those interested, this article aims to deepen your understanding of non-clustered index structures.

We know that SQL Server stores data rows using two types of data structures:
A: Heap
B: B-tree (binary tree)

Data is sorted and stored according to one of these two structures. Those familiar with data structures will recognize binary trees—why use them? Because they enable efficient binary search for fast data retrieval.

In a heap, data is not sorted in any order and lacks inherent structure. Data pages are not linked sequentially, unlike in a B-tree, where data pages are connected via doubly-linked lists. A heap table relies solely on IAM pages (Index Allocation Map pages) to link its data pages together. The IAM records page IDs and physical locations.

Unless a table has a clustered index, its data is stored as a heap.

So what about non-clustered indexes? Are they also heap structures?

Actually, SQL Server uses multiple page types (remember: all data is stored in pages, similar to how Windows manages memory in pages). Two key types are:

• Index pages
• Data pages

Many books (including my initial wording in this article) state:

"Data rows are stored in two structures: A) Heap, B) B-tree."

But I now believe this phrasing is slightly misleading. It's more accurate to say:

"Data pages are organized in two ways: 1) Heap, 2) B-tree."

Let's clarify:

• Index pages: Whether clustered or non-clustered, all index data resides in index pages, which are always structured as B-trees.
• Data pages:
  • If the table has no clustered index, actual data rows are stored in heap pages.
  • If the table has a clustered index, the data rows are stored within the leaf-level pages of the clustered index itself (i.e., in index pages).

In a B-tree, each node is also called a page. Every B-tree includes a root page (the root node)—this applies equally to both clustered and non-clustered indexes.

So now the original statement makes sense:

"Data rows are stored in two structures: A) Heap, B) B-tree."

In a heap, data pages are stored randomly. The only logical connection between them is recorded in the IAM page, which effectively acts as the root page for the heap.

What about clustered indexes? Are they heap structures?

No. Non-clustered indexes are stored in index pages (B-tree structure), while the actual data remains in heap pages—unless a clustered index exists.

When data resides in a heap (i.e., no clustered index), how does a non-clustered index link to the actual data?

The answer lies in the row locator stored in the leaf nodes (leaf pages) of the non-clustered index.

Non-clustered and clustered indexes share the same B-tree structure, but differ significantly in the following aspects:

1. Base table data rows are not sorted or stored in non-clustered key order.
2. The leaf level of a non-clustered index consists of index pages, not data pages.
3. A table with a non-clustered index can be either a B-tree (if it has a clustered index) or a heap (if it doesn’t).
4. If the table is a heap (i.e., no clustered index), the row locator is a pointer to the physical location of the row, composed of:
   File ID : Page Number : Row Slot Number.
   This pointer is called a Row ID (RID).
5. If the table has a clustered index (or if the index is on an indexed view with a clustered index), the row locator points to the clustered index key. SQL Server uses this key value—stored in the non-clustered index leaf—to search the clustered index and retrieve the actual data.

Importantly, non-clustered indexes do not alter or improve the physical storage layout of the actual data pages. Their B-tree structure applies only to their own index pages.

Nevertheless, like clustered indexes, non-clustered indexes function similarly to a lookup table (like an index in a book).

Final Summary

What’s the point of this short note?
It’s about clarifying table structures, as someone once asked on a forum: “What are the possible structures of a table?”

• A: Table with a clustered index (with or without non-clustered indexes) → B-tree
• B: Table with no indexes at all → Heap
• C: Table without a clustered index but with non-clustered indexes → B-tree (for indexes) + Heap (for data)

In forum discussions, people often refer to:

• A as a "clustered table"
• B and C as "heap tables"

I recall my university data structures professor teaching concepts like max-heaps, min-heaps, doubly-linked lists, and binary trees…
Unfortunately, I’ve long since returned all that knowledge to him!

Below are illustrative diagrams:

Heap Table Structure

Non-Clustered Index Structure

Clustered Index Structure

Source: https://www.jb51.net/article/33429.htm