Understanding clustered index

Question

Since PostgreSQL doesn't support clustered indexes, I'm considering MSSQL server. I've read the article comparing clustered and non-clustered indexes. The gist of the article is that (emphasize mine):

Non clustered indexes store both a value and a pointer to the actual row that holds that value.

And

Clustered indexes don’t need to store a pointer to the actual row because of the fact that the rows in the table are stored on disk in the same exact order as the clustered index

As I was told there and there it was very difficult to support the physical ordering of the table's data, especially if the table is splitted among multiple drives. And now, I meet the clustered index concept assuming that data stored in some order physically. This's what I was confused by.

Question: What is the clustered index structure? Does it support tree-like structure to traverse over, like PosgtreSQL does for btree indexes?

Answer 1

In SQL Server, indexes are organized as B-trees. Each page in an index B-tree is called an index node. The top node of the B-tree is called the root node. The bottom level of nodes in the index is called the leaf nodes. Any index levels between the root and the leaf nodes are collectively known as intermediate levels. In a clustered index, the leaf nodes contain the data pages of the underlying table. The root and intermediate level nodes contain index pages holding index rows. Each index row contains a key value and a pointer to either an intermediate level page in the B-tree, or a data row in the leaf level of the index. The pages in each level of the index are linked in a doubly-linked list.

Clustered indexes have one row in sys.partitions, with index_id = 1 for each partition used by the index. By default, a clustered index has a single partition. When a clustered index has multiple partitions, each partition has a B-tree structure that contains the data for that specific partition. For example, if a clustered index has four partitions, there are four B-tree structures; one in each partition.

for ref.

https://technet.microsoft.com/en-us/library/ms177443(v=sql.105).aspx http://www.sqlservercentral.com/blogs/practicalsqldba/2013/03/14/sql-server-part-4-explaining-the-non-clustered-index-structure-/