[ZODB-Dev] Curiosity concerning dead BTree slicing bug

[Tim Peters]

[Roch=E9 Compaan]
> We just stepped in a Zope 2.5.1 BTree bug that looks like it's been
> fixed in Zope 2.6.1. The issue was this: a range query on a FieldIndex
> containing strings that look like: '20020120000000'. (They're a compact=
,
> sortable, date representation.) Some ranges worked, and some didn't. We
> were curious why this happened in the 2.5.1 version of the OOBTree code.
> ...

BTrees are complicated data structures, and several obscure endcase bugs
*could* have accounted for the failure you showed.  It's impossible to sa=
y
which was at work without knowing the internal structure of the BTree you
were using at the time it failed.

In current versions of ZODB, BTrees.check.display(a_btree) shows the
internal structure, so run that if your curiosity is stronger than idle.

Two distinct kinds of BTree corruption can be identified in current versi=
ons
of ZODB, via BTrees.check.check(a_btree), and via a_btree._check().  Eith=
er
kind of damage could account for the failure you saw.  There was also a
distinct endcase bug in the way range searches were set up that could hav=
e
caused the failure you saw, although offhand that one looked unlikely to =
me
in your specific example (it was most likely at work if the range search
yielded *more* elements than it should have -- your range search example
yielded fewer).

The short course is that several obscure endcase bugs have been fixed, an=
d
they don't make sense except from a detailed internal view of how BTrees =
are
implemented.  You may find the comments in the DegenerateBTree class (new=
 in
current versions of ZODB) of the BTree test suite to be interesting readi=
ng.