[ZODB-Dev] BTrees questions

[Jim Fulton]

Toby Dickenson wrote:
> 
> Ive had a long-standing worry about the current BTree
> implemententation. I would be much happier if anyone could point out
> why I shouldnt be worried.....
> 
> The current object-keyed trees sort their keys using PyObject_Compare,
> however the python language reference defines that the relative sort
> order of different types (say int and string) may change across
> different runs of the same program. Does this mean that persistent
> BTrees with type keys are relying on undefined behaviour?
> 
> I think python 2.2 is the first time this sort order has actually
> changed, so this is no longer an ignoreable theoretical problem.

BTree data structures certainly rely on sorting, which implies that
keys must be orderable in a consistent fashion.  This is inherent
in the underlying algorithm.  Given that the algorithm is based on
ordering, using unordered keys is certainly something to worry about.
Using integer and string keys is certainly worth worrying about.
The problem here, however, is in the use of BTrees, not in BTrees 
themselves. 

I can't imagine what BTrees would use to compare objects if not 
PyObject_Compare. :)

Perhaps Python should not be so ready to order things in meaningless
ways. 

Jim

--
Jim Fulton           mailto:jim@zope.com       Python Powered!        
CTO                  (888) 344-4332            http://www.python.org  
Zope Corporation     http://www.zope.com       http://www.zope.org