Re: How are INDEXES BALANCED?

Better get out the text books. The Balance B+ tree algorithms that databases have been using for over 10 years perform automatic balancing. When a branching index node or leaf fills up, the algorithm splits the node. This generally happens seldom enough to not result in much overhead moving stuff around.

I guess I shouldn't have sold my database design book back in college. So I could bang you nuts over the head with it.

Dennis Taylor <no_spam_dammit_at_ipipeline.net> wrote in article <01bcc2af$141de4a0$6557c2cf_at_dennislap>...
>
> Kevin Loney <kevin.loney_at_astramerck.com> wrote in article
> <01bcbf88$4315f060$aa9e02a7_at_LONEYK.astramerck.com>...
> >
> > > > I need to know if an index is not balanced, how do I get it
 balanced
 or
 is
> > > > it done automatically? For example, when I enter an order number
 to
 an
> > > > order entry system and the numbers are sequentially numbered, are
 the
> > > > records added to the b-tree in one straight line to the tree?
> > > >
> > > The short answer is that Oracle automatically balances an index (or
 so
 I've
> > > been told). The logic for doing so is straightforward enough that, if
 they
> > > didn't, you'd have to go over and slap Larry Ellison upside the head.
> > >
> >
> > Then get slapping. Oracle does not automatically rebalance its
 indexes.
> > If it
> > did, then the performance of your inserts would be unpredictable. The
 only
> > way to rebalance an index is to drop and recreate it, or use the alter
> > index
> > rebuild option in 7.3.
> >
> > Kevin Loney.
>
> Hm. I was told that it did by one of the Oracle instructors - Al
 Williamson
> (Oracle Canada) - who has a pretty impressive history, with Oracle and
> otherwise. And your source is ?
>
> Anyway, who says the performance of inserts *is* predictable? By
 definition
> any multiuser software cannot perform deterministically anyway, so why
> would they leave off automatic balancing for that? And rebalancing
 involves
> perhaps a half-dozen writes extra on every x/2 record additions (on a
 *big*
> file), where x is the number of branches in an index record (This formula
> is not authoritative - more off the cuff based on my own personal
> experience - so don't drag out the textbooks).
>
> --
> ---
> email address is dtaylor at ipipeline dot net
> ---
> Spammers: Here's some free addresses for you:
> rhundt_at_fcc.gov
> jquello_at_fcc.gov
> sness_at_fcc.gov
> rchong_at_fcc.gov
>
>
>
Received on Wed Sep 17 1997 - 00:00:00 CDT