[ZODB-Dev] BTree ranges

[Tim Peters]

[Tim]
>> Range searches are often used to develop query results.  In any
>> inverse index keyed on a finite discrete coded set (e.g., 1="hated
>> it" thru 10="loved it"), there's no natural value "after the largest
>> one".  If you want to find everyone who "didn't hate it", inventing
>> an artificial key of 11 just so you can get at 2 thru 10 via
>> index.values(2, 11) seems contorted to me.

[John Belmonte]
> It's not necessary for the programmer to invent a key.  The containers
> in any library that use half-open ranges will gladly provide the
> necessary end marker.  Even BTrees do this, just specify None as the
> end of the range.

Then that's a special case clogging the code:  "OK, if they want the
endpoint included, I have to pass None -- but if they don't want the
endpoint included, I must not pass None".  That's still needlessly
contorted, compared to using the obvious closed range search.

Again, I'm not claiming that closed search is always-- or even most
often --the most appropriate form of search.  But it is sometimes, and for
*some* apps most of the time.

> Note also that with closed ranges, there is no way to specify an empty
> range.

You've apparently read my comments whining about this in the C
implementation of BTree range searches <0.9 wink>.  An empty range is
specified at the Python level by passing (any) min and (any) max with min >
max, BTW.

> This increases the complexity of the program, because you
> can't just pass around start and end values.  You have to pass around
> start, end, and is_empty.  Then you must be careful not to call any
> functions that take a closed range if is_empty is true.

What functions?  .keys() etc don't care if the slice is empty; e.g.,

>>> import ZODB
>>> from BTrees.OOBTree import OOBTree
>>> t = OOBTree([(i, i) for i in range(100)])
>>> list(t.keys(30, 40))
[30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]
>>> list(t.keys(40, 30))
[]
>>>

You're stuck if the universe of possible keys consists of 0 or 1 value, but
that's not a practical concern.  In any case where at least two distinct
possible keys exist, one is smaller than the other, and then denoting an
empty slice is no trouble.