5

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?

  • Think of clustered index as a table ordered by a key in a reverse B-Tree format. This way it always knows where that key is and can get to it right away. It's just another way of saying 'table that's ordered by whatever key you give it'. Think of non-clustered indexes as a COPY of the table's values that you have. If ALL the data you need isn't in the index, it'll often just go look at the base table or do a very expensive bookmark lookup if statistics say it's a minimal amount of lookingup, like 5% or so if I recall. – Ali Razeghi Jun 14 '16 at 17:32
2

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

  • 1
    " the leaf nodes only contain pointers to the physical location on the disk.". When the table is clustered, the leaves only contain the CI values, not any pointers. From the page you linked: "The pointer from an index row in a nonclustered index to a data row is called a row locator. The structure of the row locator depends on whether the data pages are stored in a heap or a clustered table. For a heap, a row locator is a pointer to the row. For a clustered table, the row locator is the clustered index key." – ypercubeᵀᴹ Jun 14 '16 at 18:25
  • Thank you for clarifying that ypercube. I read that page a few years ago and it felt like I was glossing over nonclustered indexes. – Antiparadigm Jun 14 '16 at 18:47
  • 2
    You can edit and correct your answer ;) – ypercubeᵀᴹ Jun 14 '16 at 18:57
  • This made it all make perfect sense to me, thank you. Max's answer is also very helpful, but personally I found this answer to directly answer my question! – Mattkwish Jun 15 '16 at 14:45
11

Hmmm... The leaf level of a clustered index is the table in SQL Server. This is comparable to a phone book (to borrow from @BrentO) in that all entries in the book are stored in the order of the index - i.e. The index is ordered logically alphabetically (and physically if there is no fragmentation). This is somewhat similar to a physically contiguous in-memory array, although SQL Server can make no guarantees about data being stored contiguously on disk or about physical order. Each page at leaf level of either index type is part of a doubly linked list and has pointers to the previous and next pages in key order, an ordered index scan uses these to traverse the index in key order.

A non-clustered index is similar to an index at the back of a book in that the index itself is sorted, making it easy to find an item in the index. You might have two non-clustered indexes, one listing all the phone book entries by phone number, and one listing all the phone book entries by address. The clustered index (the actual phone book) is laid out physically by the name of the owner of the phone number. This makes sense since you typically "look up" a phone number by "name of owner". This is somewhat analogous to an in-memory contiguous array of pointers that point to the locations of the actual data. The array only holds the index details.

If you only knew the phone number for a person, and needed to know their name, it would take a very long time indeed to find the name by looking through the entire book, name-by-name, for the number, when instead you could simply look at the phone number index to find the name of the owner. This is how a non-clustered index works.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.