Creating an index of wildcard DNS names
as dns domains are parsed from the end, it's useful to also store them that way - e.g:
For bar.foo.co.uk you'll keep uk.co.foo.Bar. 

It makes both indexing and prefix searches simple and fast. 
In the example above you'll search for uk.co.foo.% - a simple search for regular index. 

Note: it's the same way many directory (ldap,dns, etc. ) searches work.