Re: unbalanced indexes -- common wisdom?

Richard,

Sorry about the delay in replying to this; I've been at the Miracle Database Forum in Australia for the last few days, and been too busy to check the newsgroup.

The answer is easy - I was wrong. I've been carrying around an image of how leaf blocks split for years without thinking it through carefully enough. Coincidentally one of Steve Adams' presentations included a discussion of space re-use in indexes, and his description made me see the light.

All leaf blocks in a balanced b-tree are at the same level, and one when block changes its level, they all change. The specific scenario I was thinking of was for a completely full index structure.

If you insert a single row into a full leaf in this case, it splits, but you cannot 'insert a pointer' into the parent for the new leaf as the parent is full.

The image I had in mind was that the leaf therefore split into two leafs, but its place in the structure was taken by a new branch block that pointed to the two leaf blocks. Hence you got two leafs that were one level deeper than the rest of the leafs. This is complete rubbish. (Though notionally a not unreasonable algorithm - although it could easily lead to very badly balanced trees).

What actually happens is that the leaf split, therefore we need to insert a new pointer in the parent - but the parent is full, so it splits - which means we need to insert a new pointer into ITS parent, and so on up the tree, until the root splits (in fact in Oracle the root "split" has a slightly special implementation) - at which point EVERY leaf block is suddenly one level deeper in the tree, and the tree is still balanced.

--
Jonathan Lewis
http://www.jlcomp.demon.co.uk

Author of:
Practical Oracle 8i: Building Efficient Databases

Next Seminar - Australia - July/August
http://www.jlcomp.demon.co.uk/seminar.html

Host to The Co-Operative Oracle Users' FAQ
http://www.jlcomp.demon.co.uk/faq/ind_faq.html



Richard Foote wrote in message ...


>

>One thing you mention that has me curious is how the splitting of one 3rd

>level node block produces an imbalance. It results in an additional 3rd

node


>being introduced containing half the contents of the split node and it's

>parent node on the 2nd level being updated with appropriate pointers to the

>2 affected child nodes. But everything is still "balanced".

>