SQL Server Table and Index Structure

Most of this post is about a collection from MSDN.

SQL Server uses B+ tree to create index. That means it can be not balanced.

In a B-Tree index, each page contains pointers pointing to previous page and next page in the same index level. In SQL Server, it has 96 bytes for the header. This is same in both index page and data page. In the data part of the index page, each index row points to page in next level towards to leaf.

Another type of index is bitmap index, which is not supported in SQL Server. It's designed for rows with lot of duplicate and good for analytic processes. Its overhead on DML is heavier than B-Tree index.

Table:

A table is contained in one or more partitions and each partition contains data rows in either a heap or a clustered index structure. The pages of the heap or clustered index are managed in one or more allocation units, depending on the column types in the data rows.

A partition is a user-defined unit of data organization. When a table or index uses multiple partitions, the data is partitioned horizontally so that groups of rows are mapped into individual partitions, based on a specified column. The partitions can be put on one or more filegroups in the database.

To view the partitions used by a table or index, use the sys.partitions (Transact-SQL) catalog view.



Allocation Unit:
IN_ROW_DATA, ROW_OVERFLOW_DATA, LOB_DATA

HEAP: a table without a clustered index

index_id=0 in sys.partitions.

The data rows are not stored in any particular order, and there is no particular order to the sequence of the data pages. The data pages are not linked in a linked list

The column first_iam_page in the sys.system_internals_allocation_units system view points to the first IAM page in the chain of IAM(Index Allocation Map) pages that manage the space allocated to the heap in a specific partition. SQL Server uses the IAM pages to move through the heap. The data pages and the rows within them are not in any specific order and are not linked. The only logical connection between data pages is the information recorded in the IAM pages.

Clustered Index Structure:

 index_id=1 in sys.partitions table

Non-Clustered index Structure:

index_id>1 in sys.partitions

Each index row contains the nonclustered key value, a row locator (RID or Clustered index Keys) and any included, or nonkey, columns.