[bind10-dev] Friday mail: radix trees for in-memory lookups

[Evan Hunt]

> But then I thought... the *fastest* thing might be a radix tree, with
> each layer being a character in the label. So, something like:

I had that same notion a year or so ago when I was working on the
radix-based ACLs in BIND 9.5.  My next crazy thought was to do the
comparison backwards (i.e., scan "www.isc.org." as ".gro.csi.www"),
so that the most significant label is scanned for a match first.

I'm not sure it's necessarily all *that* much more space-inefficient
than the RB trees... haven't done the math, though.

--
Evan Hunt -- each at isc.org
Internet Systems Consortium, Inc.