search algorithm in DNS

Paul Kosinski bind at
Thu Nov 9 14:55:29 UTC 2017

Exact matching needs a search algorithm too.

If the DNS server in only authoritative for a couple of domains (and
subdomains), a simple linear search would be adequate (or even optimal,
due to its low overhead). Many DNS servers, however, are authoritative
for multiple domains, and so might need something like a binary search
or hash table.

Reverse DNS (PTR resolution) could also need a similar algorithm, as an
ISP's server could easily cover a lot of disparate domains with its
block of assigned IP addresses. (Although the IP address, being part of
a dense range, could be converted to an index number, I suppose.)

On 9 Nov 2017 02:28:48 -0000
"John Levine" <johnl at> wrote:

> In article <mailman.21.1510187088.749.bind-users at> you
> write:
> >-=-=-=-=-=-
> >
> >I am Munkhbaatar, a master course student studying on mechanism and
> >algorithm of DNS.I want to search algorithm in DNS, but i have not
> >found the documents clearly explaining this on the web.I guess it's
> >just a "list search", but I am not sure.Please tell me the details
> >of the search algorithm. 
> There is no search algorithm, only exact match.  See RFCs 1034, 1035,
> and 2181.
> R's,
> John

More information about the bind-users mailing list