Dan et al,
> I'm wondering if you have looked at Pierre Nicodeme's CBT's (compact
> balanced trees) to see how they compare with Judy.
Never heard of them, but no surprise. Given the word "balanced", I can
almost guarantee it's a waste of time, it indicates yet-another
by-population attempt to tune a tree that tries to keep the fanout
constant at every node. One thing I am certain of now is that the
entire approach of by-population trees is an evolutionary dead end.
Only a radix tree is infinitely extensible. It's nature's way.
I know, I don't have the academic credentials to make a claim like that,
but this also gives me the freedom to spout off without worrying about
ruining an academic reputation. :-)
Really, though, consider... The homogeneous state of the early universe
rapidly clumped at all levels. Nature does not "balance its trees".
The key to an effective radix approach is to efficiently (in both time
and space, for both modify and lookup) allow any node to have 0,1,2...
nearly-infinite elements below it. Forget about balancing anything.
Some people who understand how Judy works have complained that it's just
a bunch of tricks "flying in close formation". Ah, but the science is
in the radix approach, and the art is in choosing the right tricks.
In general two key types of tricks are:
1. Skipping unpopulated levels (keep the tree shallow, and cache fills
few), even in, say, a 2^64 tree.
2. "Compressing" nodes intelligently to minimize space and time
required to traverse them, and also to insert/delete elements.
> Relevant papers attached.
Saving to look, eventually.
Thanks,
Alan
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys - and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
