Tres Seaver wrote:
Hash: SHA1

Jim Fulton wrote:

Tres Seaver wrote:

Hash: SHA1

Fred Drake wrote:

I have a need for 64-bit BTrees (at least for IOBTree and OIBTree),
and I'm not the first.  I've created a feature development branch for
this, and checked in my initial implementation.

I've modified the existing code to use PY_LONG_LONG instead of int for
the key and/or value type; there's no longer a 32-bit version in the
modified code.  Any Python int or long that can fit in 64 bits is
accepted; ValueError is raised for values that require 65 bits (or
more).  Keys and values that can be reported as Python ints are, and
longs are only returned when the value cannot be converted to a Python

This can have a substantial effect on memory consumption, since keys
and/or values now take twice the space.  There may be performance
issues as well, but those have not been tested.

There are new unit tests, but more are likely needed.

If you're interested in getting the code from Subversion, it's
available at:


Ideally, this or some variation on this could be folded back into the
main development for ZODB.  If this is objectionable, making 64-bit
btrees available would require introducing new versions of the btrees
(possibly named LLBTree, LOBTree, and OLBTree).

I think coming up with new types is the only reasonable thing to do,
given the prevalence of persistent BTrees out in the wild.  Changing the
runtime behavior (footprint, performance) of those objects is probably
not something which most users are going to want, at least not without
carefully considering the implications.

It really depends on what the impact is.  It would be nice to get a feel
for whether this really impacts memory or performance for real
This adds 4-bytes per key or value.  That isn't much, especially in a
Zope application.  Similarly, it's hard to say what the difference in C
operations will be.  I can easily imagine it being negligible (or being
significant :).

OTOH, adding a new type could be a huge PITA. We'd like to use these
with existing
catalog and index code, all of which uses IIBTrees.  If the performance
impacts are
modest, I'd much rather declare IIBTrees to use 64-bit rather than
32-bit integers.

I suppose an alternative would be to add a mechanism to configure
IIBTrees to use
either 32-bit or 64-bit integers at run-time.

Who uses IOBTree / OIBTree / IIBTree?

  - Catalogs map RIDs to UIDs as IOBTrees (one record per
    indexed object)

  - Most indexes (those derived from Unindex) map RID to indexed value
    as an IOBTree (one record per object with a value meaningful to that
    index) and map values to RIDs as OOBTrees (where the second O is
    usually an IITreeSet).

  - ZCTextIndex uses IIBTrees to map word IDs to RIDs, in various ways,
    and make use of IOBTrees as wel..

  - Relationship "indexes" (typically not stored within catalogs)
    usually have an IIBTree which is the mapping
    of the edges as pairs of internal node IDs (one per explicit
    relationship), with OIBTrees to map the user-supplied node value
    to a node ID.

I would guess that if you could do a census of all the OIDs in all the
Datas.fs in the world, a significant majority of them would be instances
of classes declared in IOBTree / IIBTree (certainly the bulk of
*transaction* records are going to be tied up with them).

OK.  I think we are misscommunicating. Using 64 bits for IIBTrees
types would not in any way invalidate existing pickles.
64-bit IIBTrees types can be unpickled from existing data.
Of course, someone who created 64-bit BTrees type instances
that had values outside the 32-bit range would have trouble reading
these values with 32-bit IIBTrees,

The fact that IIBTrees is so widely used is exatly the reason
I want to use 64-bits for the existing types rather than having to
introduce a new type.


Jim Fulton           mailto:[EMAIL PROTECTED]       Python Powered!
CTO                  (540) 361-1714  
Zope Corporation
Zope-Dev maillist  -
**  No cross posts or HTML encoding!  **
(Related lists - )

Reply via email to