What do Clustered and Non-Clustered index actually mean?

Question

I have a limited exposure to DB and have only used DB as an application programmer. I want to know about Clustered and Non clustered indexes. I googled and what I found was :

A clustered index is a special type of index that reorders the way records in the table are physically stored. Therefore table can have only one clustered index. The leaf nodes of a clustered index contain the data pages. A nonclustered index is a special type of index in which the logical order of the index does not match the physical stored order of the rows on disk. The leaf node of a nonclustered index does not consist of the data pages. Instead, the leaf nodes contain index rows.

What I found in SO was What are the differences between a clustered and a non-clustered index?.

Can someone explain this in plain English?

Solution 1

With a clustered index the rows are stored physically on the disk in the same order as the index. Therefore, there can be only one clustered index.

With a non clustered index there is a second list that has pointers to the physical rows. You can have many non clustered indices, although each new index will increase the time it takes to write new records.

It is generally faster to read from a clustered index if you want to get back all the columns. You do not have to go first to the index and then to the table.

Writing to a table with a clustered index can be slower, if there is a need to rearrange the data.

Solution 2

A clustered index means you are telling the database to store close values actually close to one another on the disk. This has the benefit of rapid scan / retrieval of records falling into some range of clustered index values.

For example, you have two tables, Customer and Order:

Customer
----------
ID
Name
Address

Order
----------
ID
CustomerID
Price

If you wish to quickly retrieve all orders of one particular customer, you may wish to create a clustered index on the "CustomerID" column of the Order table. This way the records with the same CustomerID will be physically stored close to each other on disk (clustered) which speeds up their retrieval.

P.S. The index on CustomerID will obviously be not unique, so you either need to add a second field to "uniquify" the index or let the database handle that for you but that's another story.

Regarding multiple indexes. You can have only one clustered index per table because this defines how the data is physically arranged. If you wish an analogy, imagine a big room with many tables in it. You can either put these tables to form several rows or pull them all together to form a big conference table, but not both ways at the same time. A table can have other indexes, they will then point to the entries in the clustered index which in its turn will finally say where to find the actual data.

Solution 3

In SQL Server, row-oriented storage both clustered and nonclustered indexes are organized as B trees.

(Image Source)

The key difference between clustered indexes and non clustered indexes is that the leaf level of the clustered index is the table. This has two implications.

1. The rows on the clustered index leaf pages always contain something for each of the (non-sparse) columns in the table (either the value or a pointer to the actual value).
2. The clustered index is the primary copy of a table.

Non clustered indexes can also do point 1 by using the INCLUDE clause (Since SQL Server 2005) to explicitly include all non-key columns but they are secondary representations and there is always another copy of the data around (the table itself).

CREATE TABLE T
(
A INT,
B INT,
C INT,
D INT
)

CREATE UNIQUE CLUSTERED INDEX ci ON T(A, B)
CREATE UNIQUE NONCLUSTERED INDEX nci ON T(A, B) INCLUDE (C, D)

The two indexes above will be nearly identical. With the upper-level index pages containing values for the key columns A, B and the leaf level pages containing A, B, C, D

There can be only one clustered index per table, because the data rows themselves can be sorted in only one order.

The above quote from SQL Server books online causes much confusion

In my opinion, it would be much better phrased as.

There can be only one clustered index per table because the leaf level rows of the clustered index are the table rows.

The book's online quote is not incorrect but you should be clear that the "sorting" of both non clustered and clustered indices is logical, not physical. If you read the pages at leaf level by following the linked list and read the rows on the page in slot array order then you will read the index rows in sorted order but physically the pages may not be sorted. The commonly held belief that with a clustered index the rows are always stored physically on the disk in the same order as the index key is false.

This would be an absurd implementation. For example, if a row is inserted into the middle of a 4GB table SQL Server does not have to copy 2GB of data up in the file to make room for the newly inserted row.

Instead, a page split occurs. Each page at the leaf level of both clustered and non clustered indexes has the address (File: Page) of the next and previous page in logical key order. These pages need not be either contiguous or in key order.

e.g. the linked page chain might be 1:2000 <-> 1:157 <-> 1:7053

When a page split happens a new page is allocated from anywhere in the filegroup (from either a mixed extent, for small tables or a non-empty uniform extent belonging to that object or a newly allocated uniform extent). This might not even be in the same file if the filegroup contains more than one.

