[Zope-dev] objectValues performance

Casey Duncan cduncan@kaivo.com
Tue, 28 Nov 2000 13:38:22 -0700


Brett Carter wrote:

> Ok, I'll bite.  Why doesn't the standard folder scale?  Seems like a
> design flaw to me - why doesn't the default folder use catalogs or BTrees?
> -Brett

AFAIK a standard folder uses a linear search when you request an object from it
(ala Python dictionaries, someone please correct me if I'm wrong). This works
great except that the search time grows linearly (by n) as you add objects. The
BTreeFolder as the name implies creates a binary tree of the objects where the
search time grows by only log n. For small folders the search time difference
is minimal to non-existant, but as n increases the BTreeFolder search time
increases minimally. B-trees are fairly complex entities to manage and for the
vast majority of folders are total overkill. That is why standard folders work
the way they do, the implementation is simple and efficient for 99.9% of
applications. Your case is fairly atypical of most Zope folders.

Perhaps a future implementation of Zope folders could automatically use a
b-tree after a certain threshold is reached, for now you must explicitly select
them.

Andy's idea of using objectIds instead of objectValues is also a good one which
will save significant amounts of memory. You can always access each object
individually via id if you need to. Using a  ZCatalog could also help in this
because you can query the objects without loading them into memory and the
returned result does not load the objects themselves, only the meta-data and
only once a result item is explicitly accessed (By using so-called lazy
sequences). However the catalog will not speed up your actual object access
time unless you divide them up amongst several folders or use a BTreeFolder.
The latter being a simpler solution from a design standpoint.

Good luck!

Casey Duncan