[prev in list] [next in list] [prev in thread] [next in thread] 

List:       namedroppers
Subject:    Re: draft-ietf-dnsext-nsec3-01
From:       Ben Laurie <ben () algroup ! co ! uk>
Date:       2005-03-30 9:35:06
Message-ID: 424A72CA.2030106 () algroup ! co ! uk
[Download RAW message or body]

Samuel Weiler wrote:
> On Wed, 30 Mar 2005, Ben Laurie wrote:
> 
> 
>>>In the Performance Considerations, you could mention that the hashed
>>>labels decrease performance of some access methods (e.g. B-trees) due
>>>to poor locality.
>>
>>? I don't understand this comment - B-trees shouldn't be affected by the
>>distribution of the data (not entirely sure what you mean by "locality"
>>in this context, though).
> 
> 
> Presumably: when answering a query for a non-existing name, an
> authoritative server must first look for the exact match, then for the
> span containing the hash of the QNAME.  With NSEC-classic, the QNAME
> and the NSEC covering it can be found remarkably close to one another
> in the sorted zone.  When using a B-tree keyed on the name, presumably
> the search for the closest predecessor is shorter than starting over
> at the root at the tree.
> 
> With NSEC3, the QNAME and the NSEC3 covering hash(QNAME) are generally
> not adjacent in the sorted zone, so a server storing the zone as a
> B-tree would need to do two full searches.

Obviously if one is going to search by the hash, then one would 
construct an index using the hash, which would be around as efficient as 
an index of names (at least, it would be using B-trees).

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

--
to unsubscribe send a message to namedroppers-request@ops.ietf.org with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>
[prev in list] [next in list] [prev in thread] [next in thread]