Data structure for traversing hierarchical hostnames

2018-07-19 21:13:35

So, quite often I'll come across a situation where I'd like to process hostnames in a hierarchical manner.

For example, given a hostname "foo.bar.baz.example.com", I might want to compare it against a data structure that contains a higher authority like "example.com" or "baz.example.com" and see if I get a match.

Usually, the way I handle this is to simply use a hashtable, and iteratively remove subdomains until I find a match (or, never find a match, whatever the case may be.)

But, I was thinking that something like a trie/prefix-tree might be a lot better suited for this (if I were to reverse the domain labels).

Of course, the problem is that a trie usually works on individual characters - whereas in this case I'd want to make each subdomain (or "label", in DNS-speak), a single "unit".

Is there a data-structure that might be well suited for something like this?

Use a tree, where each node will be a subdomain. The top level will be the start symbol. Then it w

  • Use a tree, where each node will be a subdomain. The top level will be the start symbol. Then it would branch into k nodes, where k is the number of top level domains you have.

    For instance, if your entire database was two entities: foo.bar.example.com and boo.car.ample.net, k will be 2 (net and com). Each of net and com nodes will have one children each: ample and example. And so on.

    As an another example, let's consider you have only two entities again. But this time it's foo.bar.example.com and boo.bar.example.com. Now the tree would be something like this.

    root

    |

    com

    |

    example

    |

    bar

    / \

    foo boo

    This will be your tree. If you th

    2018-07-19 21:33:01