Clustered vs non-clustered tables

It happened I had to work with both SQL Server and Oracle for quite a while (thankfully not at the same time).

What still puzzles me is the approach to storing tables as balanced trees. In Oracle-like RDMS heap is default, in SQL Server (and many others ) the reverse (clustered, IOT) is true. Adepts of each approach claim their way is the only 'correct' and support chosen point of view with bunch of tests/presentations. However, in my opinion, the only point they proved is that implementation of "non-default" approach is poor, and it shouldn't be used for the most cases...

I'm pretty sure both approaches are good enough (just because they still exist on the market and show comparable performance) and have some math underneath, but I've failed to find any good references.

I realize the topic may be too broad to answer, and good links are very welcome, but I really want to know why two seemingly controversial approaches have proven they are both valid.

I was in the same position when I started my career as a SQL Server DBA, but studied mostly ORACLE (10g) at my university .. and that OCA stuff as well...

I agree to @KennethFisher that both RDBMS are different and comparing them is like - comparing Apples and Oranges.

To answer your question regarding - storing tables as balanced trees ...

• Both Oracle & SQL Server support B-Tree Indexes which keeps data sorted and allows searches, sequential access, insertions and deletions in logarithmic time.

• B-Tree is well optimized for systems that read and write large blocks of data. Note that SQL Server uses this structure for Non-clustered Indexes and Oracle

uses it as a default to store the storage location of the table internally.

• Oracle has a concept of ROWID (row id) and UROWID (universal Row ID) where in the key values and a Unique reference to the storage location of the record is contained and this represents the physical location on the disk that the record is stored.

e.g. Reference Overview of ROWID and UROWID Datatypes

SELECT ROWID, last_name FROM employees WHERE department_id = 20; 

ROWID              LAST_NAME 
------------------ ---------- 
AAAAaoAATAAABrXAAA BORTINS 
AAAAaoAATAAABrXAAE RUGGLES 
AAAAaoAATAAABrXAAG CHEN 
AAAAaoAATAAABrXAAN BLUMBERG

An extended rowid has a four-piece format, OOOOOOFFFBBBBBBRRR:


OOOOOO: The data object number that identifies the database segment (AAAAao in the example). Schema objects in the same segment, such as a cluster of tables, have the same data object number.


FFF: The tablespace-relative datafile number of the datafile that contains the row (file AAT in the example).


BBBBBB: The data block that contains the row (block AAABrX in the example). Block numbers are relative to their datafile, not tablespace. Therefore, two rows with identical block numbers could reside in two different datafiles of the same tablespace.


RRR: The row in the block.

• Hence the concepts are completely different in both RDBMS - ORACLE and SQL Server. Also, PK's created in Oracle are nothing but Balanced non-clustered indexes with ROWID for fast access and therefore no concept of either clustered or non-clustered indexes.

Now, this gets more interesting and different when it comes to B+Tree indexes:

-
B+Tree structures are similar to B-Tree structures, but the table records (actual data) is stored in the leaf nodes of the Primary key Index allowing fast access for exact match or range scan searches on the PK of the table.

-
Oracle uses what is called IOT (Index Organized Tables) and SQL Server uses what is called Clustered Indexes.

Lets look at Clustered Indexes and Index Organized tables (IOT) ...:

From Oracle Doc,


An index-organized table is a table stored in a variation of a B-tree index structure. In a heap-organized table, rows are inserted where they fit. In an index-organized table, rows are stored in an index defined on the primary key for the table. Each index entry in the B-tree also stores the non-key column values. Thus, the index is the data, and the data is the index. Applications manipulate index-organized tables just like heap-organized tables, using SQL statements.

From SQL Server Doc,


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.

• Statistics for IOT's includes the Physical scatter of rows whereas SQL Server does not include Physical location of the rows in statistics and hence Clustered Index in SQL Server is better than a HEAP - data is sorted by the clustered key and good estimates are obtained for the data to be searched.

At last some good references :

• Statistics in Oracle and SQL Server - by Jonathan Lewis and Grant Fritchey

• Oracle Heap Tables or SQL Server Clustered Indexes? - by Jonathan Lewis and Grant Fritchey

• Index Organized Tables – the Basics - Excellent series !

• Fixing heap fragmentation

• Internals and Deletes

I will add more points when I come across that are worth mentioning...

StackExchange Database Administrators Q#45485, answer score: 5