search algorithm in DNS

Paul Kosinski bind at iment.com
Sun Nov 12 14:53:39 UTC 2017


I don't call *everything* a search, but I would claim that any
practical mapping of a relatively sparse set of keys into values in
another set would require a search at some point. Only direct indexing
of sub-sequences of characters in domain names into sub-trees whose
eventual leaves were IP addresses would not involve at least simple
searches (such as in B-trees). And such trees with fully branching --
index-only, no search required -- nodes would tend asymptotically to
take exponential storage space.

(This behavior might be somewhat mitigated by the fact that domain
names are not random strings of characters, but rather follow certain
linguistic statistics.)


On Thu, 9 Nov 2017 17:56:03 +0100
Reindl Harald <h.reindl at thelounge.net> wrote:

> 
> 
> Am 09.11.2017 um 15:55 schrieb Paul Kosinski:
> > Exact matching needs a search algorithm too
> 
> no it don't - unless you call everything "search"
> https://en.wikipedia.org/wiki/Hash_table
> 
> > On 9 Nov 2017 02:28:48 -0000
> > "John Levine" <johnl at iecc.com> wrote:
> > 
> >> In article <mailman.21.1510187088.749.bind-users at lists.isc.org> 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



More information about the bind-users mailing list