[ZODB-Dev] Using IIBTrees

[Tim Peters]

[Amir Salihefendic]
> I am using ZODB 3.3 and I am considering using BTrees. I am particularly
> interested in the II-package.
>
> Right now I am storing my data in a python directory

Do you mean dictionary?  I'm going to assume you do.

> where I map URLs (hash-values) to boolean values (i.e. II mapping). I
> am storing about 50 items in the directory all the time, and there
> happens a lot of insertion and removal from the directory (the max
> number of items s 50).
>
> As I can read: If I want fast logarithmic insertion and search I should
> use BTree or TreeSet - - but my problem is, if I use them, then I can't
> remove an item from the tree (or can I?).

Yes, you can.  The spelling for a BTree is the same as for a Python
dictionary, and the spelling for a TreeSet is a little different:

>>> adict = {1: 1, 2: 1, 3: 1}
>>> from BTrees.IIBTree import IIBTree, IITreeSet

>>> aset = IITreeSet(adict)
>>> list(aset.keys())
[1, 2, 3]
>>> aset.remove(2) # remove from TreeSet
>>> list(aset.keys())
[1, 3]

>>> atree = IIBTree(adict)
>>> list(atree.items())
[(1, 1), (2, 1), (3, 1)]
>>> del atree[2]   # remove from BTree
>>> list(atree.items())
[(1, 1), (3, 1)]

> What about going for an IIBucket or an IISet? Their insertion and search
> is as fast as python directories,

Not so, but time it using your own data and access patterns.  The expected
lookup/insert/delete time for a Python dictionary is independent of the
number of items in the dict.  You definitely don't want to use a Bucket or
Set for any collection that may grow "large".

> but do they give a performance boost because they are optimized for
> integer-integer mappings?

"Performance" can be measured along many axes.  The BTree-based II data
structures usually have smaller memory requirements than a Python dictionary
containing the same <key, value> pairs, but lookup, insertion and deletion
are all generally slower.  There are exceptions.  If you're worried about
them, you're probably micro-optimizing in a counterproductive way.

You can read the section about BTrees in the ZODB Programming Guide for
more:

    http://www.zope.org/Wikis/ZODB/FrontPage/guide/node6.html