Re: Index Insider

The height is NOT limited to 4. Since
an index can have an arbitrarily large
number of entries, it must be possible for the height to increase indefinitely.

However, Oracle uses a balanced b-tree
algorithm, which ensures that the index
stays very 'flat' - specifically if the distance from the root to a leaf is N for a given entry, then the variation in N across the entire index is only 1. In other words, it is not possible for one leaf to be 3 levels from the root, it is not possible for another leaf to be 15 levels from the root. Either all leafs are 2 or 3 levels away, or all leaves are 3 or 4 levels away.

The number 4 came up originally in a rule of thumb that said something like 'if your index reaches 4 levels, then it need to be rebuilt'. The basis for this 'rule' is the way in which b-tree indexes fan out.

Take a 4K block, with a 40-byte key so
that each block can hold 100 pointers.
We'll ignore some details, and assume
that the values hold for pointers to rows and for pointers to lower level index blocks.

Look what happens in 4 layers

1 root points to 100 branch blocks
100 branch blocks point to 100 * 100 = 10,000 branch blocks 10,000 branch blocks point to 100 * 10,000 = 1,000,000 leaf blocks 1,000,000 leaf blocks point to 100,000,000 rows.

If you need a 4-level index, then either

    (a) your key is fairly large (40 bytes is quite generous)     (b) your table is pretty big.

In the good old days, when databases were small, an index going to 4 levels usually meant that the index was inefficient.

--

Jonathan Lewis
Yet another Oracle-related web site:  http://www.jlcomp.demon.co.uk

Practical Oracle 8i:  Building Efficient Databases

Publishers:                 Addison Wesley Longman
Book bound date:     8th Dec 2000
See a first review at:
http://www.ixora.com.au/resources/index.htm#practical_8i

Howard J. Rogers wrote in message <3a0b3d61_at_news.iprimus.com.au>...


>Theoretically, that can't be true: block-splitting can happen for ever, and

>hence Index height growth must be allowed to continue for ever.

>

>Now, the *mechanics* of this might mean that Oracle deals with indexes in

>such a way that the 'height' can be artificially limited, but if it does so

>(and frankly, I don't know), it will be via some mechanism that introduces

>inefficiencies of its own -so the net result will be the same in any

 case...


>indexes gradually becoming less and less efficient over time.

>

>Bear in mind that at the end of the day, whatever words we use to describe

>indexes, the entire structure simply consists of Oracle blocks organised in

>extents -so 'height' and 'horizontal' don't have any actual physical

 reality


>anyway.

>

>But if there's some guru out there who'd care to explain how height can be

>artifically limited to 4, I'd love to hear how it's done.

>

>Regards

>HJR

>--

>---------------------------------------------------------------------------

>Opinions expressed are my own, and not those of Oracle Corporation

>Oracle DBA Resources:               http://www.geocities.com/howardjr2000

>---------------------------------------------------------------------------