Re: Index Insider

Jonathan Lewis wrote:
>
> 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
> >---------------------------------------------------------------------------

I wonder what level you could actually achieve - take the smallest blocksize, largest index keys and keep on pumping rows in until you hit the table size limit then check the level...

Anyone care to do the maths ??

-- 
===========================================
Connor McDonald
http://www.oracledba.co.uk (mirrored at
http://www.oradba.freeserve.co.uk)

"Early to bed and early to rise, 
 makes a man healthy, wealthy and wise." - some dead guy