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

[Shane Kerr]

All,

Since it's Friday I thought I'd throw a random crazy idea out.

I was thinking how to get the fastest database lookup when we get a
query. Right now BIND 9 uses a red-black tree, which is more-or-less as
fast as a binary tree that stays sort-of balanced when you update it. It
might be faster to use a simple hash table, at least in some cases.

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

struct node {
    void *dns_information;
    struct node *children[256];
};

struct node root;

So a lookup would be simply following the tree down and seeing what we
get:

void *
radix_lookup (const char *name)
{
    struct node *p;

    p = &root;
    while (*name != '\0') {
        p = p->children[(unsigned)*name];
        if (p == NULL) {
            return NULL;
        }
        name++;
    }
    return p->dns_information;
}

This is of course obscenely inefficient in terms of space (which might
harm us a bit due to blowing out the data cache), even if various tweaks
were done to improve the situation. But the lookup time is basically the
time it takes to scan the label.

Anyway, that was my wacky Friday idea. :)

--
Shane