[ZODB-Dev] ZODB idioms

[Tim Peters]

[Jeremy Hylton]
> The particular problem of sequential keys is unfortunate, but hardly
> catastrophic.  The BTree uses twice as much space as it would under
> ideal conditions.

[Toby Dickenson]
> Twice as much disk space, yes.

I don't believe that, but covered the subject in a different email.  They'll
use twice as many bucket *nodes* on disk, but the raw node size is small
compared to the size consumed by keys+value, and the latter space is the
same regardless of how many bucket nodes the keys+values are spread over
(whether they're all in the same bucket, or all in their own bucket).

> Disk space isnt the problem.

Good <wink>.

> An unbalanced tree will use *linear* memory and
> number-of-comparisons for a lookup.  That defeats the main selling
> point of a BTree.

Sometime last week I changed _BTree_get() from a recursive routine to an
iterative one.  That means the memory for a lookup remains constant now no
matter how unbalanced a tree may get.  I have no reason to believe that
Zope's B-Trees do get noticeably unbalanced in real life; they *cannot*
become unbalanced by insertions alone.