Re: How are INDEXES BALANCED?

From: Steve Adams <steveadams_at_acslink.net.au>
Date: 1997/09/18
Message-ID: <34209b38.1204753792@newsserver.trl.oz.au>#1/1

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

---

On 17 Sep 97 12:50:05 GMT, "Kevin Loney" <kevin.loney_at_astramerck.com> wrote:
>Insert 52000 names into a table , 2000 for each letter of the alphabet.
>Now, insert 52000 new names, all starting with the letter J. (2000 JAs,
>2000 JBs, etc)
>Oracle SHOULD rebalance the index so that all the J entries are at the
>same level as the rest of the index entries. But that's not what happens.
>Oracle
>leaves the rest of the index alone and splits the J entry blocks, creating
>new levels
>in the index only at that part of the index.
Received on Thu Sep 18 1997 - 00:00:00 CDT