[ZODB-Dev] OOBTree problem

[Paul Roe]

I'm having a bit of fun with ZCatalog (Range searches on FieldIndices)
the problem seems to be with OOBTree. Here's a simplistic code snippet
that reproduces the problem.
Basically the BTree does not always find values in a range when the
data is not sequential.


# $Id: OOBtreeTest.py,v 1.3 2001/09/07 01:48:17 PaulRoe Exp $

from BTrees.OOBTree import OOBTree

def testItems(code,treedata):
    # Use the first few characters as a basis for the search
    # try a few different ranges to prove the point
    for length in range(3):
        lo = code[0:length]
        hi = lo + '9999999'
        # we only care if we dont find anything as we should
        # because we know we but it in there
        if not len(treedata.items(lo, hi)):
            print "could not find anything in range %s - %s length %d" % (lo, hi, length)
            if len(treedata.items(code, code + '9999999')):
                print ">>>We should have at least found ....", code

print "Sparse Data"  
treedata = OOBTree()
# Generate some str data with gaps and store in a OOBTree
for id in range(0,200,3):
    code = str(id)
    treedata[code] = code

print "Numrecs", len(treedata)        
# See if we can find it all again with an Item range search
for code in treedata.keys():   
    testItems(code, treedata)
    
print "Sequential Data"
treedata = OOBTree()
# Generate some sequential str data and store in a OOBTree
for id in range(0,1000):
    code = str(id)
    treedata[code] = code

print "Numrecs", len(treedata)        
# See if we can find it all again with an Item range search
for code in treedata.keys():   
    testItems(code, treedata)
    

Output from a Run... (Python 2.1)

Sparse Data
Numrecs 67
could not find anything in range 14 - 149999999 length 2
>>>We should have at least found .... 141
could not find anything in range 14 - 149999999 length 2
>>>We should have at least found .... 144
could not find anything in range 14 - 149999999 length 2
>>>We should have at least found .... 147
could not find anything in range 5 - 59999999 length 1
>>>We should have at least found .... 51
could not find anything in range 5 - 59999999 length 1
>>>We should have at least found .... 54
could not find anything in range 5 - 59999999 length 1
>>>We should have at least found .... 57
Sequential Data
Numrecs 1000


-- 
Paul Roe

Artifact Imaging Systems        Voice:  +64 3 3266213
Sumner, New Zealand             Mobile: +64 21 676301
paul@artifact-imaging.co.nz     Fax:    +64 3 3267936