Clustered and non-clustered index

Question

Is it possible to create a non clustered index which is not unique? What data structure is used to implement non clustered indexes.

Answer 1

Assuming you are talking about SQL Server then simply don't specify UNIQUE when creating the index.

CREATE /*UNIQUE*/ NONCLUSTERED INDEX IX ON T(C)

As UNIQUE is commented out above this does not enforce uniqueness on the C column. But in fact it will still be made unique behind the scenes by adding the (unique) row locator in to the non clustered index key.

Regarding data structure both clustered and non clustered indexes are B+ trees.

Answer 2

As stated by Martin Smith, the indexes don't need to be logically unique but in practice, SQL Server adds a 4 byte 'uniquifier' column to guarantee physical uniqueness.

In terms of structural difference, the non-clustered indexes include pointers to the clustered index or the heap pointer (if you haven't created a clustered index).

You should note that while they are both B-Trees, there are other differences - non-clustered indexes have their leaf nodes 1 level higher, which can mean reading from non-clustered indexes can be faster than reading from a clustered index providing the data required is available in the leaf nodes (the columns required are in the key of the index).

Here's the clustered index structure from Books Online:

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

Here's the non-clustered index structure:

http://technet.microsoft.com/en-gb/library/ms177484(v=sql.105).aspx

So, reading from a 'covered' non-clustered index can be faster as each level incurs 1 page read so because the non-clustered index has fewer levels to get to the data then you will incur fewer logical reads which in turn will mean fewer physical disk reads and less work for the CPU.

You should also consider that covering indexes with only the specific columns required for a specific query will mean fewer total pages need to be read to grab all the data resulting in faster performance but also be aware that the more indexes you have, the more cost your writes will incur.