[ZODB-Dev] ZODB idioms

[Casey Duncan]

An interesting thought might be to attempt to rebalance BTrees to
"ideal" at pack time. At least that would give you some chance to
rectify unfortunate insert ordering.

Another interesting thought would be a BTree visualization tool which
created a graph from an existing BTree. or at least a method that showed
some measure of balance so that we could test and see how adverse
unbalanced trees really are.

I mean, what does a BTree look like if I insert 1000 elements in order?
I think you described it, but it would be nice to see a pretty picture
too...

-Casey

On Mon, 2002-06-24 at 11:40, Jeremy Hylton wrote:
> >>>>> "CD" == Casey Duncan <casey@zope.com> writes:
> 
>   CD> Hmmm, I thought the B stood for "Balanced". Isn't that false
>   CD> advertising? ;^) Unless of course it stands for binary...
> 
> No one knows what the B stands for.  The inventors of the BTree (Bayer
> and McCreight) aren't telling.
> 
> I assume that it was just too hard / too much work to get rebalancing
> implemented. 
> 
>   CD> This could make FieldIndexes of sequencial values rather
>   CD> unfortunate....
> 
> The particular problem of sequential keys is unfortunate, but hardly
> catastrophic.  The BTree uses twice as much space as it would under
> ideal conditions.
> 
> I think the much worse problems come when there are deletions from the
> BTree, but I'll have to leave that for a BTree expert like Tim.
> 
> I think it's safe to say, though, that we have no idea what effect
> unbalanced BTrees have in real life.
> 
> Jeremy
>