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

[Jim Fulton]

Kevin Dangoor wrote:
> 
> Hi,
> 
>     I just wanted to make sure of something before I make a change that will
> stick more than 1000 objects in one container... when you're looking up an
> object by ID, that's a O(log n) function, right?

It depends on the container.

Folders use Python dictionaries, which use hashing.  This is
much faster than O(log n), if the container is already 
loaded in memory.  One problem with using Python dictionaries
is that for *really* big (hundreds of thousands of objects) 
containers, you have to have have alot of information in memory
and reloading the container into memory if O(n).

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.

Jim

--
Jim Fulton           mailto:jim@digicool.com
Technical Director   (888) 344-4332              Python Powered!
Digital Creations    http://www.digicool.com     http://www.python.org

Under US Code Title 47, Sec.227(b)(1)(C), Sec.227(a)(2)(B) This email
address may not be added to any commercial mail list with out my
permission.  Violation of my privacy with advertising or SPAM will
result in a suit for a MINIMUM of $500 damages/incident, $1500 for
repeats.