[rabbitmq-discuss] topix

[David R. MacIver]

On Mon, Feb 22, 2010 at 01:07:59PM +0100, Martin Sustrik wrote:
> David R. MacIver wrote:
> 
> >>If that's the case, all three fundamental operations can be
> >>implemented in O(1) time where n is number of topics and/or bindings
> >
> >Well, O(log(branching rate for the tree)) (you need to do key lookups at
> >each level), but near enough.
> 
> Right. However, in ideal case you'll use hash table for the lookup
> which will get the average case down to a constant.

True, although the worst case down to O(n) [we should probably take the resulting
vim vs. emacs style trees-vs-hash-tables debate that normally follows at this
point as read]
 
> >'though I guess that sparks another question: How long are the keys people are
> >actually using with this?
> 
> My experience from stock trading sphere is that most keys are 3-5
> items long, the longest being somewhere in the range of 15-20 items.

Thanks, that's good to know. 

Paul Jones just pointed me to an interesting use case here. 

http://github.com/paulj/trapeze

The keys being used correspond to URLS + methods and seem to look something like

GET.some.domain.//.foo.bar.baz

(I'm not sure if that's exactly right, but that's the idea)

so your routing would normally look something like 

*.some.domain.//.some.prefix.#

The keys are probably no longer than what you describe, but the initial * does
mean that they need to be able gracefully transition between simple prefixes
and the more general NFA.