[Zope-dev] Is object lookup in a container O(log n)?

[Toby Dickenson]

On Tue, 8 Feb 2000 10:49:42 -0500, "Kevin Dangoor"
<kid@kendermedia.com> wrote:

>I assume an ObjectManager ZClass will be the same, performance-wise, as a
>Folder. Do you have any idea where the threshold is as far as the hash table
>is concerned?

Dictionaries increase the size of their table to prevent it getting
too full. Performance degenerates quite smoothly.

>For my own application, I'd be looking at 1000-2000 objects
>right now. For others (since this is code I'm thinking of releasing), they
>could be looking at much more.

Hashing will not be a problem here. However something else might
be.... When the container is activated, the object database will have
to load all 2000 objects.

>I can consider doing something like breaking off the first two characters of
>the identifiers and creating containers with those characters as an id and
>splitting the objects up in those folders.

This lets ZODB load the objects more gradually. If a different
grouping scheme would improve locality, then that would be better
still.

>> We plan, in the future, to provide folder-like objects
>> suited to very large collections. These will be based on
>> BTrees and will be O(log n) for lookup.  Catalog uses BTrees
>> and is O(log n) for searches.
>
>Sounds good...

MMmmmmm.



Toby Dickenson
tdickenson@geminidataloggers.com