[ZODB-Dev] BTree ranges

Tim Peters tim at zope.com
Sun Oct 5 22:21:06 EDT 2003


[John Belmonte]
> Currently, the BTree methods all use closed ranges.  For example,
> OOBTree.items(x, y) returns items in the closed range [x, y] (that is,
> between x and y inclusive).  Example:
>
>  >>> from BTrees.OOBTree import OOBTree
>  >>> a = OOBTree({1.5: 'foo', 2.0: 'bar'})
>  >>> for x in a.items(1.0, 2.0): print x
> ...
> (1.5, 'foo')
> (2.0, 'bar')
>
> Closed ranges don't work well when dealing with continuous values,
> such as floating point numbers.  Consider that you have an OOBTree
> with float keys.  Say you want to iterate over the 10's, and then the
> 20's.  With tree.items(10.0, 20.0) you'll get the first group.  You
> only wanted only the 10's, but unfortunately you'll get 20.0 too if
> it happens to exist. That isn't the only problem.  The second
> group, tree.items(20.0, 30.0), overlaps with the first.  Again, if
> 20.0 exists in the tree, it will appear in both groups.  The
> workarounds are ugly.  You can use items(x, y-epsilon), but computing
> epsilon may be difficult, and furthermore this approach isn't
> straightforward if you are dealing with keys with custom __cmp__,
> such as a tuple object.  Another way is to continue using items(x, y),
> but explicitly ignore y if it exists in the result.

I doubt anyone here uses BTrees indexed by floats.  Luckily for you <wink>,
the same problems occur, mutatis mutandis, in BTrees indexed by strings.
For example, find all the keys starting with 'b'.  Same problem, except
worse in that a suitable "epsilon" doesn't exist even in theory (there is no
"largest string" starting with 'b').

> The BTree methods should use half-open ranges.

Your point is well taken but futile as given:  it would break far too much
code to change this.

However, in ZODB4 the relevant BTree methods have grown optional exclude_min
and exclude_max Boolean arguments.  There, e.g.,

    tree.items(10.0, 20.0, exclude_max=True)

does what you want.  Since that's a new feature, it can't be added to the
3.1 or even 3.2 versions of ZODB.  It may get backported to a 3.3 version of
ZODB (if such a thing ever exists).




More information about the ZODB-Dev mailing list