Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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.

enter image description here

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.

enter image description here

  • 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 :

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

share|improve this answer
    
Thank you very much for the answer and great references. I wouldn't agree with your metaphor regarding 'apples and oranges' though. –  a1ex07 Jul 1 '13 at 17:28
    
@a1ex07 Glad that it could help. The metaphor regarding 'apples and oranges' was specifically for how 2 different RDBMS stores the data as well as different Index options available for them. –  Kin Jul 1 '13 at 18:43
add comment

Actually there is a fairly simple answer. Oracle and similar RDBMS' are optimized to use heaps, while MS SQL Server and similar are optimized to use clustered indexes. If you take a look at the internals of each system you will find that their design is built to handle the chosen method. So in this particular case both groups of "Adepts" are correct. In SQL Server tables with clustered indexes function better, in Oracle heaps work better (in general in both cases). I'm not sure either approach is better or worse in general, it's just a matter preference by the RDBMS' designers. And based on what I've seen of the internals of MS SQL Server (I haven't studied Oracle's internals yet) I'm not sure you could write a RDBMS that would function well both ways.

share|improve this answer
    
Thanks for your time writing the answer (+1) . But I really want to see something a bit more specific then 'just optimized to use/not use clustered indexes'. Thank you anyway... –  a1ex07 Jul 1 '13 at 0:37
    
Yea unfortunately I'm only just getting into MS SQL Server deeply enough to be aware of the differences, and I know next to nothing about Oracle so I can only speak in generalities at this point. –  Kenneth Fisher Jul 1 '13 at 3:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.