The degree to which the logical order and contiguity differ from the idealized physical version is the degree of logical fragmentation.

In a newly created database with a single file, I ran the following.

CREATE TABLE T
  (
     X TINYINT NOT NULL,
     Y CHAR(3000) NULL
  );

CREATE CLUSTERED INDEX ix
  ON T(X);

GO

--Insert 100 rows with values 1 - 100 in random order
DECLARE @C1 AS CURSOR,
        @X  AS INT

SET @C1 = CURSOR FAST_FORWARD
FOR SELECT number
    FROM   master..spt_values
    WHERE  type = 'P'
           AND number BETWEEN 1 AND 100
    ORDER  BY CRYPT_GEN_RANDOM(4)

OPEN @C1;

FETCH NEXT FROM @C1 INTO @X;

WHILE @@FETCH_STATUS = 0
  BEGIN
      INSERT INTO T (X)
      VALUES        (@X);

      FETCH NEXT FROM @C1 INTO @X;
  END

Then checked the page layout with

SELECT page_id,
       X,
       geometry::Point(page_id, X, 0).STBuffer(1)
FROM   T
       CROSS APPLY sys.fn_PhysLocCracker( %% physloc %% )
ORDER  BY page_id

The results were all over the place. The first row in key order (with value 1 - highlighted with an arrow below) was on nearly the last physical page.

Fragmentation can be reduced or removed by rebuilding or reorganizing an index to increase the correlation between logical order and physical order.

After running

ALTER INDEX ix ON T REBUILD;

I got the following

If the table has no clustered index it is called a heap.

Non clustered indexes can be built on either a heap or a clustered index. They always contain a row locator back to the base table. In the case of a heap, this is a physical row identifier (rid) and consists of three components (File:Page: Slot). In the case of a Clustered index, the row locator is logical (the clustered index key).

For the latter case if the non clustered index already naturally includes the CI key column(s) either as NCI key columns or INCLUDE-d columns then nothing is added. Otherwise, the missing CI key column(s) silently gets added to the NCI.

SQL Server always ensures that the key columns are unique for both types of indexes. The mechanism in which this is enforced for indexes not declared as unique differs between the two index types, however.

Clustered indexes get a uniquifier added for any rows with key values that duplicate an existing row. This is just an ascending integer.

For non clustered indexes not declared as unique SQL Server silently adds the row locator into the non clustered index key. This applies to all rows, not just those that are actually duplicates.

The clustered vs non clustered nomenclature is also used for column store indexes. The paper Enhancements to SQL Server Column Stores states

Although column store data is not really "clustered" on any key, we decided to retain the traditional SQL Server convention of referring to the primary index as a clustered index.

Solution 4

I realize this is a very old question, but I thought I would offer an analogy to help illustrate the fine answers above.

CLUSTERED INDEX

If you walk into a public library, you will find that the books are all arranged in a particular order (most likely the Dewey Decimal System, or DDS). This corresponds to the "clustered index" of the books. If the DDS# for the book you want was 005.7565 F736s, you would start by locating the row of bookshelves that is labeled 001-099 or something like that. (This endcap sign at the end of the stack corresponds to an "intermediate node" in the index.) Eventually you would drill down to the specific shelf labelled 005.7450 - 005.7600, then you would scan until you found the book with the specified DDS#, and at that point you have found your book.

NON-CLUSTERED INDEX

