Index Organization

Indexing

Creating a clustered index on the table means, sorting rows on the give clustering key and placing in order. These rows are placed as a list in the pages. As no. of rows increases, we require more no. of pages. for eg, a table with 10k rows may be distributed over 5 pages. even though they are distributed in multiple pages, they logically represent a table. As no. of rows in a table (group of pages forming a logical table) increases say 1 million rows, it will be time taking factor to query from this huge list. In order to reduce time in selecting from this huge list, we further divide into partitions. Now, these 1 million row data is divided across multiple partitions say 10 partitions and each partition containing 100K rows. 

In short, creating a clustered index in ordering rows in a table. Pages containing rows are indexed using a balanced tree structure. traversing between pages is done using doubly linked list implemented on the pages.

Creating a non-clustered index on a column, takes row locations of all rows and sorts them forming a b-tree structure. When we traverse through b-tree doesn't point to actual rows, instead contains either pointer to row or clustered index key of the row.

Reference:

Table and Index Organization

Cluster Index

Non-Clustered Index

Questions to get answers for:

1. how non-numeric columns are sorted ?