Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms)

[skaller <skaller@users.sourceforge.net>]

On Thu, 2005-11-17 at 12:08 -0600, Brian Hurt wrote:

> > I'm not sure what it is we disagree on.
> 
> They don't ever need global rebalancing.

Yup, they do not need it to maintain the invariant
you stated. But performance can still benefit from it
significantly.

Two quite distinct BTrees can contain the same data exactly,
it depends on the order of insertion of keys. If you are
clever, you can fill up a BTree so every block is exactly
full .. however you don't need to be clever to get the worst
possible BTree -- just fill an empty tree with sorted
data and almost all the blocks are guaranteed to be half
full (the worst possible case for storage use and
access time). Yet, this is a common case in practice.
** all the blocks will be half full except those on
the right edge of the tree -- for a tree of depth 5
that's millions of half full blocks, and only 5 that 
can possibly be more than half full :)

And in between, blocks can be filled to different extents.
Rebalancing adjusts this. 

The basic algorithm you describe has MANY tweaks which
attempt to rebalance the tree.

The version I played with did 'scrolling', where
instead of splitting an overfull block, you scroll
a key (and child) across to one of its siblings 
via the parent. This is quite tricky ..  but it
fixes the sorted insertion problem nicely --
with this modification, all the blocks are
always FULL .. except those on the right most
edge and their left siblings: they grow until
they're both full, then the rightmost one (only)
is split. So at worst, you waste 5 blocks
out of millions.. basically this doubles the 
capacity of the tree (built from a sorted list).

The same tweak can be used on random insertions
the same way, however the extra reads and write
may or may not be worth it, depending on how
valuable your disk storage is (etc).

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net