Re: RE: How does Oracle keep B-tree indexes to 3 levels?
- From: "Jonathan Lewis" <jonathan@xxxxxxxxxxxxxxxxxx>
- To: <oracle-l@xxxxxxxxxxxxx>
- Date: Fri, 6 Feb 2004 14:13:12 -0000
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@xxxxxxx>
To: <oracle-l@xxxxxxxxxxxxx>
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@xxxxxxxxxxxxx
put 'unsubscribe' in the subject line.
--
Archives are at //www.freelists.org/archives/oracle-l/
FAQ is at //www.freelists.org/help/fom-serve/cache/1.html
-----------------------------------------------------------------
Other related posts:
