[ZODB-Dev] [BTrees] considerable optimization potential in"intersection"

[Dieter Maurer]

Tim Peters wrote at 2004-8-4 23:17 -0400:
> ...
>> Would you mind when I tried to optimize "intersection"?
>
>I think it would be great if you wrote it in Python.

I do not think that this is a good idea:

  To optimize intersection for a minimal number of loads,
  the tree structure is very essential (to be able to
  skip whole subhierarchies).

  But, this structure is not exposed at the Python level...

I know that you crack this structure for the tree display and
checking code. It appears that you use pickling/unpickling
there. But, intersection should work efficiently for
both in-memory and out-of-memory structures.
It should not be necessary to pickle the tree in order to get
its structure.

I may be wrong, but I have the feeling that the "C" level
is the right place to attack.

Note also, that intersection is non-destructive.
Reading the input trees requires that the nodes are
loaded from ZODB before access and that they
stay there while we access them. I know, there are
macros for this effect. Otherwise, the structure is
straight forward: intersection needs not to worry
about "first leaf pointers" and "leaf chain" and other
subleties that make plague other algorithms.

-- 
Dieter