Balanced tree type coming in next Python?

Tim Peters tim.one at comcast.net
Tue Jun 8 20:11:33 CEST 2004


[Christos TZOTZIOY Georgiou]
>> PS Any volunteers to port and maintain Judy arrays/trees for Python?-)
>> http://judy.sourceforge.net/ They'd be an interesting alternative to
>> dictionaries in some cases (esp very large dictionaries).

[Thomas Guettler]
> How do they compare to BTrees (ZODB)?

Judy arrays are in-memory data structures, and were designed to be
cache-friendly.  ZODB BTrees were designed to support persistent storage in
a database, and to be pickle-friendly <wink>.

Because Judy uses a trie structure, depending on the data it can get large
memory savings from sharing common key prefixes.

Judy arrays can only be indexed by native-size integers or by byte strings.
ZODB BTrees can be indexed by any Python object (whether builtin or
user-defined) that defines a consistent total ordering.

Both have worst-case O(log N) time for lookup, insertion, and deletion.
Because of low-level tricks to reduce conflicts when multiple transactions
modify a BTree simultaneously, finding the size of a ZODB BTree is actually
a much more expensive operation (O(N) time, and has to touch every bucket in
the BTree!).






More information about the Python-list mailing list