down sev0?

Tony Li tli at
Fri Oct 27 23:27:44 UTC 2006


> Nah. You assume branching factor of 2 (and not radix tree but 
> rather a 
> form of binary tree, i.e. AVL, r/b or Patricia - they have that 
> O(log2(num_entries)) behaviour, while radix trees are traversed in 
> O(key_length/branching_factor)).

I assumed a binary radix trie (not tree) because that's the normal
cannonical version used by computer science students.  Yes, as you
outlined, there are many games you can play, if you're willing to make
space/time tradeoffs.

Regardless of the details, the point remains: if your data structures
are largely constant, then you are more efficient searching a small data
set vs. searching a large one.


More information about the NANOG mailing list