[ZODB-Dev] How are modified *TreeSets stored?

[Tim Peters]

[Christian Robottom Reis]
> I've been debugging some conflict errors in our desktop application
> (which now has users to generate them, finally) and I ran into
> something that [initially] surprised me: I never create IISets in my
> code, and yet I'm finding IISets in the storage.
>
> Since I *do* create IITreeSets, and taking the hint from
> http://zope.org/Members/ajung/BTrees/DataTypes [*] that TreeSets are
> not persisted all at once, my current hypothesis is that, in the same
> fashion as BTrees, which are persisted in Bucket-typed chunks when
> changed, the TreeSet objects are persisted in Set-typed chunks.  Am I
> right?

Yes, and you could also take this hint <wink> from the ZODB/ZEO Programming
Guide:

    http://zope.org/Wikis/ZODB/FrontPage/guide/index.html

    The Bucket and Set types are the individual building blocks
    for BTrees and TreeSets, respectively.

> [*] The thing that bothers me is that Andreas' text says that
> TreeSets are persisted in Buckets, but that can't be true, since
> Buckets are essentially mappings, since they contain key, value
> pairs, right?

Correct.  Andreas may have peeked at the code, though, and under the covers
Buckets and Sets are the same type, called "Bucket" in the code:

/* A Bucket wraps contiguous vectors of keys and values.  Keys are unique,
 * and stored in sorted order.  The 'values' pointer may be NULL if the
 * Bucket is used to implement a set.  Buckets serving as leafs of BTrees
 * are chained together via 'next', so that the entire BTree contents
 * can be traversed in sorted order quickly and easily.
 */
typedef struct Bucket_s {
  sizedcontainer_HEAD
  struct Bucket_s *next;    /* the bucket with the next-larger keys */
  KEY_TYPE *keys;           /* 'len' keys, in increasing order */
  VALUE_TYPE *values;       /* 'len' corresponding values; NULL if a set */
} Bucket;