I'm just starting out as a DBA, and have recently been interested in indexes and how they speed up queries. I was reading about indexes here:
https://msdn.microsoft.com/en-us/library/ms190457.aspx and trying to understand the difference between a clustered index and a non-clustered index in SQL Server.
From what I read, it sounds like a clustered index sorts the data so the index always 'knows' where the next value lies, directly next to it. This reminded me of an array with contiguous memory. Similarly, a nonclustered index sounded like a linked list, in that there is a part of the index which holds the value, and also a part of the index which points to the next index. Is this an apt compiarison to make?
Best Answer
The difference is not like arrays vs. linked lists (Both are data structures - But not the correct ones.). Both types of indexes use B-Trees (Data Structure) to organize the data. The difference is how the B-Tree is organized.
For a clustered index, the data is organized in the data structure with the leafs being physically organized on the disk. This has a few implications: 1) Increases the overhead on inserts. 2) Speeds up the whole search since the disk reader head does not have to travel all over the disk to find things and 3) You can only create 1 clustered index per table.
For a non-clustered index, the B-Tree indexes just like the clustered, except the leaf nodes only contain pointers to the physical location on the disk. This means that you can have more then 1 per table. While this is not as fast as a clustered in that all the data is in a known, organized manner, it at least is a location where the system can go to lookup where that data is located instead of having to scan over the whole disk.
Source: https://msdn.microsoft.com/en-us/library/ms190457.aspx