Balanced tree type coming in next Python?
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).
> 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
More information about the Python-list