[bind10-dev] new in-memory zone data design

[Michal 'vorner' Vaner]

Hello

On Wed, Jun 20, 2012 at 09:41:29AM +0000, Francis Dupont wrote:
> > I've had a look and I have few questions:
> >  * It seems to be taken as a fact that it'll be a red-black tree. Is
> >    there a reason for that? Are we able to reuse our implementation?
> >    If not, we might want to consider different kinds of trees (2-3
> >    tree, 2-4 tree or AVL), since they can have benefits we might
> >    like.
> 
> => according to experts (i.e., guys D. Knuth nods to when he sees them)
> the red-black tree is the best (known) data structure for this kind of
> things, in particular its dynamic performance is pretty good. So I
> support Junmei in his choice!

Well, that's the point. Dynamic performance means it is fast with updates.
However, we have much more lookups than updates. AVL trees are somewhat slower,
but they are better balanced, so they trade the update speed to get better
lookup speed. So I think AVL tree might be better for that reason.

What I fear is, somebody decided to use RB tree because it is generally the good
choice (without really thinking about specific needs) and then everybody uses
them because everybody uses them. We never had a discussion about what tree we
want to use.

And there are many more choices. For example, a radix tree might make sense,
since the names are effectively strings. Or, we could have (sometime in future)
a version that does not support updates, only complete rebuilds (then it is
reasonable to build a perfectly balanced tree instead), or one that doesn't
support DNSSEC (therefore it does not have to be a tree at all).

With regards

-- 
Einstein argued that there must be simplified explanations of nature, because
God is not capricious or arbitrary.  No such faith comforts the software
engineer.
                -- Fred Brooks

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20120620/f51b1750/attachment.bin>