Re: Maximum height of an Oracle B-tree index
- From: Tim Gorman <tim@xxxxxxxxxxxxx>
- To: <oracle-l@xxxxxxxxxxxxx>
- Date: Tue, 09 Mar 2004 18:19:59 -0700
Comments inline...
on 3/9/04 6:20 AM, ryan.gaffuri@xxxxxxx at ryan.gaffuri@xxxxxxx wrote:
> what type of algorithm do you run to increase the height of a b-tree index? My
> understanding is that oracle dynamically increases the number of pointers each
> block can have(which is different than other b-trees) in order to keep the
> height low? am I correct in this assumption?
>
> Why isn't it good to rebuild an index when the height increases? The formula
> for calculating I/O of an index is as follows
>
> LOG_height(blocks) = estimated I/O
[TG]: This isn't the only algorithm for calculation logical I/O on an index.
There are at least four different operations available for use on B-Tree
indexes:
* Unique probe
* Range scan
* Full scan
* Fast full scan
The algorithm mentioned is just for a "unique scan".
Arguably, the "range scan" is the most often-used algorithm on indexes, and
the algorithm for calculating logical reads would have to take into account
the scan across leaf and data blocks. When you think about it, the "height"
portion of this algorithm can get insignificant rather quickly as the number
of entries/rows scanned increases...
I honestly don't see "full scan" (i.e. scan from leaf-to-leaf from lowest to
highest) in use very often any more, but "fast full scan" is used in many
situations, and that operation closely resembles a FULL table scan except
the target is an index. A "fast full scan" will try to sweep up the entire
index using sequential, multi-block I/O, then get rid of the branches and
just keep the leaves. Kind of like cleaning pot back in high-school (20+
years ago for me)...
Anyway, for all access algorithms except "unique probe", the height of the
index doesn't matter all that much. For the latter two algorithms, it is
not a factor at all as the branches and root are completely ignored...
>
> That is LOG of the height of an index to the base of its total number of
> blocks. Now I think there is a fudge factor based on the size of your blocks,
> because larger blocks incur more LIOs.
>
> This is not oracle specific. Its general tree theory.
[TG]: Correct. Oracle did not invent this stuff...
>>
>> From: "Richard Foote" <richard.foote@xxxxxxxxxxx>
>> Date: 2004/03/09 Tue AM 09:18:59 EST
>> To: <oracle-l@xxxxxxxxxxxxx>
>> Subject: Maximum height of an Oracle B-tree index
>>
>> Hi All,
>>
>> I'm currently writing a rather detailed paper for our local user group on
>> Index Internals, tentatively titled "Index Internals - Rebuilding The
>> Truth". I haven't had this much fun with tree and block dumps for quite a
>> while ;)
>>
>> One of the many myths I'm exposing is the "rebuild if index has more than 2,
>> 3, 4, 42, whatever levels". Now to get an honary mention in the paper (what
>> more reward can one wish for !!), I would love to know who on the list has
>> created an index with the greatest height and perhaps a little info on it's
>> circumstance.
>>
>> Steve Adams once mentioned to me creating an index with 20+ levels, can
>> anyone else come close ?
>>
>> Thanks for any replies.
>>
>> Richard
>>
>>
>> ----------------------------------------------------------------
>> 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
>> -----------------------------------------------------------------
>>
>
> ----------------------------------------------------------------
> 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
> -----------------------------------------------------------------
----------------------------------------------------------------
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:
