principlesqlModerate
Clustered vs Nonclustered indexes, similar to arrays vs linked lists?
Viewed 0 times
clusteredarraysindexesnonclusteredlinkedlistssimilar
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Database Administrators Q#141185, answer score: 11
Revisions (0)
No revisions yet.