BIND - sorting of reverse domain.

[Mark_Andrews at isc.org]

> 
> On 3 Jul 2002, Kevin Darcy wrote:
> >"D. Stussy" wrote:
> >> Older versions of BIND did not.  However, BIND-9 does - but someone else
> >> indicated that this is a side effect of its memory image of the data and n
> ot
> >> intentionally done.  If truly not intentional, that could moot my question
> .
> >>
> >> I do note that someone also indicated that BIND arranges the data in
> >> alphabetical/machine order so as to abort early with an NXDOMAIN error if 
> it
> >> passes the point where the target query name would be.  Such a search is
> >> potentially an O(n/2) on the average - while a balanced binary tree search
>  would
> >> be O(log2(n)) (and the worst case unbalanced tree - O(n/2)).  Except for n
> =1 or
> >> n=2, log2(n) < (n/2) for postive integers, so why choose a non-optimal sea
> rch?
> >> [This goes beyond my original question/comment, so responses aren't necess
> ary.]
> >
> >BIND stores zone data in memory in a hashed structure which has little or no
>  relationship to the format in which it writes out
> >zonefiles.
> 
> If true, then it must actively sort the zone file in order for it to be writt
> en
> out in alphabetical order (which is occuring with this version).  It is
> obviously bothering to take the time to do this, so while we're at it, why no
> t
> write out the reverse domain files in numerical order where possible?  [We're
> back to my original question!]
> 
	BIND 8 uses a hash.

	BIND 9 sorts in DNSSEC order because it *needs* the zone to be
	sorted this way to able to find the correct NXT record to be 
	returned with a NXDOMAIN response.

	Both BIND 8 and BIND 9 dump zones in internal order though they
	do put the SOA and NS RRsets for the zone first.
--
Mark Andrews, Internet Software Consortium
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: Mark.Andrews at isc.org