Index Structures in SQL Server

In SQL Server, all indexes are organized on B-trees except ColumnStore indexes. In a B-tree, every single page is known as Index node which is responsible to allow keyed access to data because it contains the pair of key value and pointer. In the Index, the top node of the B-tree is called the root node and the lowest nodes are called the leaf nodes. All index levels between the top node (Root Node) and bottom nodes (Leaf nodes) are known as intermediate levels or nodes.

If we are taking about a clustered index structure then we see that the leaf nodes are containing multiple data pages. There are multiple index pages between the root and intermediate level nodes to hold the index rows. We already stated that index row contains a key value and a pointer to either an intermediate level page in the B-tree, or a data row in the leaf level of the index. The pages in each level of the index are linked in a doubly-linked list.
Clustered Index structure in SQL Server

How does SQL Server navigate a clustered index?

Nonclustered Index structure in SQL Server

How does Nonclustered index navigate on a Heap?

SQL Server B-Tree Rules

There are some standard rules of B-Tree which are given below-

• Root and intermediate nodes point only to other nodes where Root node is the top most layer of the index structure.
• Only, the lowest node means leaf nodes point to data pages.
• The number of nodes between the root and any leaf is the same for all leaves
• A node always contains between K and K/2 branches, where K is the branching factor
• Branching factor is the number of keys in the node
• B-trees are always sorted
• The tree will be maintained during insertion, deletion, and updating so that these rules are met
• When records are inserted or updated, nodes may split
• When records are deleted, nodes may be collapsed 
• Index page fragmentation occurs when a new key-pointer pair must be added to an index page that is full 
• Repair index fragmentation by rebuilding index
• Rebuilding clustered index repairs table fragmentation

Conclusion

The clustered index is implemented as a B-treeindex structure that supports fast retrieval of the rows, based on their clustered index key values. The pages in each level of the index, including the data pages in the leaf level, are linked in a doubly-linked list. However, navigation from one level to another is performed by using key values.

References: https://technet.microsoft.com/en-us/library/ms177443(v=sql.105).aspx