B-Trees: Difference Between Clustered and Non-Clustered Indices

B-Trees
First lets be clear on what a B-Tree is, and why they are important in Database Systems. A B-Tree index provides fast access to data by searching on a key value of the index. B-Trees cluster records with similar keys. The B stands for balanced (not binary!), and balancing the tree is a core feature of the B-tree’s usefulness. The trees are managed and branches are grafted as necessary, so navigating down the tree to find a value and locate a specific record takes only a few page accesses. Because the trees are balanced, finding any record only requires (about) the same number of resources, and retrieval speed is consistent because index has the same depth throughout the tree.

In any index, whether clustered or non-clustered, the leaf level contains every key value (or combination of values for composite indices) in key sequence. The biggest difference between a clustered and non-clustered index is what else in the leaf. Below I'll explain in detail what the difference between a Clustered and Non-clustered index is:

Clustered Index
The leaf level of a clustered index contains the data pages, not just the index keys. Read that last line again. All columns of every row are in the leaf level; the data itself is part of the index. A clustered index keeps the data in a table ordered around the key. The data pages in the table are kept in a doubly linked list called a page chain (In a Heap pages are not linked together). Therefore the order of pages in the page chain, and the order of rows on the data pages, is the order of the index key or keys. When the key is found in a clustered index the data has been found, not simply pointed to.

Since the actual page chain for the data pages can only be ordered in one way, a table can only have one clustered index. It is a common misconception that clustered indexes store the data in sorted order on the disk. Sorted order simply means that the data page chain is logically in order, if the SQL Server follows the page chain it can access each row in the clustered index key order. New pages can be added simply by adjusting the links in the page chain

Non-Clustered Index
In a non-clustered index, the leaf level does not contain all the data. In addition to the key values, each inde row in the leaf level contains a bookmark that tells you where to find the data row corresponding to the key in the index. If the table is a heap (no clustered index) the non-clustered index’s bookmarks are row identifiers (RID) which is an actual row locator in the form File#.Page#.Slot#

The presence or absence of a non-clustered index does not affect how the data pages are organized; therefore you are not restricted to only having one non-clustered index per table. When you search for data using a non-clustered index the index is traversed, and then SQL server retrieves the record or records pointed to by the leaf-level indexes.