[ZODB-Dev] PersistentMapping good for large numbers of objects?

[Tim Peters]

[Casey Duncan]
> ...
> keys() for a btree returns a lazy iterator.

Yup.

> In theory the size of the BTree should not affect the time taken by
> keys().

Nope, but pretty close.  keys() has to find both (but only) the first and
last ("leftmost" and "rightmost") buckets to get the lazy iterator started.
Finding the first bucket is a constant-time operation (independent of BTree
size), but finding the last bucket is done by following rightmost child
pointers from the root, so takes time proportional to the *depth* of the
rightmost bucket in the tree.  This is usually no larger than 3 (but "in
theory" could be as large as the number of items in the tree, for an
extremely degenerate BTree).

> The time to iterate all the keys would of course increase with a larger
> BTree since each iteration must lookup the next key in sequence.

Perhaps surprisingly, iteration doesn't do any key lookups (no tree search,
no key comparisons).  A BTree's leaf buckets are linked directly together,
left to right, in a linear chain, independent of the tree links used for
lookups.  So iteration is very efficient (and much more efficient than doing
an equal number of key lookups).

> Tim could probably tell you what the exact algorithmic complexity of
> key lookups is <wink>.

I could, but luckily lookups aren't relevant here <wink>.

> ...
> So keeping a Length trades a bit of expense at write time
> for a big savings a read time. Often a worthy trade.

Just one more caution:  the app has to be careful to keep the Length object
up-to-date too.  I suspect it can be easy to forget to fiddle it in lockstep
along with tree mutations.