Re: Index Insider

Hi, Jonathan (and Howard),

Quote from James Morle "Scaling oracle8i, Building Highly Scalable OLTP System Architectures" p.236:

Oracle maintains very shallow B-trees. This means that the number of root/branch blocks read before the actual leaf block is hit is very low- -typically two (one root, one branch), with the maximum of four levels.

End quote

James seems to say that the number of levels *is* limited to 4 as if it's hardcoded in Oracle software, not because of common DBA practice or difficulty to do an experiment to achieve more than 4 levels. However, his book is not Oracle documentation. So we can take that with a grain of salt.

A B-tree data structure does not itself limit the level to 4. I believe it's just that the Oracle implementation does so. Howard is right that theoretically it should not be limited to any number. It can be artificially limited only if the software artificially limits the total number of keys stored in the index, which is very large for even a 4k block size as Jonathan shows.

Yong Huang
yong321_at_yahoo.com

In article <973847701.27999.0.nnrp-02.9e984b29_at_news.demon.co.uk>,   "Jonathan Lewis" <jonathan_at_jlcomp.demon.co.uk> 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.

[snipped]

Sent via Deja.com http://www.deja.com/
Before you buy. Received on Sat Nov 11 2000 - 22:49:12 CST