What is the difference between a clustered and a non-clustered index?

A telephone directory is sorted by surname. The data itself is in that order, so finding "Sharma" means flipping straight to the S pages, and all the Sharmas sit together. That is a clustered index. A book can only be physically sorted one way, so there is only one.

The index at the back of a textbook is different. It lists topics alphabetically with page numbers. You look up "Normalization", read "page 212", then turn to that page. That is a non-clustered index: a separate list that points to where the real content lives. A book can have several such indexes: by topic, by author name, by figure number.

SQL Server syntax, where the difference is explicit:

CREATE TABLE orders (
  order_id    int NOT NULL,
  customer_id int NOT NULL,
  order_date  date NOT NULL,
  amount      decimal(10, 2)
);

-- One clustered index: rows are stored in order_id order
CREATE CLUSTERED INDEX ix_orders_id ON orders (order_id);

-- Many non-clustered indexes: separate structures pointing back to rows
CREATE NONCLUSTERED INDEX ix_orders_customer ON orders (customer_id);
CREATE NONCLUSTERED INDEX ix_orders_date ON orders (order_date) INCLUDE (amount);

In SQL Server, a PRIMARY KEY creates a clustered index by default if the table does not have one already.

Both are usually B-tree structures. In a clustered index the leaf level holds the actual rows. In a non-clustered index the leaf level holds the key and a locator: the clustered key value if the table has a clustered index, or a physical row ID if it does not.

How common databases handle this:

• MySQL InnoDB: every table is clustered on its primary key. If there is no primary key, InnoDB uses the first unique NOT NULL index, or creates a hidden row ID. Secondary indexes store the primary key value, so a big primary key makes every secondary index bigger.
• SQL Server: you choose which index is clustered; a table without one is called a heap.
• PostgreSQL: tables are always heaps and all indexes are separate structures, so in SQL Server terms every PostgreSQL index is non-clustered. The CLUSTER command reorders a table by an index once, but the order is not maintained for new rows.

• Cluster an orders table on an increasing order_id or created_at, so new rows go at the end and "orders from last week" reads neighbouring pages.
• Add non-clustered indexes on columns you filter by, such as customer_id or a phone number on a users table.
• Use a covering index (INCLUDE columns) for a frequent query, so it never has to visit the table.

• Saying a table can have several clustered indexes. It has at most one, because rows can be stored in only one order.
• Assuming the primary key and the clustered index are always the same thing. They often are by default, but in SQL Server you can cluster on a different column.
• Choosing a random value, like a random UUID, as the clustered key. Inserts land all over the table and cause page splits and fragmentation.
• Describing PostgreSQL indexes as clustered because of the CLUSTER command.

• What is a covering index, and what is a key lookup?
• Why is a narrow, increasing primary key preferred in InnoDB?
• What is a page split?