Re: How are INDEXES BALANCED?

Steve Adams <steveadams_at_acslink.net.au> wrote in article <34209b38.1204753792_at_newsserver.trl.oz.au>...
>
> Hello Kevin, Tom and others,
>
> Sometime ago I began to suspect that what Kevin has written might
 in
> fact have been the case. So I set up an experiment (using 7.0.16)
 to
> check it out in detail, taking block dumps of the entire index
 before
> and after each operation. What I found to be happening was that if
> (using Kevin's illustration) the J branch block was full and needed
 to
> split, then a new block would be inserted next to the existing
 block,
> ON THE SAME LEVEL of the B*-tree, and the keys divided between the
 two
> blocks. The split requires that a new compressed key and block
 pointer
> be inserted into the parent block, which might in turn cause that
> block to split too, and so on, all the way up to the root if
> necessary. The effect of this algorithm (block splits propagating
> upwards) is that the B*-tree remains height balanced at all times,
 and
> rebalancing is never needed. Of course, some branches of the tree
 may
> become sparse, as others have already noted, but that is another
> matter. The tree remains balanced and Kevin's theory is not in fact
> what Oracle is doing internally.
>
> Steve Adams

And whilst we're on the topic of proper testing -

The last time I used a block-dumping check to see what happened with indexes based on sequences (some time around 7.1.3 I think), I found that the 'right hand' leaf does not split when it is full and the new value
exceeds the current upper limit: instead a new leaf is added at the same
level and the leaf layer stays 100% packed.

The old chestnut about sequence-based indexes leaving trails of half-filled blocks is not true. (Was it ever ? Did anyone every prove
it or was it just part of the oral history that was never tested ?) Received on Thu Sep 18 1997 - 00:00:00 CDT