But if you didn't come into the library with the DDS# of your book memorized, then you would need a second index to assist you. In the olden days you would find at the front of the library a wonderful bureau of drawers known as the "Card Catalog". In it were thousands of 3x5 cards -- one for each book, sorted in alphabetical order (by title, perhaps). This corresponds to the "non-clustered index". These card catalogs were organized in a hierarchical structure, so that each drawer would be labeled with the range of cards it contained (Ka - Kl, for example; i.e., the "intermediate node"). Once again, you would drill in until you found your book, but in this case, once you have found it (i.e, the "leaf node"), you don't have the book itself, but just a card with an index number (the DDS#) with which you could find the actual book in the clustered index.

Of course, nothing would stop the librarian from photocopying all the cards and sorting them in a different order in a separate card catalog. (Typically there were at least two such catalogs: one sorted by author name, and one by title.) In principle, you could have as many of these "non-clustered" indexes as you want.

Solution 5

Find below some characteristics of clustered and non-clustered indexes:

Clustered Indexes

1. Clustered indexes are indexes that uniquely identify the rows in an SQL table.
2. Every table can have exactly one clustered index.
3. You can create a clustered index that covers more than one column. For example: create Index index_name(col1, col2, col.....).
4. By default, a column with a primary key already has a clustered index.

Non-clustered Indexes

1. Non-clustered indexes are like simple indexes. They are just used for fast retrieval of data. Not sure to have unique data.

View more solutions

Comments

[Rick]

These two videos (Clustered vs. Nonclustered Index Structures in SQL Server and Database Design 39 - Indexes (Clustered, Nonclustered, Composite Index) ) are more helpful than a plain text answer in my opinion.

[rookie]

You should clarify what you mean by "physically".

[Peter]

physically as in the actual bits stored on the disk

[Hibou57]

“There can therefore be only one clustered index.”: I don't see the point, and SQL shows every day you can order on multiple indexes or columns. By the way, a complementary question: I heard to say with MS‑SQL server, a primary key always defines a clustered index… is it true with other databases as well?

[Ming]

Refer to msdn "When you create a PRIMARY KEY constraint, a unique clustered index on the column or columns is automatically created if a clustered index on the table does not already exist", which means it's not necessary have to be the same column.

[Nigel]

One slight correction to Point 1. A clustered index does not necessarily uniquely identify the rows in an SQL table. That's the function of a PRIMARY KEY

[mko]

That being said CI should be always used for PK

[Caltor]

So with a clustered index is it the records in the index or the table that are stored close together?

[FLGMwt]

@Caltor The table. The index is ordered by definition. For example, a btree would be ordered so that one can simply do address arithmetic to search. The idea of the cluster is to cater the table to the performance of a particular index. To be clear, the records of the table will be reordered to match the order that the index is originally in.

[FLGMwt]

@Caltor Not at all! Indeed, the documentation and the name itself are quite misleading. Having a "clustered index" really has quite little to do with the index. Conceptually, what you really have is "a table clustered on index x".

[Martin Smith]

@Pete that isn't the case. SQL Server certainly doesn't guarantee that all data files are laid out in a contiguous physical area of disc and there is zero file system fragmentation. It isn't even true that a clustered index is in order within the data file. The degree to which this isn't the case is the degree of logical fragmentation.

[brain storm]

Although your explanation for With a clustered index the rows are stored physically on the disk in the same order as the index is a false statement is convincing, almost all articles/blogs/database administrators claim that in clustered index, rows are physically sorted and stored contiguously

[Martin Smith]

@brainstorm yes I'm aware of that. Probably that is because of the phrasing on this MSDN page but to see that the phrasing there is somewhat misleading you just need to look at the fragmentation topics

[supercat]

@brainstorm: It's amazing how some false statements get repeated as gospel. A clustered indicates that, at least from the perspective of sequential reads, it would be "desirable" to have the rows stored physically on disk in the same order as the index, but that's a far cry from saying that it will cause them to actually be stored in such a fashion.

[InfZero]

@user151323, a second field to «uniquify» the index can be a date and time?

[Admin]

@JohnOrtizOrdoñez: Sure, you can use almost any that's stored in-row, so no XML, VARCHAR(MAX), or VARBINARY(MAX). Note that it usually makes sense to cluster on the date field first, as a clustered index is most efficient for range scans, which are most common on date types. YMMV.

[anar khalilov]

@Nigel, a PRIMARY KEY or a UNIQUE INDEX?

[gotqn]

@MartinSmith I have reproduced and confirmed the results of your test on SQL Server 2014. I get 95% fragmentation of the index after the initial insert. After index rebuild the fragmentation was 0% and the values were ordered. I am wondering, can we say that The only time the data rows in a table are stored in sorted order is when its clustered index fragmentation is 0?

[Martin Smith]

@gotqn Fragmentation also covers contiguity but basically yes.

[Ariel]

Great explanation, the visual part helped the understanding ! Just one question, the horizontal numbers mean the page right ? So as close the page numbers are for the register the better ?

[Martin Smith]

@Terkhos yes, the horizontal numbers are the page and the vertical ones the index key. The second graph has entirely different page numbers showing the rebuild used a new area later in the file. A perfectly unfragmented index would use contiguous pages in key order. Which the second graph is pretty close to.

[TheGameiswar]

@MartinSmith,this may be long question,but it helped me understand fragmentation,when i use spatial results as mentioned ,i am not able to see dots as shown in your image,can you please help understand ?

[Martin Smith]

@TheGameiswar - You might need to increase the number from 1 in STBuffer(1) if the pages cover a much wider range than they do in my example.

[Martin Smith]

@TheGameiswar - And you might need to boost it by quite a lot. Even into the thousands depending on how far apart the page numbers are. e.g. i.stack.imgur.com/SPtUD.png. So it could be improved by applying a scaling factor so that X and Y axis are both 1-100 based on min and max actual values.

[vaitrafra]

@MartinSmith Now, Sir, this is an answer. I'd love to see it on top of the responses list but as SO goes, "quick and simple" gets the upvoting.

[Martin Smith]

@vaitrafra - Thanks. This answer is 5 years younger than some on this page which hasn't helped the positioning.

[niico]

I have an index with very high fragmentation 98% - what is the recommended action - regular maintenance?

[blobbles]

Just a quick comment to back up Martin Smith's point - clustered indexes do not guarantee sequential storage on the disk. Managing exactly where data is placed on the disk is the job of the OS, not the DBMS. But it suggests that items are ordered generally according to the clustering key. What this means is that if the DB grows by 10GB, for instance, the OS may decide to put that 10GB in 5x2GB chunks on different parts of the disk. A clustered table covering the 10GB will be stored sequentially on each 2GB chunk, those 2GB chunks MAY NOT be sequential however.

[IDIR Samir]

This sentence sold me the concept in a second! thanks "If you wish to quickly retrieve all orders of one particular customer, you may wish to create a clustered index on the "CustomerID" column of the Order table ...... physically stored close to each other on disk (clustered) which speeds up their retrieval."

[Ashish Choudhary]

I know this is late but this video give a nice graphical explanation. youtube.com/watch?v=ITcOiLSfVJQ

[kmote]

I could, perhaps, extend this analogy to describe "Included" columns, which can be used with Non-Clustered Indexes: One could imagine a card in the card catalog including more than just a single book, but instead a list of all the published versions of the book, organized numerically by publication date. Just like in an "included column" this information is stored only at the leaf level (thus reducing the number of cards the librarian must create).

[Nelda.techspiress]

@MartinSmith Appreciate that you provided the graphics and the command to rebuild the index.

[OfirD]

Anyone who reads this answer should scroll down to @Martin Smith's answer and see why claiming that With a clustered index, the rows are stored physically on the disk in the same order as the index is simply wrong.

[Mohammed Noureldin]

Ok the idea is relatively clear, but when to non clustered index?

[Ciprian Tomoiagă]

Umm, why it is generally faster to read from a clustered index if you want to get back all the columns ? Maybe you meant all the rows ?

[Manachi]

It's a great answer but the question specifically said "in plain English". To me this implies they were after a high level explanation described simply (as the top answer is).

[Martin Smith]

@Manachi this answer was given 5 years after the original question was asked. The purpose of it is to correct some misleading aspects of those answers. The (now 8 year old) whims of the OP are not a concern of mine. Other readers may appreciate a lower level view.

[Oreo]

Oh my, that sys.fn_PhysLocCracker function is brilliant for visualising what the hell is going on!

[Dominik Szymański]

That's very good explanation that makes a lot of sense. Thank you bro for this bit of information. That one should be marked as correct answer, as the one that is marked contains false statemements.

[sfarbota]

Downvoted for confusing/inaccurate use of "physically on the disk".

[Denis]

great analogy - really helps to visualize it!

[barbecue]

Upvoted for using technically inaccurate but easily understood simplification to explain the concept in "plain English". When someone asks for a simplified explanation, nit-picking technical details is counterproductive.

[barbecue]

Downvoted for providing extremnely detailed highly technical response to a request for an answer in simple English. The OP's original question as asked DOES MATTER.

[ChenHuang]

The way you described is very clear to understand those complex theories. Thank you!

[Vladimir Sitnikov]

Nice try, yet it misses the vital meaning: table data ordering. See the official documentation docs.microsoft.com/en-us/sql/relational-databases/indexes/…. > Clustered indexes sort and store the data rows in the table or view based on their key values. These are the columns included in the index definition. There can be only one clustered index per table, because the data rows themselves can be stored in only one order.

[Vlad Mihalcea]

Your reply fits so well in this meme 😂