Re: RE: How does Oracle keep B-tree indexes to 3 levels?

From: Jonathan Lewis <jonathan_at_jlcomp.demon.co.uk>
Date: Fri, 6 Feb 2004 14:13:12 -0000
Message-ID: <01b601c3ecbb$5bca4d10$6702a8c0@Primary>

Bearing in mind that we are only considering the B-tree option:

Oracle uses dense indexes - generally, every row in the table has its own entry in the index.

The only exceptions are the rows which have null values for every column in the index definition. In this special case, Oracle doesn't create an index entry.

Emptiness (one or two pointers in a node) can be an issue at the leaf level - which is why Oracle introduced the COALESCE command, which merges adjacent leaf blocks in a series of small transactions. In the general case (randomly arriving data) indexes don't get sparse, but tend to hover around the 69% mark **.

Oracle also uses a compression mechanism in branch blocks (nodes) which can result in very dense packing - so even branches 'go bad' they can't go very bad, so Oracle indexes tend to stay at a very small number of steps from root to leaf.

Footnote - I used to believe it was supposed to be at 75% because on average a block was somewhere between half full and full - but I've given a reference to a paper that demonstrates that the failure to merge in real time leaves Oracle with a lower value. I haven't yet found time to read the paper, though.

Regards

Jonathan Lewis
http://www.jlcomp.demon.co.uk

  The educated person is not the person
  who can answer the questions, but the
  person who can question the answers -- T. Schick Jr

Next public appearances:
March 2004 Hotsos Symposium - The Burden of Proof March 2004 Charlotte NC OUG - CBO Tutorial April 2004 Iceland

One-day tutorials:
http://www.jlcomp.demon.co.uk/tutorial.html

Three-day seminar:
see http://www.jlcomp.demon.co.uk/seminar.html ____UK___February
____UK___June

The Co-operative Oracle Users' FAQ
http://www.jlcomp.demon.co.uk/faq/ind_faq.html

Original Message ----- From: <ryan.gaffuri_at_cox.net> To: <oracle-l_at_freelists.org> Sent: Friday, February 06, 2004 1:58 PM Subject: Re: RE: How does Oracle keep B-tree indexes to 3 levels?

so nodes can be as sparse as having 1-2 pointers in them? Doesnt this increase the size of the tree and decrease performance?

also, does oracle use 'sparse' indexes. With standard dense indexes there is a pointer to every record in the table. With sparse indexes you get pointers to a range of records.

For example.

You have a column with

1
2
3
4
5

You might have a pointer to '1' and a pointer to '5'. Does oracle use this?
>

Please see the official ORACLE-L FAQ: http://www.orafaq.com

To unsubscribe send email to: oracle-l-request_at_freelists.org put 'unsubscribe' in the subject line.

--
Archives are at http://www.freelists.org/archives/oracle-l/
FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
-----------------------------------------------------------------

Received on Fri Feb 06 2004 - 08:13:12 CST